帶時間窗的甘肅應(yīng)急物流配送路徑優(yōu)化研究

尹耀杰 馬麗榮

摘要：文章對應(yīng)急物流配送路徑進行分析的基礎(chǔ)上，構(gòu)建了帶時間窗的應(yīng)急物流配送路徑最短優(yōu)化模型，提出了遺傳優(yōu)化算法，最后以漳縣公路網(wǎng)絡(luò)為算例進行分析，利用MATLAB軟件編程實現(xiàn)，算例結(jié)果表明，遺傳優(yōu)化算法更好地解決應(yīng)急物流配送問題，驗證了遺傳算法解決應(yīng)急物流配送路徑的可行性。

關(guān)鍵詞：時間窗;應(yīng)急物流;配送路徑;遺傳算法;甘肅省

自然災(zāi)害具有強大的破壞力，給人類帶來了巨大的財產(chǎn)損失和人員傷亡，經(jīng)常造成自然環(huán)境破壞，在不同程度上造成重大的經(jīng)濟損失和人們心理恐慌，為降低災(zāi)害造成的損傷，在短期內(nèi)災(zāi)區(qū)急需大量的救援物資，應(yīng)急物流開辟了為快速有效地開展救援工作同時提供滿足受災(zāi)群眾生活和醫(yī)療物資的需求，而應(yīng)急物流具有突發(fā)性和緊迫性等特點，為了提高應(yīng)急物資配送的及時性和有效性，要對應(yīng)急物流車輛配送路徑做出科學的決策。然而，由于災(zāi)情的不確定性和難以預(yù)測性以及救援的緊迫性使得應(yīng)急管理部門很難準確獲得受災(zāi)地區(qū)對應(yīng)急物資的需求量。同時，應(yīng)急車輛配送物資的過程中常常面臨路徑通行能力差、山體滑坡和道路塌陷損壞等風險，也影響應(yīng)急物資的精準送達。

如何以最短路徑、高滿意度、最低成本等為目標在最短的時間內(nèi)完成突發(fā)事件下應(yīng)急物資的配送問題，成為國內(nèi)外學者高度關(guān)注的問題。李志等研究了以物資分配公平性和需求效用最大化為目標，建立基于多目標的混合整數(shù)規(guī)劃方法應(yīng)急物資供應(yīng)點定位-分配模型;楊恩緣，李進等提出了以運輸成本最小為目標，結(jié)合容量限制及應(yīng)急配送的多樣性和多級性特點，構(gòu)建了應(yīng)急物資多級配送選址-路徑的混合整數(shù)規(guī)劃模型;陳湉，林勇提出基于離散蜂群的災(zāi)害應(yīng)急物流車輛調(diào)度優(yōu)化問題研究，以供應(yīng)過量、物資分配不足所造成的損失最小化、車輛調(diào)度成本最低為優(yōu)化目標，以服務(wù)時間窗和車輛運載能力為約束條件，構(gòu)建了應(yīng)急需求下的車輛調(diào)度優(yōu)化模型，并采用離散蜂群算法求解;張偉，楊斌等以運輸距離最短化、運輸時間最小化和路徑復(fù)雜性為目標，建立多目標應(yīng)急物流路徑規(guī)劃模型;蔣杰輝，馬良利用改進智能水滴算法求解應(yīng)急物資配送中車輛路徑優(yōu)化問題;朱娜，鄭亞平采用“矢量投影-理想點法”以車輛運載能力等為限制條件，以應(yīng)急運輸成本、應(yīng)急時間及救災(zāi)點數(shù)量為優(yōu)化目標構(gòu)建了應(yīng)急物資分配模型;朱佳翔等以運輸時間最少、成本最優(yōu)以及用戶滿意度最大等為目標，構(gòu)建多階段多目標應(yīng)急物流配送的灰色動態(tài)規(guī)劃模型。

一、問題的描述

帶時間窗的車輛運輸路徑問題（VRPTW）是應(yīng)急物流研究的基本問題，也是實現(xiàn)在有限時間內(nèi)實現(xiàn)物資的及時送達，提高救援效率，將災(zāi)害降到最小化的有效途徑。本文針對甘肅應(yīng)急物流運輸與配送問題，構(gòu)建了帶時間窗路徑最短為目標的車輛配送模型，設(shè)計遺傳算法對應(yīng)急物流配送路徑模型求解，兼顧考慮多個制約條件，如車輛載重量的限制，受災(zāi)點對物資需求時間窗的限制等。假設(shè)有一個配送中心對多個受災(zāi)點進行應(yīng)急物資配送，配送中心有容量不同的車輛，受災(zāi)點對物資需求的時間各不相同，要求在規(guī)定的時間內(nèi)完成配送任務(wù)，規(guī)劃配送路線并要求每條路線上只有一輛車配送，規(guī)定車輛從配送中心出發(fā)完成配送任務(wù)后再返回配送中心，使車輛配送車輛總運達的路徑最短，利用MATLAB軟件編程求解，計算出應(yīng)急物流最短配送路徑最優(yōu)解。

二、構(gòu)建帶時間窗的應(yīng)急物流配送路徑模型

（一）模型參數(shù)與變量定義

N={0，1，…，n，n+1}是節(jié)點集合，0，n+1表示配送中心，需求點編號為{1，…，n};

di：需求點i的需求量;

K={1，2，…，k}是車輛集合，為了降低配送成本盡可能合理使用配送車輛，采用下列公式確定車輛數(shù)：

k=■d■/μc+1

A：弧的集合;

xijk={0，1}，表示車輛k是否從i點出發(fā)前往j點，如果車輛k是從i點出發(fā)前往j點，則xijk=1，否則xijk=0;

Cij：表示i點和j點之間的距離;

Wik：表示車輛k對i點的開始服務(wù)時間;

si：表示受災(zāi)點i的服務(wù)時間;

tij：表示從i點到j(luò)點的行駛時間;

Mij：一個足夠大的數(shù)，可以取10的7次方;

ai：受災(zāi)點i的左時間窗;

bi：受災(zāi)點i的右時間窗;

E：配送中心的左時間窗;

L：配送中心的右時間窗;

Ck：車輛k最大裝載量;

s+（i）：表示從i點出發(fā)的弧的集合;

s-（i）：表示回到j(luò)點的弧的集合。

（二）模型設(shè)計

min■■cijxijk（1）

■■xijk=1 ？坌i∈N（2）

■x0jk=1 ？坌k∈K（3）

■xijk-■xjik=0 ？坌j∈N，？坌k∈K（4）

■xi，n+1，k=1 ？坌k∈K（5）

wik+si+tij-wjk≤（1-xijk）Mij，？坌k∈K，？坌（i，j）∈A（6）

ai（■xijk）≤wik≤bi（■xijk） ？坌k∈K，？坌i∈A（7）

E≤wik≤L，？坌k∈K，？坌i∈{0，n+1}（8）

■■xijk≤C ？坌k∈K（9）

xijk=10 ？坌k∈K，？坌（i，j）∈A（10）

其中目標函數(shù)（1）表示車輛最短應(yīng)急物流配送路徑;（2）～（10）是約束條件，（2）表示每個需求點只能被分配到一條配送路徑上;（3）表示每條配送線路上從配送中心出發(fā)只能前往一個需求點;（4）表示車輛k在路徑上的流量限制;（5）表示車輛配送完畢都必須返回配送中心;（6）表示配送時間連續(xù)性;（7）表示需求點時間窗約束;（8）表示配送中心時間窗約束;（9）表示載重量約束;（10）表示變量取值的約束。

三、基于遺傳算法（GA）的應(yīng)急物流配送路徑模型求解

（一）算法設(shè)計

1. 編碼

在使用GA求解VRPTW問題時，可以采用整數(shù)編碼的形式對染色體進行編碼，當配送車輛數(shù)最多為K， 且節(jié)點數(shù)目為N時，染色體長度為N+K-1，那么表達該染色體的基本形式為（1，2，3，…，N，N+1，…，N+K-1）。

2. 遺傳適應(yīng)度函數(shù)

當編碼的解碼不能保證都滿足每條配送路線上對時間窗的約束和載重量的約束條件時，為了解決違反約束問題，進行求解時采用懲罰函數(shù)。構(gòu)建的懲罰函數(shù)如下：f（s）=c（s）+αq（s）+βw（s），c（s）表示車輛總行駛距離，q（s）表示各條路徑違反的容量約束之和，w（s）表示所有顧客違反的時間窗約束之和。因為違反容量約束相對來說不太容易，所以將α設(shè)為10。而較容易違反時間窗約束，所以將β設(shè)為100。

目標函數(shù)值越小越優(yōu)越，因此在選擇環(huán)節(jié)，將懲罰函數(shù)的倒數(shù)設(shè)置為適應(yīng)度函數(shù)，即為1/f（s）。

3. 初始化種群

先構(gòu)建帶時間窗車輛路徑問題的初始解，再進行初始化種群。

設(shè)節(jié)點數(shù)目為m。

第一步：任意選擇某一節(jié)點i∈{1，2，3，…，m};

第二步：使用車輛數(shù)的初始化k=1;

第三步：遍歷節(jié)點生成序列Sq=[i，i+1，…，m，1，2，…，i-1]

第四步：遍歷節(jié)點j至節(jié)點m，形成初始解。按序列Sq遍歷節(jié)點Sq（j），將節(jié)點Sq（j）添加到第q條路徑中，在添加到對應(yīng)線路中時要考慮車輛的載重量和左時間窗的約束條件。

得到的初始解就是一個配送方案，通過將個體賦值的方式轉(zhuǎn)換為種群初始化。

4. 選擇

從群體中選擇優(yōu)良個體來繁殖子代的過程，并進行優(yōu)勝劣汰操作，通過基于適應(yīng)度的過程選擇個體解決方案，即從群體中選擇多個適應(yīng)度值大的個體進行交叉、變異以及局部搜索過程。

5. 交叉

交叉是指兩個父代個體的部分結(jié)構(gòu)加以替換重組而生成新的個體，然后從前到后把重復(fù)的基因位刪除，形成兩個子代個體。

6. 變異

變異過程是將父代染色體先選擇兩個位置，將這兩個位置上的基因互換形成子代染色體。

7. 終止條件

遺傳算法具有隨機搜索特性，需要設(shè)置終止條件以在可接受時間內(nèi)獲得最優(yōu)解。比如設(shè)置最大進化次數(shù)為終止條件，或達到最大迭代數(shù)時終止算法運算，再如判斷種群適應(yīng)度值的收斂性，種群適應(yīng)度值不被繼續(xù)優(yōu)化時終止算法運算。

（二）遺傳算法的運算流程

遺傳算法（GA）是借鑒生物界的進化論，適者生存，優(yōu)勝劣汰的遺傳機制演化而來，是一種隨機化搜索全局尋優(yōu)的生物進化過程算法，具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力，采用概率化的尋優(yōu)方法，能自動獲取和指導(dǎo)優(yōu)化的搜索空間，自適應(yīng)地調(diào)整搜索方向，使群體不斷進化，逐漸接近最優(yōu)。GA是解決VRPTW問題的有效方法之一，在求解應(yīng)急物流配送模型中得到了廣泛的應(yīng)用。其流程圖1所示。

四、 算例分析

以漳縣公路網(wǎng)絡(luò)應(yīng)急物流配送為算例進行分析，漳縣有13個鄉(xiāng)鎮(zhèn)，其分布狀況如圖1所示，假定武陽鎮(zhèn)是配送中心，配送中心有5輛載重量為68t的汽車，各鄉(xiāng)鎮(zhèn)對物資的需求量由各鄉(xiāng)鎮(zhèn)的人數(shù)來確定，需求點相關(guān)信息見表1。

本算例采用MATLAB軟件對設(shè)計的GA算法進行編程實現(xiàn)，通過仿真運算結(jié)果發(fā)現(xiàn)，在求解配送路徑優(yōu)化問題時，帶時間窗的遺傳算法收斂速度快、程序運行時間短、效率高，有效實現(xiàn)了時間約束條件下應(yīng)急物流配送路徑優(yōu)化，在應(yīng)急物資配送中調(diào)用了3輛汽車，具體的最優(yōu)配送方案如圖2所示，車輛行駛路徑及載重量如表2所示。通過求解軌跡結(jié)果可以得出基于時間窗的總行駛里程最短的路徑安排。

五、結(jié)語

本文針對配送中心如何向災(zāi)區(qū)配送應(yīng)急物資這一問題，提出了一個基于時間窗的遺傳算法的應(yīng)急物流車輛配送路徑優(yōu)化方案，考慮應(yīng)急物流的時間約束性，構(gòu)建了以配送路徑最短為目標，滿足多個約束條件下優(yōu)化問題模型，結(jié)合模型特點使用遺傳算法進行求解，找到目標函數(shù)最小時對應(yīng)的應(yīng)急物流配送路徑。研究結(jié)果表明，遺傳算法能有效解決應(yīng)急物流配送路徑問題。本文假定只考慮一個配送中心的情況下車輛配送路徑優(yōu)化，實際上，應(yīng)急物流錯綜復(fù)雜，如應(yīng)急物資有帳篷、衣物、食品、藥品等性質(zhì)不同的物資，配送要求不同，再如多配送中心問題研究、應(yīng)急道路狀況等，針對復(fù)雜情況下對應(yīng)急物資配送規(guī)劃是未來研究的重點難點。

參考文獻：

[1]李志，焦琴琴，周愉峰.震后應(yīng)急物資供應(yīng)點的多目標動態(tài)定位-分配模型[J].計算機工程，2017，43（06）：281-288.

[2]楊恩緣，李進，嚴翌嫻，黃文耀.震后多品種應(yīng)急物資多級配送中的選址-路徑模型[J].災(zāi)害學，2016，31（02）：200-205.

[3]陳湉，林勇.大數(shù)據(jù)背景下臺風災(zāi)害應(yīng)急物流車輛調(diào)度優(yōu)化仿真[J].災(zāi)害學，2019，34（01）：194-197.

[4]張偉，楊斌，朱小林.多目標應(yīng)急物流路徑選擇研究[J].江蘇科技大學學報（自然科學版），2017，31（02）：219-224.

[5]蔣杰輝，馬良.多目標應(yīng)急物資路徑優(yōu)化及其改進智能水滴算法[J].計算機應(yīng)用研究，2016，33（12）：3602-3605.

[6]朱娜，鄭亞平.復(fù)雜物流網(wǎng)絡(luò)下的應(yīng)急物資分配模型[J].數(shù)學的實踐與認識，2016，46（19）：133-140.

[7]朱佳翔，譚清美，蔡建飛.基于雙重不確定性的應(yīng)急物流配送策略[J].系統(tǒng)工程， 2016，34（03）：1-7.

[8]李洋，陸娟.物流運籌學[M].北京：科學出版社，2017.

[9]余勝威.MATLAB優(yōu)化算法案例分析與應(yīng)用[M].北京：清華大學出版社，2014（09）：227-261.

*基金項目：甘肅省社科規(guī)劃項目“基于群智能算法的甘肅省應(yīng)急物流配送中心選址及路徑優(yōu)化研究”（編號：20YB114）;甘肅省科技廳軟科學項目“基于多目標的甘肅省應(yīng)急物流配送路徑優(yōu)化問題研究”（編號：20CX9ZA023）。

（作者單位：蘭州石化職業(yè)技術(shù)大學國際商務(wù)學院）