帶時間窗的甘肅應急物流配送路徑優化研究

尹耀杰 馬麗榮

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

關鍵詞：時間窗;應急物流;配送路徑;遺傳算法;甘肅省

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

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

一、問題的描述

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

二、構建帶時間窗的應急物流配送路徑模型

（一）模型參數與變量定義

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

di：需求點i的需求量;

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

k=■d■/μc+1

A：弧的集合;

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

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

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

si：表示受災點i的服務時間;

tij：表示從i點到j點的行駛時間;

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

ai：受災點i的左時間窗;

bi：受災點i的右時間窗;

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

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

Ck：車輛k最大裝載量;

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

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

（二）模型設計

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）

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

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

（一）算法設計

1. 編碼

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

2. 遺傳適應度函數

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

目標函數值越小越優越，因此在選擇環節，將懲罰函數的倒數設置為適應度函數，即為1/f（s）。

3. 初始化種群

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

設節點數目為m。

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

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

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

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

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

4. 選擇

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

5. 交叉

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

6. 變異

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

7. 終止條件

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

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

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

四、 算例分析

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

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

五、結語

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

參考文獻：

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

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

[3]陳湉，林勇.大數據背景下臺風災害應急物流車輛調度優化仿真[J].災害學，2019，34（01）：194-197.

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

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

[6]朱娜，鄭亞平.復雜物流網絡下的應急物資分配模型[J].數學的實踐與認識，2016，46（19）：133-140.

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

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

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

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

（作者單位：蘭州石化職業技術大學國際商務學院）