應(yīng)急物資調(diào)度方案的優(yōu)化問題研究

董玉玲，劉小芳

（1.人工智能四川省重點實驗室，自貢643000；2.四川輕化工大學(xué)自動化與信息工程學(xué)院，自貢643000；3.四川輕化工大學(xué)計算機(jī)科學(xué)與工程學(xué)院，自貢643000）

0 引言

廣泛的應(yīng)急物資的調(diào)度問題研究選取以地震災(zāi)害為例展開說明，原因為地震是危害力極大、發(fā)生率極高的自然災(zāi)害之一，同時，地震的發(fā)生也會影響著人類自身的生存與社會經(jīng)濟(jì)的持續(xù)發(fā)展[1]，具有一定的可行性與相似性。自二十一世紀(jì)以來，里氏6.0級以上地震發(fā)生了1584次，平均113次。如青海玉樹的7.1級地震，云南盈江的5.8級地震，新疆于田的7.3級地震，四川雅安的7.0級地震等。從科學(xué)技術(shù)層面而言，地震是不可阻止與避免的，為一定程度上減少高頻地震災(zāi)害產(chǎn)生的損失，采取合理的應(yīng)急資源調(diào)度方案已然成為應(yīng)對突發(fā)地震災(zāi)害的必要措施，因此以震災(zāi)為例，對應(yīng)急物資調(diào)度方案的優(yōu)化問題研究具有較大意義。

在震災(zāi)物資調(diào)度決策問題上，關(guān)鍵在于物資運(yùn)輸?shù)臅r效性、安全性和經(jīng)濟(jì)性三個分量函數(shù)之間的衡量抉擇。針對車輛運(yùn)輸?shù)奶厥庑?，目前車輛運(yùn)輸問題（VRP）受到廣泛關(guān)注與重視，若以運(yùn)輸成本最小化作為目標(biāo)，Knott[2]提出的一個關(guān)于應(yīng)急食品調(diào)度的線性規(guī)劃數(shù)學(xué)模型，用作散裝食品運(yùn)輸以及配送車輛隊伍的效率提升，目標(biāo)是使運(yùn)輸成本最低或者配送食品的數(shù)量最多；若以延遲時間最小化作為目標(biāo)，何建敏[3]提出的在發(fā)生大規(guī)模震災(zāi)時，多出救點車輛調(diào)度的組合優(yōu)化問題以滿足受災(zāi)點的應(yīng)急物資需求量；若以運(yùn)輸路徑最小化作為目標(biāo)，F(xiàn)u[4]提出在旅行時間還沒有確定的情況下，交通網(wǎng)絡(luò)中的最短路徑問題可以描述為動態(tài)隨機(jī)最短路徑問題（Dynamic and Stochastic Shortest Problem，DSSP），在網(wǎng)絡(luò)中有部分或全部弧的旅行時間未固定而是無規(guī)律變化的，其概率分布在于抵達(dá)此弧的不同時刻，把隨機(jī)過程作為描述交通網(wǎng)絡(luò)中路徑選擇的參數(shù)。

因應(yīng)急物資車輛路線選擇問題相對復(fù)雜，所以使用指派問題中的旅行商理論方法，依據(jù)三個分量屬性分別構(gòu)造目標(biāo)函數(shù)，隨后通過無量綱處理和權(quán)重聚合賦權(quán)處理（組合賦權(quán)處理）轉(zhuǎn)化為單目標(biāo)函數(shù)，最后使用樹算法求得理想目標(biāo)函數(shù)值，以此獲得最佳物資協(xié)調(diào)方案。

1 系統(tǒng)建模

應(yīng)急物資的運(yùn)輸調(diào)度方案中選擇運(yùn)輸路線問題實質(zhì)上屬于多目標(biāo)決策問題，其主要決策問題是使多目標(biāo)決策函數(shù)的三個分決策函數(shù)：時效性函數(shù)、經(jīng)濟(jì)性函數(shù)和安全性函數(shù)都達(dá)到最佳值（或理想值）然后確定其優(yōu)先排列順序。首先，通過每個方案的時效性函數(shù)、經(jīng)濟(jì)性函數(shù)和安全性函數(shù)使用無量綱處理的方法，隨后通過組合賦權(quán)法使各個目標(biāo)子函數(shù)融合在一個函數(shù)式子即得到?jīng)Q策效用函數(shù)。最后，為了選取最優(yōu)路線調(diào)度決策方案，利用數(shù)算法求解目標(biāo)決策函數(shù)的數(shù)學(xué)模型。

1.1 多目標(biāo)函數(shù)的構(gòu)造

在地震災(zāi)害發(fā)生時，對詳細(xì)情況進(jìn)行分析，若各物資存儲點（或出救點）的應(yīng)急物資能夠滿足各受災(zāi)點的需求，解決在滿足需求的情況下，如何將各類應(yīng)急物資從多個出救點運(yùn)送至多個受災(zāi)點（或災(zāi)害點）。假定各受災(zāi)點需要的應(yīng)急物資數(shù)量未知或因道路、天氣等外界因素導(dǎo)致的運(yùn)輸時間不確定性。因此，將震災(zāi)爆發(fā)后的應(yīng)急物資運(yùn)輸方案的選擇問題可描述為：假設(shè)現(xiàn)在考慮某一種應(yīng)急物資“棉被”需要調(diào)配，已知可供應(yīng)“棉被”有D1，D2，…，Dm的m個庫存點（如地震應(yīng)急物資儲備庫所在地），需要“棉被”有S1，S2，…，Sn的n個受災(zāi)點。假設(shè)在時刻t，需要將應(yīng)急物資“棉被”從庫存點i運(yùn)送至受災(zāi)點j，其中受災(zāi)區(qū)j的人員受傷死亡密度為Rj，所對應(yīng)的運(yùn)輸成本為Pij，運(yùn)輸時間為Tij，選擇的應(yīng)急物資調(diào)度優(yōu)化方案應(yīng)當(dāng)滿足以下要求：每個存儲點應(yīng)提供應(yīng)急物資的數(shù)量為多少，分別運(yùn)送至哪些災(zāi)害點，當(dāng)Di=0則說明第i個存儲點不參與此次應(yīng)急物資的運(yùn)輸，應(yīng)急物資運(yùn)輸目標(biāo)應(yīng)該在滿足各受災(zāi)點的應(yīng)急物資需求作為前提，使得時間最短或傷亡密度最大或成本最低。即多目標(biāo)函數(shù)的表示為：

1.2 決策效用函數(shù)數(shù)學(xué)模型的構(gòu)造

假設(shè)在地震災(zāi)害的應(yīng)急物資運(yùn)送問題中，時效性、安全性和經(jīng)濟(jì)性三者互相獨(dú)立，利用其獨(dú)立且互相不影響的特性，將多目標(biāo)決策效用函數(shù)轉(zhuǎn)換為單目標(biāo)效用函數(shù)的加法函數(shù)[5]。即可將決策效用函數(shù)表示為目標(biāo)分量得無量綱指標(biāo)加法函數(shù)。因此，對時效性分函數(shù)、經(jīng)濟(jì)性分函數(shù)和安全性分函數(shù)三個子目標(biāo)函數(shù)通過無量綱處理的方法，得到各分量函數(shù)的理想數(shù)值（最大值或最小值），完成求解多目標(biāo)決策函數(shù)的第一步。

針對時效性函數(shù)中的時間分量，使用Dijkstra算法在道路網(wǎng)絡(luò)圖上求出理想值即最短時間和最長時間。假定在地震發(fā)生后，應(yīng)急物資從存儲點i運(yùn)送至受災(zāi)點j，所需要的時間表示為Tij，因此，最短時間為Tmin，最長時間為Tmax，g(i1j)為運(yùn)輸時間Tij的無量綱指標(biāo)，表達(dá)式如下：

因為Tmin≤Tij≤Tmax，則時間的無量綱指標(biāo)g(i1j)∈(0，1)，而Tmax-Tmin的值是固定不變，Tij的值越小，則分子Tmax-Tij的值越大，即g(i1j)的值越大，代表運(yùn)輸時間越短或時效性函數(shù)越佳的運(yùn)輸路徑，對應(yīng)的無量指標(biāo)g(i1j)越大[6]。

同理可得，設(shè)應(yīng)急物資從存儲點i運(yùn)送至受災(zāi)點j，運(yùn)輸成本表示為Pij，g(i2j)為運(yùn)輸費(fèi)用的無量綱指標(biāo)。因此，最低運(yùn)輸費(fèi)用為Pmin和最高運(yùn)輸費(fèi)用為Pmax，表達(dá)式如下：

由于Pmin≤Pij≤Pmax，由上式可得，運(yùn)費(fèi)的無量綱指標(biāo)g(i2j)∈(0，1)，而Pmax-Pmin的值固定不變，Pij的值越小，則分子Pmax-Pij的值越大，即g(i2j)的值越大，表明g(i2j)的值越大就選運(yùn)輸費(fèi)用越低的條件相契合。

針對安全性函數(shù)中的人員傷亡分量，利用數(shù)據(jù)融合技術(shù)統(tǒng)計應(yīng)急物資從受災(zāi)點i運(yùn)送至受災(zāi)點j的人員傷亡密度，設(shè)g(i3j)為受災(zāi)點j的傷亡密度無量綱指標(biāo)，最大傷亡密度表示為Rmax，最小傷亡密度表示為Rmin，與此同時，為保持與其他兩個分量無量綱指標(biāo)的一致，g(i3j)的值越大越好，換句話說，隨著人員傷亡分量或傷亡密度R的值越大，g(i3j)的值越大，即安全性函數(shù)越好。則表達(dá)式如下：

假設(shè)α1、α2、α3表示應(yīng)急物資調(diào)度管理的時間性決策函數(shù)、經(jīng)濟(jì)性決策函數(shù)、安全性決策函數(shù)這三個分量決策函數(shù)的權(quán)重，其權(quán)重向量為α=（α1，α2，α3）T，滿足0≤α1≤1，0≤α2≤1,0≤α3≤1,α1+α2+α3=1，設(shè)Gij為運(yùn)輸線路的決策效用指標(biāo)，則相應(yīng)路徑選擇的決策效用函數(shù)數(shù)學(xué)模型如下所示：

由上所得，若Gij的數(shù)值越大，物資運(yùn)輸路線的綜合評價性指標(biāo)越高即效果越佳，所以選取Gij值最大的應(yīng)急物資運(yùn)輸路徑（從存儲點i運(yùn)送至受災(zāi)點j）為最終決策。

2 加權(quán)處理

目前，確定權(quán)重主要有三類方法:組合賦權(quán)法（主客觀綜合賦權(quán)法）、主觀賦權(quán)法以及客觀賦權(quán)法。主觀賦權(quán)法是依據(jù)決策者（或?qū)＜遥γ款悓傩缘闹饔^關(guān)注度來確定權(quán)重。如專家調(diào)查法（Delphi法）、二項系數(shù)法及層次分析法（AHP法）等[7]。客觀賦權(quán)法是依照各目標(biāo)函數(shù)的原始數(shù)據(jù)間的關(guān)系，不依靠人的主觀偏好來確定權(quán)重。如主成分分析法、均方差法及熵法等。

結(jié)合主、客觀賦權(quán)法各自的優(yōu)缺點，以及決策者（或?qū)＜遥x權(quán)法的偏好度和賦權(quán)法原始數(shù)據(jù)的一致性程度是相對合情合理的，使對權(quán)重的確定達(dá)到主觀方面與客觀方面的互相統(tǒng)一，得到的最終決策結(jié)果更加真實有說服力，提出了一類綜合主、客觀賦權(quán)優(yōu)點的方法，即組合賦權(quán)法。

2.1 數(shù)據(jù)預(yù)處理

假設(shè)有n個決策方案，其方案集合表示為B={B1，B2，…，Bn}，決策目標(biāo)有m個，其指標(biāo)集表示為U={U1，U2，…，Um}，方案Bj=(j=1，2，3，…n)在決策目標(biāo)Ui=(i=1，2，3，…m)下的屬性值為λij，決策矩陣（或?qū)傩跃仃嚕锽=(λij)m*n。通常，目標(biāo)類型有效益型與成本型。效益性目標(biāo)表示正比型指標(biāo)（即效益值越大越好的指標(biāo)），成本性目標(biāo)表示反比型指標(biāo)（即成本值越小越好的指標(biāo)）。由于各目標(biāo)屬性具有不同的量綱與量綱單位，由此具有的不可公度性將會對決策結(jié)果有一定影響，此前，應(yīng)將目標(biāo)屬性指標(biāo)做預(yù)處理，即通過無量綱處理將決策矩陣（或?qū)傩跃仃嚕┗癁橐?guī)范化矩陣。（λmjax、λmjin分別表示決策目標(biāo)j的最大和最小值。）設(shè)效益型目標(biāo)為：

可以看出，rij∈[0,1]，1≤i≤m,1≤j≤n，所以規(guī)范化矩陣為:R=(rij)m*n

結(jié)合主、客觀權(quán)重賦權(quán)法的利弊，可以考慮組合的賦權(quán)方法ω=(ω1,ω2,ωm)T，稱ω為集成后的權(quán)重向量，ωˉ"、ωˉ*分別稱為主、客觀綜合權(quán)重，其表達(dá)式如下：

首先是主觀權(quán)重賦權(quán)法，由于各個決策者（或?qū)＜遥┰诟鶕?jù)對每個目標(biāo)屬性的重視程度進(jìn)行賦值時，難以兼顧每一個目標(biāo)屬性之間的互相影響與制約[8]，所以在決策者（或?qū)＜遥┰诮o出一般情況下的決策權(quán)重為ω=(ω1,ω2,ω3,…,ωm)T后，引 入 目 標(biāo) 影 響 權(quán) 重[9]為ω(2)=(ω1(2),ω2(2),…,ωm(2))T。設(shè)xij是表示目標(biāo)Ui對目標(biāo)Uj的影響程度，則有目標(biāo)相互影響矩陣為：X=(xij)m*n，而表示目標(biāo)Ui對其余目標(biāo)的影響度，而表示目標(biāo)Uj對其余目標(biāo)的影響度。

因此，由目標(biāo)之間相互影響度所得到的權(quán)重為：

若不考慮目標(biāo)間的影響程度只考慮目標(biāo)本身的價值權(quán)重為：

比較以上兩式可得，式（9）綜合考慮到了目標(biāo)的價值權(quán)重，這表明在一個目標(biāo)對價值權(quán)重的重要程度上相對較高或稱為有較大影響力，則其影響的權(quán)重也會隨之相對較高。綜上兩種權(quán)重的表達(dá)式，能夠全方位的反映出一個目標(biāo)的相對重要程度屬性，假設(shè)λ為目標(biāo)價值權(quán)重與目標(biāo)影響權(quán)重的比例因子，且0<λ<1則有主觀綜合權(quán)重為：

同時，對目標(biāo)之間相互影響所得到的權(quán)重、目標(biāo)本身的價值權(quán)重及主觀權(quán)重為：

2.2 主客觀權(quán)重的集成與評價

假設(shè)θ1、θ2分別為主、客觀權(quán)重的重要程度指標(biāo)系數(shù)（或組合權(quán)系數(shù)向量的線性表出系數(shù)）且θ1+θ2=1，θ1>0，θ2>0，將主觀權(quán)重ωˉ"與客觀權(quán)重ωˉ*集和組成即代入式（8）有：

從上式可以看出，集成后的權(quán)重向量包括主觀權(quán)重即反映決策者（或?qū)＜遥┑钠玫臋?quán)重和目標(biāo)間相互影響的權(quán)重，以及客觀權(quán)重即反映原始數(shù)據(jù)屬性的權(quán)重，從而使權(quán)重的確定更加精準(zhǔn)。

2.3 構(gòu)建單目標(biāo)函數(shù)數(shù)學(xué)模型

（1）樹算法

分配問題又可以看做為指派問題，即將m項任務(wù)分給n個人的指派問題，每人只能完成一項任務(wù)，且每個任務(wù)只能由本人獨(dú)立完成，第i個人單獨(dú)完成第j項任務(wù)的效益為cij，如何才能使總效益值達(dá)到最小?[12]由文獻(xiàn)[13]可以清楚知道樹算法的基本思想，即在完整指派樹中每片樹葉有相對應(yīng)一個指派方案，共有n!個樹葉，最優(yōu)指派方案就是從所有樹葉中找出數(shù)值最小的樹葉，逆向追蹤得到的指派方案。

（2）數(shù)學(xué)模型的構(gòu)建

分配問題或指派問題的求解通常是匈牙利算法，但是其解法步驟復(fù)雜、不實用，所以選擇優(yōu)化改進(jìn)或找尋其他簡易方法，樹算法是簡易中的其中一種。由上述介紹可以推出，樹算法也可運(yùn)用于運(yùn)籌學(xué)[14]中的最優(yōu)匹配問題或最優(yōu)指派問題，所以，利用此特性能將決策效用函數(shù)矩陣類比于樹算法中的效益矩陣，得到最佳應(yīng)急物資調(diào)度方案，則有數(shù)學(xué)模型如下所示：

在指派問題中，xij=1/0，1表示指定第i個人完成第j項任務(wù)，0表示不指定第i個人完成第j項任務(wù)，在本文來講，xij=0是表示運(yùn)輸路線不經(jīng)過路段(i，j)，xij=1是表示物資運(yùn)輸路線經(jīng)過路段(i，j)，在運(yùn)算求解最大效益值fmax(xˉ)的過程中就能得到最佳調(diào)度路線方案。

3 案例分析

假設(shè)某城市發(fā)生突發(fā)性強(qiáng)烈地震災(zāi)害，現(xiàn)在需要將應(yīng)急物資從存儲點運(yùn)送至受災(zāi)點，設(shè)現(xiàn)有四個存儲點D1、D2、D3、D4和四個受災(zāi)點S1、S2、S3、S4，從存儲點Di到受災(zāi)點Sj，對應(yīng)的運(yùn)輸成本為Pij，配送時間為Tij，其中在發(fā)生地震的第5小時后，受災(zāi)區(qū)j的人員受傷死亡密度為Rj，如表1-表3。

表1 運(yùn)輸成本表（千元）

表2 配送時間表（小時）

表3 人員受傷死亡密度（個／1萬平方米）

3.1 無量綱處理

由式（2）、（3）、（4）可得無量綱處理后的數(shù)值，如表4-表6所示。

表4 運(yùn)輸成本表（千元）

表5 配送時間表（小時）

表6 人員受傷死亡密度（個／1萬平方米）

3.2 加權(quán)處理

針對三個存儲點D1、D2、D3和三個受災(zāi)點S1、S2、S3其方案集有6個，分別表示為F1（D1→S1，D2→S2，D3→S3），F(xiàn)2（D1→S1，D2→S3，D3→S2），F(xiàn)3（D1→S2，D2→S1，D3→S3），F(xiàn)4（D1→S2，D2→S3，D3→S1），F(xiàn)5（D1→S3，D2→S2，D3→S1，F(xiàn)6（D1→S3，D2→S2，D3→S1），評估目標(biāo)有三項：時效性是U1、安全性是U2及經(jīng)濟(jì)性是U3，同時，專家給出的權(quán)重表示為：ω=（0.45，0.28,0.27）；其中0代表無影響、2代表較小影響、4代表一般影響及8代表較大影響，則有目標(biāo)相互影響矩陣為：

而且U1、U3為成本型目標(biāo)，U2為效益性目標(biāo)，則經(jīng)無量綱處理后的規(guī)范化矩陣如下所示：（說明：屬性值取無量綱處理后每一個方案Bj(j=1，2，3，…，n)在決策目標(biāo)Ui(i=1，2，3，…，n)下的屬性值λij的平均值作為規(guī)范化矩陣）。

然后，由式（10）和式（11）可得主觀權(quán)向量ωˉ"，取λ=0.5，其表達(dá)式如下：

ωˉ"=(0.4199,0.3242,0.2558)T

由式（18）可得客觀權(quán)向量ωˉ*，則有表達(dá)式為：

ωˉ*=(0.3964,0.3559,0.2477)T

假設(shè)主、客觀權(quán)重的重要程度相同，即θ1=θ2=0.5，由式（19）可得集成后的權(quán)重為：

ω=(0.4082,0.3401,0.2518)T

所以三個分量決策函數(shù)的權(quán)重分別為α1=0.4082，α2=0.3401，α3=0.2518，由式（5）可得決策效用指標(biāo)函數(shù)Gij，則如表7所示。

表7 決策效用指標(biāo)函數(shù)Gij

利用樹算法求解[]計算其他分枝，根據(jù)簡化指派樹得最大效益值，可得最優(yōu)方案為方案F2（D1→S1，D2→S3，D3→S2）。

4 結(jié)語

本文依據(jù)震災(zāi)發(fā)生后的應(yīng)急物資運(yùn)輸?shù)臅r效性、傷亡性和經(jīng)濟(jì)性三大特性解決多目標(biāo)決策問題，利用無量綱處理和將決策者（或?qū)＜遥┑钠靡蛩亍Q策目標(biāo)間互相影響因素與客觀因素最大程度集成在一起的主客觀賦權(quán)法確定目標(biāo)權(quán)重，再經(jīng)構(gòu)造決策效用指標(biāo)函數(shù)使多目標(biāo)決策轉(zhuǎn)化為單目標(biāo)，最后，通過樹算法轉(zhuǎn)化為極小值問題求解最值的過程中找到最佳路線匹配，求得最佳的震災(zāi)應(yīng)急物資調(diào)度方案。以此震災(zāi)的應(yīng)急物資調(diào)度方案研究可推論至廣泛的應(yīng)急物資調(diào)度問題研究，具有相對可行性與有效性，但優(yōu)越性還需再深入研討。