尹耀杰 馬麗榮

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

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

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

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

一、問題的描述

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

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

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

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

di：需求點(diǎn)i的需求量;

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

k=■d■/μc+1

A：弧的集合;

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

Cij：表示i點(diǎn)和j點(diǎn)之間的距離;

Wik：表示車輛k對(duì)i點(diǎn)的開始服務(wù)時(shí)間;

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

tij：表示從i點(diǎn)到j(luò)點(diǎn)的行駛時(shí)間;

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

ai：受災(zāi)點(diǎn)i的左時(shí)間窗;

bi：受災(zāi)點(diǎn)i的右時(shí)間窗;

E：配送中心的左時(shí)間窗;

L：配送中心的右時(shí)間窗;

Ck：車輛k最大裝載量;

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

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

（二）模型設(shè)計(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）

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

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

（一）算法設(shè)計(jì)

1. 編碼

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

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

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

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

3. 初始化種群

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

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

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

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

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

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

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

4. 選擇

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

5. 交叉

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

6. 變異

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

7. 終止條件

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

（二）遺傳算法的運(yùn)算流程

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

四、 算例分析

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

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

五、結(jié)語

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

[8]李洋，陸娟.物流運(yùn)籌學(xué)[M].北京：科學(xué)出版社，2017.

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

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

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