張洪福，屈維意

（河海大學(xué)商學(xué)院，江蘇南京211100）

基于改進(jìn)節(jié)約算法的行蓄洪區(qū)物資配送路徑優(yōu)化

張洪福，屈維意

（河海大學(xué)商學(xué)院，江蘇南京211100）

針對行蓄洪區(qū)各避險(xiǎn)高臺生活區(qū)能夠獲得充足與高效的物資配送，本研究采用以物資配送中心、行蓄洪區(qū)各避險(xiǎn)高臺生活區(qū)為供應(yīng)系統(tǒng)，以配送車輛的在途時(shí)間最小、車輛到達(dá)生活區(qū)的“時(shí)間滿意度”最大為目標(biāo)，建立應(yīng)急物資配送路徑優(yōu)化模型，利用改進(jìn)節(jié)約算法作為求解模型的算法，并用算例證明模型可解決3種類型物資產(chǎn)品在8處生活區(qū)之間最高效的物資配送，為洪水來臨前的物資配送問題提供決策依據(jù)。

節(jié)約算法；物資配送；洪災(zāi)區(qū)；路徑優(yōu)化

洪災(zāi)后需要大量的應(yīng)急物資，而物資產(chǎn)品則是應(yīng)急物資中較為特殊的一類［1_3］。由于生活物資需求量在短時(shí)間內(nèi)突然增大［4］，當(dāng)?shù)匚镔Y庫存無法滿足正常生活需求，需要從非災(zāi)區(qū)物資中心緊急調(diào)運(yùn)物資產(chǎn)品。在實(shí)際調(diào)運(yùn)過程中，往往會有“食物報(bào)廢”和“生活物資荒”接連出現(xiàn)、因道路阻隔而導(dǎo)致物資供應(yīng)中斷等現(xiàn)象［5］，如何解決物資供應(yīng)不及時(shí)、效率低等問題成為是一個(gè)值得研究的課題。

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

本文以一個(gè)物資中心、行蓄洪區(qū)若干高臺避險(xiǎn)生活區(qū)為物資產(chǎn)品供應(yīng)系統(tǒng)，以配送車輛的在途時(shí)間最小、車輛到達(dá)生活區(qū)的“時(shí)間滿意度”最大為目標(biāo)，建立基于時(shí)間滿意度的應(yīng)急物資產(chǎn)品配送路徑優(yōu)化模型，并對節(jié)約算法進(jìn)行改進(jìn)，作為解決優(yōu)化模型的算法，并用算例證明模型的可行性，為應(yīng)急物資配送問題提供決策依據(jù)。

1　應(yīng)急物資配送路徑優(yōu)化模型的構(gòu)建

1.1問題描述

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

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

圖1　時(shí)間滿意度函數(shù)圖像

則時(shí)間滿意度的模糊隸屬函數(shù)可以表示為：

擬解決的問題為：洪水發(fā)生后應(yīng)急物資配送過程中，物資中心與行蓄洪區(qū)內(nèi)各個(gè)生活區(qū)之間有多條路徑可以選擇。本文以減少配送車輛的在途時(shí)間和提高車輛到達(dá)生活區(qū)的“時(shí)間滿意度”為目標(biāo)，解決應(yīng)急物資從物資中心到各生活區(qū)的路線安排問題，保證應(yīng)急物資在規(guī)定的時(shí)間內(nèi)運(yùn)達(dá)的同時(shí)提高行蓄洪區(qū)內(nèi)生活區(qū)對到達(dá)時(shí)間點(diǎn)的滿意度。

1.2假設(shè)條件

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

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

1.3符號表示

決策變量：

表1　符號對應(yīng)表

1.4模型構(gòu)建

應(yīng)急物資配送的在途時(shí)間越小，行蓄洪區(qū)內(nèi)被困人員則越有希望及時(shí)得到正常生活，所以模型目標(biāo)函數(shù)之一是車輛的在途時(shí)間最小化，表示如下：

目標(biāo)函數(shù)之二是車輛到達(dá)生活區(qū)的時(shí)間滿意度最大化，表示如下：

要獲得車輛到達(dá)時(shí)的時(shí)間滿意度，首先應(yīng)算得車輛到達(dá)生活區(qū)的時(shí)刻，車輛到達(dá)節(jié)點(diǎn)j的時(shí)刻表示如下：

在車輛到達(dá)各生活區(qū)并將所需物資產(chǎn)品卸車后，應(yīng)對車中剩余物資產(chǎn)品的量進(jìn)行清算，以估計(jì)車中剩余物資產(chǎn)品的量是否能夠滿足下一個(gè)生活區(qū)的需求，到達(dá)生活區(qū)節(jié)點(diǎn)i時(shí)車輛中剩余的物資產(chǎn)品p的量為：

運(yùn)輸車輛不能進(jìn)行超載運(yùn)輸，配送車輛所裝載的物資產(chǎn)品總量不應(yīng)超過車輛的最大載重量，表示如下：

由于受配送車輛的數(shù)量限制，且從提高配送效率出發(fā)，每個(gè)私生活去所需的物資產(chǎn)品僅由一輛配送車配送，表示如下：

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

發(fā)出的車輛數(shù)等于返回的車輛數(shù)，表示如下：

由于不可能出現(xiàn)多輛車向同一個(gè)生活區(qū)配送物資產(chǎn)品的情況，也不可能出現(xiàn)多輛車從同一個(gè)生活區(qū)出發(fā)繼續(xù)配送的情況，所以每條線路中任意一個(gè)生活區(qū)（即節(jié)點(diǎn)h）的上下有且僅有一個(gè)節(jié)點(diǎn)與之相連，表示如下：

生活區(qū)i點(diǎn)可接受物資產(chǎn)品的最大時(shí)間范圍，表示如下：

2　改進(jìn)節(jié)約算法的行蓄洪區(qū)應(yīng)急物資配送路徑優(yōu)化求解

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

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

其中，fij即為合并后單目標(biāo)的目標(biāo)值，cij為節(jié)點(diǎn)i、j相連后的節(jié)約值。

算法步驟如下：

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

Step2：把fij按照對應(yīng)的有序?qū)Γ╥，j）排列成n×n的矩陣D，將其中負(fù)值元素化為0；

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

Step4：令fij=0，轉(zhuǎn)入Step3；

Step5：對路徑往后進(jìn)行延伸。將j的數(shù)值賦予i；對矩陣D 非0元素進(jìn)行改造：計(jì)算運(yùn)輸工具到達(dá)下一個(gè)任意生活區(qū)節(jié)點(diǎn)時(shí)的滿意度S（tj），令S（ti）=0，根據(jù)式（13），對矩陣D的第i行賦予新的fij值（其他行數(shù)fij值不變）；

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

Step7：當(dāng)矩陣D中第i行的元素都不滿足條件時(shí)，結(jié)束該條路徑，令第i行元素為0，轉(zhuǎn)入Step3；

Step8：當(dāng)矩陣D中的所有元素都為0時(shí)，算法結(jié)束。

3　實(shí)證算例

某行蓄洪區(qū)發(fā)生泄洪后，人員轉(zhuǎn)移到當(dāng)?shù)氐貏葺^高的8個(gè)高臺生活區(qū)，當(dāng)?shù)匚镔Y中心負(fù)責(zé)給這8處生活區(qū)運(yùn)輸針對生活用水、食物和帳篷這3種類型物資產(chǎn)品。初步預(yù)測之后，8處生活區(qū)所需3種物資產(chǎn)品的數(shù)量見表2。運(yùn)輸車輛的平均速度為50 km/h，物資中心到8處生活區(qū)的路程以及8處生活區(qū)相互之間的路程由表3給出，路段的路況系數(shù)由表4給出。每處生活區(qū)所要求的最早送達(dá)時(shí)間和最晚送達(dá)時(shí)間以及完全滿意的時(shí)間見表5。

表2　各生活處對各類物資產(chǎn)品的需求量

表3　各生活區(qū)之間的路程

假設(shè)：θ1=0.6，θ2=0.4，λ=0.2（h），經(jīng)初步預(yù)測后，每輛車承載2 000單位生活用水物資產(chǎn)品，700單位食物物資產(chǎn)品和320單位帳篷物資產(chǎn)品。

根據(jù)上述算法，可得出優(yōu)化結(jié)果：

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

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

表4　各生活區(qū)之間的路況系數(shù)

表5　各生活區(qū)要求最早、最晚送達(dá)時(shí)間及完全滿意時(shí)間

圖2　物資產(chǎn)品配送優(yōu)化路徑

4　結(jié)論

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

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

［2］陳雷雷，王海燕.大規(guī)模突發(fā)事件中基于滿意度的應(yīng)急物資優(yōu)化調(diào)度模型［J］.中國安全科學(xué)學(xué)報(bào)，2010，20（5）：46_52.

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

［4］張永領(lǐng).公眾洪災(zāi)應(yīng)急避險(xiǎn)模式和避險(xiǎn)體系研究［J］.自然災(zāi)害學(xué)報(bào)，2013（4）：95_104.

［5］張永領(lǐng).基于層次分析法的應(yīng)急物資儲備方式研究［J］.災(zāi)害學(xué)，2011（3）：120_125.

［6］田軍，馬文正，汪應(yīng)洛，等.應(yīng)急物資配送動(dòng)態(tài)調(diào)度的粒子群算法［J］.系統(tǒng)工程理論與實(shí)踐，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］徐志宇，彭嘉臻，許維勝.應(yīng)急物流的分批配送規(guī)劃及蟻群優(yōu)化求解［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47（24）：1_3，8.

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

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

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

［12］俞武揚(yáng).基于時(shí)間滿意度的應(yīng)急物資中轉(zhuǎn)運(yùn)輸模型［J］.系統(tǒng)管理學(xué)報(bào)，2013，22（6）：882_887.

［13］莫鴻強(qiáng)，李向陽，萬國成，等.加權(quán)編碼遺傳算法線性函數(shù)能力分析［J］.計(jì)算機(jī)工程與應(yīng)用，2007（8）：85_87.

［14］陳艷波，馬進(jìn)，陳茜.混合整數(shù)線性規(guī)劃形式的抗差狀態(tài)估計(jì)方法［J］.電力自動(dòng)化設(shè)備，2015，35（7）：26_31.

［15］金成，閔嘉寧.供應(yīng)鏈物流配送路徑優(yōu)化節(jié)約算法改進(jìn)研究［J］.制造業(yè)自動(dòng)化，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

國家自然科學(xué)基金項(xiàng)目資助（41401010）；江蘇省社會科學(xué)基金項(xiàng)目（13GLC011）

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