應急物資調度方案的優化問題研究

董玉玲，劉小芳

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

0 引言

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

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

因應急物資車輛路線選擇問題相對復雜，所以使用指派問題中的旅行商理論方法，依據三個分量屬性分別構造目標函數，隨后通過無量綱處理和權重聚合賦權處理（組合賦權處理）轉化為單目標函數，最后使用樹算法求得理想目標函數值，以此獲得最佳物資協調方案。

1 系統建模

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

1.1 多目標函數的構造

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

1.2 決策效用函數數學模型的構造

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

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

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

同理可得，設應急物資從存儲點i運送至受災點j，運輸成本表示為Pij，g(i2j)為運輸費用的無量綱指標。因此，最低運輸費用為Pmin和最高運輸費用為Pmax，表達式如下：

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

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

假設α1、α2、α3表示應急物資調度管理的時間性決策函數、經濟性決策函數、安全性決策函數這三個分量決策函數的權重，其權重向量為α=（α1，α2，α3）T，滿足0≤α1≤1，0≤α2≤1,0≤α3≤1,α1+α2+α3=1，設Gij為運輸線路的決策效用指標，則相應路徑選擇的決策效用函數數學模型如下所示：

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

2 加權處理

目前，確定權重主要有三類方法:組合賦權法（主客觀綜合賦權法）、主觀賦權法以及客觀賦權法。主觀賦權法是依據決策者（或專家）對每類屬性的主觀關注度來確定權重。如專家調查法（Delphi法）、二項系數法及層次分析法（AHP法）等[7]。客觀賦權法是依照各目標函數的原始數據間的關系，不依靠人的主觀偏好來確定權重。如主成分分析法、均方差法及熵法等。

結合主、客觀賦權法各自的優缺點，以及決策者（或專家）對賦權法的偏好度和賦權法原始數據的一致性程度是相對合情合理的，使對權重的確定達到主觀方面與客觀方面的互相統一，得到的最終決策結果更加真實有說服力，提出了一類綜合主、客觀賦權優點的方法，即組合賦權法。

2.1 數據預處理

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

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

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

首先是主觀權重賦權法，由于各個決策者（或專家）在根據對每個目標屬性的重視程度進行賦值時，難以兼顧每一個目標屬性之間的互相影響與制約[8]，所以在決策者（或專家）在給出一般情況下的決策權重為ω=(ω1,ω2,ω3,…,ωm)T后，引 入 目 標 影 響 權 重[9]為ω(2)=(ω1(2),ω2(2),…,ωm(2))T。設xij是表示目標Ui對目標Uj的影響程度，則有目標相互影響矩陣為：X=(xij)m*n，而表示目標Ui對其余目標的影響度，而表示目標Uj對其余目標的影響度。

因此，由目標之間相互影響度所得到的權重為：

若不考慮目標間的影響程度只考慮目標本身的價值權重為：

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

同時，對目標之間相互影響所得到的權重、目標本身的價值權重及主觀權重為：

2.2 主客觀權重的集成與評價

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

從上式可以看出，集成后的權重向量包括主觀權重即反映決策者（或專家）的偏好的權重和目標間相互影響的權重，以及客觀權重即反映原始數據屬性的權重，從而使權重的確定更加精準。

2.3 構建單目標函數數學模型

（1）樹算法

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

（2）數學模型的構建

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

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

3 案例分析

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

表1 運輸成本表（千元）

表2 配送時間表（小時）

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

3.1 無量綱處理

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

表4 運輸成本表（千元）

表5 配送時間表（小時）

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

3.2 加權處理

針對三個存儲點D1、D2、D3和三個受災點S1、S2、S3其方案集有6個，分別表示為F1（D1→S1，D2→S2，D3→S3），F2（D1→S1，D2→S3，D3→S2），F3（D1→S2，D2→S1，D3→S3），F4（D1→S2，D2→S3，D3→S1），F5（D1→S3，D2→S2，D3→S1，F6（D1→S3，D2→S2，D3→S1），評估目標有三項：時效性是U1、安全性是U2及經濟性是U3，同時，專家給出的權重表示為：ω=（0.45，0.28,0.27）；其中0代表無影響、2代表較小影響、4代表一般影響及8代表較大影響，則有目標相互影響矩陣為：

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

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

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

由式（18）可得客觀權向量ωˉ*，則有表達式為：

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

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

ω=(0.4082,0.3401,0.2518)T

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

表7 決策效用指標函數Gij

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

4 結語

本文依據震災發生后的應急物資運輸的時效性、傷亡性和經濟性三大特性解決多目標決策問題，利用無量綱處理和將決策者（或專家）的偏好因素、決策目標間互相影響因素與客觀因素最大程度集成在一起的主客觀賦權法確定目標權重，再經構造決策效用指標函數使多目標決策轉化為單目標，最后，通過樹算法轉化為極小值問題求解最值的過程中找到最佳路線匹配，求得最佳的震災應急物資調度方案。以此震災的應急物資調度方案研究可推論至廣泛的應急物資調度問題研究，具有相對可行性與有效性，但優越性還需再深入研討。