基于改進節約算法的行蓄洪區物資配送路徑優化

張洪福，屈維意

（河海大學商學院，江蘇南京211100）

基于改進節約算法的行蓄洪區物資配送路徑優化

張洪福，屈維意

（河海大學商學院，江蘇南京211100）

針對行蓄洪區各避險高臺生活區能夠獲得充足與高效的物資配送，本研究采用以物資配送中心、行蓄洪區各避險高臺生活區為供應系統，以配送車輛的在途時間最小、車輛到達生活區的“時間滿意度”最大為目標，建立應急物資配送路徑優化模型，利用改進節約算法作為求解模型的算法，并用算例證明模型可解決3種類型物資產品在8處生活區之間最高效的物資配送，為洪水來臨前的物資配送問題提供決策依據。

節約算法；物資配送；洪災區；路徑優化

洪災后需要大量的應急物資，而物資產品則是應急物資中較為特殊的一類［1_3］。由于生活物資需求量在短時間內突然增大［4］，當地物資庫存無法滿足正常生活需求，需要從非災區物資中心緊急調運物資產品。在實際調運過程中，往往會有“食物報廢”和“生活物資荒”接連出現、因道路阻隔而導致物資供應中斷等現象［5］，如何解決物資供應不及時、效率低等問題成為是一個值得研究的課題。

應急物資車輛調度問題，其本質上是TPS（旅行商問題）。用于解決TPS問題的算法有很多：粒子群算法［6］，運籌方法［7］，蟻群算法［8］和節約算法［9］。但仍有諸多問題及未涉及的領域存在。尤其是對洪災后保障問題及生活物資運輸問題的研究，不管是生活物資保障體系、運輸模型的建立方面，還是解決模型的算法方面，仍有很大的研究空間。鑒于應急物資的成分性、食物的易腐性等特征［10］，以及洪災后事件救援過程的緊急性和弱經濟性等特征［11］，考慮物資到達行蓄洪區生活區的時間必須在一定的范圍之內以便更好地確保正常災民生活。

本文以一個物資中心、行蓄洪區若干高臺避險生活區為物資產品供應系統，以配送車輛的在途時間最小、車輛到達生活區的“時間滿意度”最大為目標，建立基于時間滿意度的應急物資產品配送路徑優化模型，并對節約算法進行改進，作為解決優化模型的算法，并用算例證明模型的可行性，為應急物資配送問題提供決策依據。

1　應急物資配送路徑優化模型的構建

1.1問題描述

行蓄洪區作為緩解洪峰壓力而臨時啟用的蓄水區，其地理位置具有相對特殊性。洪水來臨發生之后，人員立即被轉移到地勢較高的位置等待急救人員的救援。由于行蓄洪區內的物資有限，當地的物資中心要向各家物資中心緊急配送物資。在實際物資中，由于等待救援人員的種類不同，需要的生活必須物資也不相同，本文將應急救援物資成分分為生活用水、食物和帳篷3種物資產品種類。在實際運輸過程中，可能會出現堵車、道路中斷等交通狀況，故引入“路況系數”參數，來模擬運輸過程中的交通狀況。

文中利用“時間滿意度”的概念［12］，車輛到達行蓄洪區的時間滿意度0～1用之間的數表示，0表示行蓄洪區對車輛到達時間完全不滿意，1表示行蓄洪區對車輛到達時間完全滿意。根據實際需要，對模糊預約時間進行界定，如圖1所示。［Eti，Lti］表示行蓄洪區可接受的應急物資到達的最大時間范圍，［eti，lti］表示生活區期望物資產品到達的時間范圍。

圖1　時間滿意度函數圖像

則時間滿意度的模糊隸屬函數可以表示為：

擬解決的問題為：洪水發生后應急物資配送過程中，物資中心與行蓄洪區內各個生活區之間有多條路徑可以選擇。本文以減少配送車輛的在途時間和提高車輛到達生活區的“時間滿意度”為目標，解決應急物資從物資中心到各生活區的路線安排問題，保證應急物資在規定的時間內運達的同時提高行蓄洪區內生活區對到達時間點的滿意度。

1.2假設條件

為了清晰描述，避免不必要的問題干擾，本文在建立車輛配送路徑優化模型作如下假設：

1）車輛從物資中心出發，經過行蓄洪區內各生活區后返回到儲備中心，且每個生活區與物資中心及各個生活區之間的距離已知；2）車輛的載重量、車速已知，各車可以到多個生活區，但每個生活區只能由一輛車滿足其需要；3）物資中心配備足夠數量的車輛及應急物資滿足生活區內人員的需求；4）每輛車所裝載的應急物資各類型比例根據預測設置。

1.3符號表示

決策變量：

表1　符號對應表

1.4模型構建

應急物資配送的在途時間越小，行蓄洪區內被困人員則越有希望及時得到正常生活，所以模型目標函數之一是車輛的在途時間最小化，表示如下：

目標函數之二是車輛到達生活區的時間滿意度最大化，表示如下：

要獲得車輛到達時的時間滿意度，首先應算得車輛到達生活區的時刻，車輛到達節點j的時刻表示如下：

在車輛到達各生活區并將所需物資產品卸車后，應對車中剩余物資產品的量進行清算，以估計車中剩余物資產品的量是否能夠滿足下一個生活區的需求，到達生活區節點i時車輛中剩余的物資產品p的量為：

運輸車輛不能進行超載運輸，配送車輛所裝載的物資產品總量不應超過車輛的最大載重量，表示如下：

由于受配送車輛的數量限制，且從提高配送效率出發，每個私生活去所需的物資產品僅由一輛配送車配送，表示如下：

由于每個生活區僅會有一輛送物資車輛為其服務，所以每個生活區在且僅在一條線路中，表示如下：

發出的車輛數等于返回的車輛數，表示如下：

由于不可能出現多輛車向同一個生活區配送物資產品的情況，也不可能出現多輛車從同一個生活區出發繼續配送的情況，所以每條線路中任意一個生活區（即節點h）的上下有且僅有一個節點與之相連，表示如下：

生活區i點可接受物資產品的最大時間范圍，表示如下：

2　改進節約算法的行蓄洪區應急物資配送路徑優化求解

求解多目標規劃問題有多種方法，本文采用常見的線性加權和函數法［13］，引入時間權系數θ1和時間滿意度權系數θ2，其中θ1+θ2=1。根據對配送時間和時間滿意度的不同要求，可以靈活調整θ1和θ2的值。同時，為避免時間和時間滿意度目標量綱不同的影響，引入系數λ（h）。本問題現轉化為單目標的混合整數線性規劃問題［14］。

根據求解多目標規劃問題的方法以及節約算法的思想［15］，可先將上文所建模型的目標函數設置為時間節約值最大化和時間滿意度最大化，再將兩個目標函數合并為一個單目標函數，表示如下：

其中，fij即為合并后單目標的目標值，cij為節點i、j相連后的節約值。

算法步驟如下：

Step1：每個節點i與配送中心o連接，形成n條僅含一個送貨點的線路o—i—o，計算toi和tio；然后，計算任意兩節點連接后從節點i到節點j所需的時間tij，節約時間cij=toi+tio_tij；分別計算兩節點連接后車輛先到達i再到達j時生活區的滿意度S（ti）和S（tj），并根據式（13）得出fij；

Step2：把fij按照對應的有序對（i，j）排列成n×n的矩陣D，將其中負值元素化為0；

Step3：找出矩陣D中的最大元素fij（如有多個，則任選一個），對節點i、j進行考察：根式（4）、（5）計算出Qkp、tj，如果對?p，Qip≤Qkpi，Qjp≤Qkpi，且ti∈［Eti，Lti］，tj∈［Etj，Ltj］，則連接o—i—j—o，且令第i行、第i列和第j列的所有元素都為0，轉入Step5；否則，轉入Step4；

Step4：令fij=0，轉入Step3；

Step5：對路徑往后進行延伸。將j的數值賦予i；對矩陣D 非0元素進行改造：計算運輸工具到達下一個任意生活區節點時的滿意度S（tj），令S（ti）=0，根據式（13），對矩陣D的第i行賦予新的fij值（其他行數fij值不變）；

Step6：找出第i行最大元素fij，對節點j進行考察：根據式（4）、（5）計算出Qkp、tj，如果對?p，Qjp≤Qkpi，且ti∈［Eti，Lti］，則將j點接入路線，且令第i行，第j列的所有元素都為0，轉入Step5；否則，令fij=0，轉入Step6；

Step7：當矩陣D中第i行的元素都不滿足條件時，結束該條路徑，令第i行元素為0，轉入Step3；

Step8：當矩陣D中的所有元素都為0時，算法結束。

3　實證算例

某行蓄洪區發生泄洪后，人員轉移到當地地勢較高的8個高臺生活區，當地物資中心負責給這8處生活區運輸針對生活用水、食物和帳篷這3種類型物資產品。初步預測之后，8處生活區所需3種物資產品的數量見表2。運輸車輛的平均速度為50 km/h，物資中心到8處生活區的路程以及8處生活區相互之間的路程由表3給出，路段的路況系數由表4給出。每處生活區所要求的最早送達時間和最晚送達時間以及完全滿意的時間見表5。

表2　各生活處對各類物資產品的需求量

表3　各生活區之間的路程

假設：θ1=0.6，θ2=0.4，λ=0.2（h），經初步預測后，每輛車承載2 000單位生活用水物資產品，700單位食物物資產品和320單位帳篷物資產品。

根據上述算法，可得出優化結果：

1）0_6_8_4_0；2）0_7_3_5_0；3）0_2_1_0；

即物資中心可以派出3輛車進行物資的應急配送。第一輛車的行駛路徑為o—6—8—4—o；第二輛車的行駛路徑為o—7—3—5—o；第三輛車的行駛路徑為o—2—1—o。此路線相對于其他路線，更能節省車輛的在途時間，且能使物資到達的時間更加滿意，如圖2所示。

表4　各生活區之間的路況系數

表5　各生活區要求最早、最晚送達時間及完全滿意時間

圖2　物資產品配送優化路徑

4　結論

行蓄洪區泄洪后的物資保障直接關系受災人員的生活。本文研究了以一個物資種系、若干個行蓄洪區高臺避險生活區為系統的應應急產品配送路徑優化問題，在注重減少車輛在途時間的同時，利用了“時間滿意度”概念，滿足生活區對到達時間的要求，從而提高物資產品應急管理的效率。由此，本文以車輛在途時間最小以及車輛達到生活區的時間滿意度最大為目標，建立多目標應急物資配送路徑優化模型。本文在設計算法時遵循節約算法的基本思想，對其稍作改進后使之適用于上述模型的求解，并通過以一個物資中心、8個生活區為系統的算例證明了此模型可以優化配送路徑，算法也適用于模型的求解。

［1］鐘佳，劉鋼.城市防汛應急物資儲備模式研究［J］.人民長江，2013，44（20）：102_106.

［2］陳雷雷，王海燕.大規模突發事件中基于滿意度的應急物資優化調度模型［J］.中國安全科學學報，2010，20（5）：46_52.

［3］宋曉宇，劉春會，常春光.面向應急物資調度的一種灰色規劃模型［J］.計算機應用研究，2010，27（4）：1259_1262.

［4］張永領.公眾洪災應急避險模式和避險體系研究［J］.自然災害學報，2013（4）：95_104.

［5］張永領.基于層次分析法的應急物資儲備方式研究［J］.災害學，2011（3）：120_125.

［6］田軍，馬文正，汪應洛，等.應急物資配送動態調度的粒子群算法［J］.系統工程理論與實踐，2011，31（5）：898_906.

［7］Knott R P.Vehic1e schedu1ing for emergency re1ief managem_ ent：a know1edge_based approach［J］.Disasters，1988，12（4）：285_ 293.

［8］徐志宇，彭嘉臻，許維勝.應急物流的分批配送規劃及蟻群優化求解［J］.計算機工程與應用，2011，47（24）：1_3，8.

［9］賈濤，劉靜，陳方婕.異質車輛配送可重復裝貨易腐品庫存路徑模型［J］.工業工程與管理，2012（4）：15_20+30.

［10］張連瑞.基于應急物資管理創新的物資供應保障能力研究［J］.價值工程，2015（3）：27_28.

［11］汪茜，梁立武，楊軼，等.洪災與地震醫療救援的對比分析［J］.武警醫學，2011，22（1）：85_87.

［12］俞武揚.基于時間滿意度的應急物資中轉運輸模型［J］.系統管理學報，2013，22（6）：882_887.

［13］莫鴻強，李向陽，萬國成，等.加權編碼遺傳算法線性函數能力分析［J］.計算機工程與應用，2007（8）：85_87.

［14］陳艷波，馬進，陳茜.混合整數線性規劃形式的抗差狀態估計方法［J］.電力自動化設備，2015，35（7）：26_31.

［15］金成，閔嘉寧.供應鏈物流配送路徑優化節約算法改進研究［J］.制造業自動化，2014（1）：86_89.

ImProVed saVlng algorlthm for dlstrlbutlon Path oPtlmlzatlon based on flood storage materlals

ZHANG Hong_fu，QU Wei_yi
（School of Business，Hohai University，Nanjing 211100，China）

For high_risk f1ood p1ain 1iving areas each have access to adequate and efficient materia1 distribution，this study in materia1s distribution center，high_risk f1ood p1ain each 1iving area for the supp1y system to the distribution of vehic1es in transit time is minimized，the vehic1e reaches″Time satisfaction″1iving areas up to the goa1，the estab1ishment of emergency supp1ies distribution route optimization mode1，the improved a1gorithm as the a1gorithm mode1 of conservation，and use examp1es to prove the mode1 can so1ve the three types of supp1ies products in the 1iving area between 8 most efficient materia1 distribution for supp1ies before the onset of the f1ood distribution prob1ems making basis.

saving a1gorithmj materia1 distributionj f1ood disasterj route optimization

TN02

A

1674_6236（2016）10_0009_04

2016_01_16稿件編號：201601128

國家自然科學基金項目資助（41401010）；江蘇省社會科學基金項目（13GLC011）

張洪福（1991—），男，吉林遼源人，碩士研究生。研究方向：水資源開發與規劃。