李卓 李引珍 李文霞

摘 要：針對(duì)應(yīng)急前期運(yùn)輸商自有車(chē)輛不足的實(shí)際背景，采用自有車(chē)輛和第三方租用車(chē)輛共同配送的運(yùn)輸模式，對(duì)混合車(chē)輛路徑的組合優(yōu)化問(wèn)題進(jìn)行研究。首先，考慮需求點(diǎn)和運(yùn)輸商的不同利益訴求，以系統(tǒng)滿(mǎn)意度最大、系統(tǒng)配送時(shí)間和總成本最小為優(yōu)化目標(biāo)，建立帶軟時(shí)間窗的多目標(biāo)混合車(chē)輛路徑優(yōu)化模型。其次，考慮NSGA-Ⅱ算法在求解該類(lèi)問(wèn)題時(shí)收斂性差和Pareto前沿分布不均勻的缺點(diǎn)，將蟻群算法的啟發(fā)式策略和信息素正反饋機(jī)制用于生成子代種群，非支配排序策略模型用于指導(dǎo)算法的多目標(biāo)擇優(yōu)過(guò)程，并引入變鄰域下降搜索以擴(kuò)大搜索空間，提出求解多目標(biāo)的非支配排序蟻群算法以突破原有算法瓶頸。算例表明：構(gòu)建的模型可對(duì)決策者在不同的情境下依據(jù)不同的優(yōu)化目標(biāo)選擇合理的路徑提供參考，提出的算法在求解不同規(guī)模的問(wèn)題和不同分布類(lèi)型的問(wèn)題中均表現(xiàn)出較好的性能。

關(guān)鍵詞：應(yīng)急物流;混合車(chē)輛路徑問(wèn)題;多準(zhǔn)則優(yōu)化;非支配排序策略;蟻群算法;變鄰域搜索

中圖分類(lèi)號(hào)：TP301.6

文獻(xiàn)標(biāo)志碼：A

Multi-objective optimization model and solution algorithm for emergency material transportation path

LI Zhuo， LI Yinzhen*， LI Wenxia

School of Traffic and Transportation，? Lanzhou Jiaotong University， Lanzhou Gansu 730070， China

Abstract：

For the actual background of the shortage of self-owned vehicles of the transporters in the early stage of emergency， the combinatorial optimization problem of hybrid vehicle paths with transportation mode of joint distribution of self-owned vehicles and? vehicles rented by third-party was studied. Firstly， with the different interests between demand points and transporters considered， a multi-objective hybrid vehicle routing optimization model with soft time windows was established with the goal of maximizing system satisfaction and minimizing system delivery time and total cost. Secondly， the shortcomings of NSGA-Ⅱ algorithm in solving this kind of problems such as poor convergence and uneven distribution of Pareto frontiers were considered， the heuristic strategy and pheromone positive feedback mechanism of ant colony algorithm were used to generate offspring population， non-dominated sorting strategy model was used to guide the multi-objective optimization process， and the variable neighborhood descent search was introduced to expand the search space. A multi-objective non-dominated sorting ant colony algorithm was proposed to break through the bottleneck of the original algorithm. The example shows that the proposed model can provide reference for decision makers to choose reasonable paths according to different optimization objectives in different situations， and the proposed algorithm shows better performance in solving different scale problems and different distribution type problems.

Key words：

emergency logistics; heterogeneous vehicle routing problem; multi-criteria optimization; non-dominated sorting strategy; ant colony algorithm; variable neighborhood search

0 引言

隨著全球自然環(huán)境的急劇變化，一系列突發(fā)事件給社會(huì)穩(wěn)定和安全帶來(lái)嚴(yán)重威脅，然而國(guó)內(nèi)由于應(yīng)急物流體系不夠完善，造成的損失占其總損失的15%～20%[1]。因此，建立完善的應(yīng)急系統(tǒng)已成為熱點(diǎn)議題，對(duì)緩解災(zāi)情、降低損失具有重要意義。

應(yīng)急物流體系是一個(gè)多階段、多層次結(jié)構(gòu)的供應(yīng)網(wǎng)絡(luò)。針對(duì)末端配送的車(chē)輛路徑問(wèn)題（Vehicle Routing Problem， VRP），國(guó)內(nèi)外學(xué)者展開(kāi)了廣泛研究[2-4]。關(guān)于單目標(biāo)的應(yīng)急VRP問(wèn)題，郭詠梅等[5]考慮路網(wǎng)通行能力和物資優(yōu)先級(jí)，以系統(tǒng)響應(yīng)能力最大為目標(biāo)構(gòu)建開(kāi)放式車(chē)輛路徑問(wèn)題（Open Vehicle Routing Problem， OVRP）數(shù)學(xué)模型，并設(shè)計(jì)改進(jìn)蟻群算法進(jìn)行求解。程碧榮等[6]針對(duì)物資供應(yīng)不足及需求不確定的特點(diǎn)，提出隨機(jī)需求環(huán)境下的應(yīng)急路徑優(yōu)化方法。Wohlgemuth等[7]最小化時(shí)間延誤并提高車(chē)輛利用率，建立了確定性需求下的動(dòng)態(tài)車(chē)輛路徑優(yōu)化模型。關(guān)于多目標(biāo)的應(yīng)急VRP問(wèn)題，多數(shù)文獻(xiàn)通?？紤]時(shí)效性和經(jīng)濟(jì)性[8-9]。近年來(lái)，隨著研究的深入，部分學(xué)者兼顧考慮需求點(diǎn)的需求滿(mǎn)足率和救援公平性等，如Chang等[10]提出最小化交付時(shí)間、運(yùn)輸成本和需求不滿(mǎn)足率的三目標(biāo)優(yōu)化模型，并針對(duì)該問(wèn)題設(shè)計(jì)基于貪婪搜索的多目標(biāo)遺傳算法。Zhang等[11]最大限度降低需求未滿(mǎn)足程度、總交付時(shí)間和配送的不平衡性，提出多目標(biāo)、多周期的應(yīng)急物流優(yōu)化方法。由于VRP問(wèn)題的NP-hard性質(zhì)，精確算法無(wú)法避免指數(shù)爆炸問(wèn)題，難以求解大規(guī)模問(wèn)題[12]，而遺傳算法、蟻群算法、禁忌搜索算法等啟發(fā)式算法在解決該類(lèi)問(wèn)題中表現(xiàn)出良好的求解效果[13-15]，但在求解精度和收斂性等方面仍有待提高，為此，已有學(xué)者考慮對(duì)算法進(jìn)行改進(jìn)[16-17]。綜上所述，既有研究中大多數(shù)文獻(xiàn)針對(duì)的實(shí)際背景問(wèn)題較為單一，采用多目標(biāo)優(yōu)化模型且設(shè)計(jì)更有效的求解算法的文獻(xiàn)比較少見(jiàn)。

在實(shí)際救援中，由于突發(fā)事件的隨機(jī)發(fā)生，造成救援初期可調(diào)度的應(yīng)急設(shè)施往往不能應(yīng)付繁重的救援工作，尤其是面對(duì)大規(guī)模、多災(zāi)點(diǎn)的應(yīng)急物資運(yùn)輸任務(wù)，運(yùn)輸車(chē)保有量不足使得可調(diào)度的車(chē)輛有限，必然會(huì)降低救援效率，造成額外的經(jīng)濟(jì)損失和人員傷亡。為此，本文考慮應(yīng)急前期自有車(chē)輛不足的一類(lèi)實(shí)際情況，提出自有車(chē)輛和租用車(chē)輛相結(jié)合的配送模式，即混合車(chē)輛路徑問(wèn)題?；旌闲愿拍钌婕败?chē)輛所有權(quán)，即應(yīng)急初期配送車(chē)輛數(shù)不足時(shí)，必須從第三方承運(yùn)人租用車(chē)輛完成配送?；诖?，考慮災(zāi)點(diǎn)系統(tǒng)滿(mǎn)意度、運(yùn)輸總成本和系統(tǒng)配送時(shí)間建立多目標(biāo)應(yīng)急路徑優(yōu)化模型，并針對(duì)該問(wèn)題設(shè)計(jì)求解多目標(biāo)的非支配排序蟻群算法。

1 多目標(biāo)優(yōu)化模型

1.1 問(wèn)題描述

某些突發(fā)事件波及范圍較大，且末端物資運(yùn)輸工作具有時(shí)間的緊迫性和面向多災(zāi)點(diǎn)的復(fù)雜性，導(dǎo)致運(yùn)輸商自有車(chē)輛不足，需要租借車(chē)輛繼續(xù)完成配送任務(wù)?？紤]車(chē)輛的所有權(quán)，自有車(chē)輛完成配送任務(wù)后需返回調(diào)度中心，是閉環(huán)VRP;租用車(chē)輛完成配送任務(wù)后停留在最后一個(gè)任務(wù)點(diǎn)，不需返回調(diào)度中心，是開(kāi)環(huán)VRP。基于此，該問(wèn)題可歸結(jié)為帶軟時(shí)間窗的混合車(chē)輛路徑問(wèn)題（Heterogeneous Vehicle Routing Problem with Soft Time Windows， HVRPSTW），如圖1所示。本文以此為背景，從實(shí)際角度出發(fā)，解決應(yīng)急條件下兼顧多個(gè)優(yōu)化方面的運(yùn)輸路徑選擇問(wèn)題，設(shè)計(jì)建立多目標(biāo)優(yōu)化數(shù)學(xué)模型。

1.2 模型參數(shù)及變量

完全有向的應(yīng)急物流運(yùn)輸網(wǎng)絡(luò)為G=（V，E），其他參數(shù)及相關(guān)變量見(jiàn)表1。

1.3 HVRPSTW模型建立

災(zāi)后需求點(diǎn)對(duì)時(shí)效性的要求較高，在盡可能滿(mǎn)足需求點(diǎn)時(shí)間窗限制的前提下，隨著交付時(shí)間的延遲，滿(mǎn)意度逐漸降低，滿(mǎn)意度按下式計(jì)算：

wki=（li-tki）/li， 0≤tki≤li

0，tki>li（1）

考慮取所有需求點(diǎn)滿(mǎn)意度的平均值為系統(tǒng)滿(mǎn)意度S：

S=1n-1∑i∈V0∑k∈Kykiwki（2）

為了加快設(shè)備周轉(zhuǎn)速度，運(yùn)輸企業(yè)需要考慮系統(tǒng)配送時(shí)間，這里，首先定義第k類(lèi)車(chē)第mk輛車(chē)完成若干需求點(diǎn)配送任務(wù)所花費(fèi)的時(shí)間Tmk：

Tmk=∑i∈V∑j∈Vxkijtkij+∑i∈V0ykiui-∑i∈V0xbi0tbi0; k∈K（3）

完成所有需求點(diǎn)配送任務(wù)的系統(tǒng)配送時(shí)間T為：

T=max{Tmkk∈K}（4）

此外，還要考慮經(jīng)濟(jì)性，總配送費(fèi)用為：

C=∑i∈V∑j∈V∑k∈Kxkijfij+∑j∈V0∑k∈Kxk0jfrk-∑i∈V0xbi0fi0+∑i∈V0∑k∈Kykipi（tki）（5）

其中：pi（tki）=r·max{（tki-li），0}為超出時(shí)間窗限制的懲罰成本函數(shù)。

表格（有表名）

表1 模型變量參數(shù)定義

Tab. 1 Variables and parameters definition of model

類(lèi)型符號(hào)含義

集合參數(shù)變量

V節(jié)點(diǎn)集合，V={1，2，…，n}，調(diào)度中心為1

V0需求點(diǎn)集合，V0=V/{1}

E節(jié)點(diǎn)間有向弧段集合E={（i， j）：i， j∈V，i≠j}

A需求點(diǎn)的任意子集，AV0

K車(chē)輛類(lèi)別集合，K={k|a，b}，k=a為自有車(chē)，k=b為租用車(chē)

mkk類(lèi)車(chē)輛集合，mk={1，2，…，n}

vkk類(lèi)車(chē)平均速度

Qkk類(lèi)車(chē)載重

qi需求點(diǎn)i的物資需求量

ui需求點(diǎn)i的服務(wù)持續(xù)時(shí)間

tu單位需求量的服務(wù)時(shí)間

diji≠j∈V間路徑（i， j）∈E的長(zhǎng)度

fij路徑dij的行駛成本

frkk類(lèi)車(chē)固定啟用成本

tkijk類(lèi)車(chē)在路徑dij的行駛時(shí)間

li需求點(diǎn)i時(shí)間窗上界

c路徑dij的單位行駛成本

r超出時(shí)間窗l(fā)i限制單位時(shí)間懲罰成本

M控制參數(shù)，極大整數(shù)

tkik類(lèi)車(chē)到達(dá)需求點(diǎn)的時(shí)間，tk 0=0

xkij決策變量，當(dāng)k類(lèi)車(chē)負(fù)責(zé)路徑（i， j）∈E時(shí)取值為1;否則為0

yki決策變量，當(dāng)k類(lèi)車(chē)服務(wù)需求點(diǎn)i∈V0時(shí)取值為1;否則為0

考慮運(yùn)輸過(guò)程的復(fù)雜性，兼顧多個(gè)優(yōu)化方面，建立多目標(biāo)路徑優(yōu)化模型：

Z=（FS（y），F(xiàn)T（x，y），F(xiàn)C（x，y））（6）

FS（y）=max S（7）

FT（x，y）=min T（8）

FC（x，y）=min C（9）

s.t. ∑j∈V∑k∈Kxkij=∑j∈V∑k∈Kxkji=1; i∈V（10）

∑i∈V∑j∈Vxkij≤A-1; k∈K，A≥2（11）

∑j∈V0xk0j=∑j∈V0xkj0≤mk; k∈K（12）

∑i∈Vxkih-∑j∈Vxkhj=0; k∈K，h∈V0（13）

∑i∈V0ykiqi≤Qk; k∈K（14）

tki+ui+tkij≤tkj+M（1-xkij）; i， j∈V0，k∈K（15）

tkij=dij/vk

fij=c·dij

ui=tu·qi ;i， j∈V， k∈K（16）

xkij，yki∈{0，1}; i， j∈V，k∈K（17）

Qk，qi，ui>0; i∈V0，k∈K（18）

模型中，式（6）～（9）為多運(yùn)輸準(zhǔn)則的不同優(yōu)化目標(biāo);式（10）保證每個(gè)需求點(diǎn)僅被一輛車(chē)服務(wù)且僅服務(wù)一次;式（11）為子回路消除約束;式（12）保證車(chē)輛從調(diào)度中心出發(fā)最后返回調(diào)度中心，且啟用車(chē)輛數(shù)小于車(chē)輛擁有數(shù);式（13）為節(jié)點(diǎn)平衡方程;式（14）為車(chē)輛載重約束;式（15）為配送過(guò)程中各需求點(diǎn)的時(shí)間限制條件;式（16）～（18）為決策變量和參數(shù)約束。

2 求解算法設(shè)計(jì)

HVRPSTW是VRP問(wèn)題的變體之一，啟發(fā)式算法是解決該類(lèi)問(wèn)題的有效方法之一。蟻群優(yōu)化（Ant Colony Optimization， ACO）算法在求解VRP及其變體中得到了成功的應(yīng)用，在求解大規(guī)模問(wèn)題中表現(xiàn)出較好的收斂性[18];改進(jìn)非支配排序遺傳算法（Non-dominated Sorting Genetic Algorithm-Ⅱ， NSGA-Ⅱ）作為常用的多目標(biāo)求解算法，比同類(lèi)算法表現(xiàn)出更優(yōu)的性能[19]。考慮上述兩種算法的優(yōu)勢(shì)，首先以ACO算法為基本架構(gòu)，非支配排序策略用于多目標(biāo)擇優(yōu)過(guò)程;其次，為了避免算法在迭代后期陷入信息素停滯，采用變鄰域下降搜索機(jī)制，進(jìn)一步擴(kuò)大搜索的解空間。設(shè)計(jì)求解多目標(biāo)的非支配排序蟻群優(yōu)化算法（Non-dominated Sorting-Ant Colony Optimization algorithm， NSACO）。

2.1 求解多目標(biāo)的NSACO算法

2.1.1 非支配排序策略模型

模型包括兩個(gè)子過(guò)程：非支配排序和擁擠度評(píng)估。非支配排序是對(duì)種群進(jìn)行非支配前沿劃分，保證相同排序?qū)蛹?jí)個(gè)體之間不存在支配關(guān)系;擁擠度是同一排序?qū)觽€(gè)體周?chē)膫€(gè)體密度，確保種群多樣性。

構(gòu)建初始種群P，計(jì)算適應(yīng)度值并基于Pareto占優(yōu)對(duì)P分層排序?yàn)閗層子集，即P={P1，P2，…，Pk}，Pi+1中個(gè)體受Pi中個(gè)體支配，且Pi∩Pi+1=，i，i+1∈{1，2，…，k}，得到種群個(gè)體間的非支配關(guān)系。對(duì)于個(gè)體p∈P初始化兩個(gè)參數(shù)np和sp，np記錄支配個(gè)體p的個(gè)體數(shù)量，sp存放被個(gè)體p支配的個(gè)體的集合。執(zhí)行以上非支配排序過(guò)程后，計(jì)算每個(gè)排序?qū)覲i中個(gè)體p的擁擠程度I（p），p∈Pi，擁擠度I是相同排序?qū)又邢噜弬€(gè)體適應(yīng)度f(wàn)h（x）的距離差值。

執(zhí)行以上兩個(gè)子過(guò)程后，種群P中個(gè)體p被賦予非支配排序?qū)蛹?jí)prank和擁擠度I（p），通過(guò)以上兩個(gè)屬性區(qū)分個(gè)體間的優(yōu)劣關(guān)系：滿(mǎn)足①prankI（q）;則個(gè)體p優(yōu)于q。

2.1.2 變鄰域下降搜索

在經(jīng)過(guò)規(guī)定的迭代次數(shù)后，解的質(zhì)量仍然沒(méi)有改善，則啟

用變鄰域下降搜索。該過(guò)程采用多個(gè)不同鄰域進(jìn)行系統(tǒng)搜索，首先采用小鄰域結(jié)構(gòu)，當(dāng)解沒(méi)有改進(jìn)時(shí)，再切換較大的鄰域結(jié)構(gòu)。變鄰域下降搜索偽代碼如下。

程序前

for each p∈parent_set

Select a neighbourhood structure VLSi， i=1，2，…，imax

i → 1//初始化鄰域結(jié)構(gòu)VLS1

While i ≠ imax+1

VLSi（p）→p′//對(duì)p執(zhí)行鄰域結(jié)構(gòu)VLSi

If p′ unfeasible

repair p′//修復(fù)不可行解

If （f（p′）

p′ → p， i → 1//更新當(dāng)前可行解

else

i=i+1

end

If（f（p）

p→p*//更新全局最優(yōu)解

end

程序后

本文采用4個(gè)鄰域結(jié)構(gòu)（VNS={VNS1，VNS2，…，VNS4}）的搜索機(jī)制;兩個(gè)子路徑內(nèi)鄰域結(jié)構(gòu)，兩個(gè)子路徑間鄰域結(jié)構(gòu)具體如下：

子路徑內(nèi)relocate算子（VNS1）：隨機(jī)選取路徑1-11-5-1-6-2-4-7-3-1-16-14-8-1中一條子路徑1-6-2-4-7-3-1，對(duì)子路徑隨機(jī)生成移出節(jié)點(diǎn)note1和插入節(jié)點(diǎn)note2，將note1位置對(duì)應(yīng)的元素插入到note2位置，如圖2。

子路徑內(nèi)or-opt算子（VNS2）：隨機(jī)選取路徑1-11-5-1-6-2-4-7-3-1-16-14-8-1中一條子路徑1-6-2-4-7-3-1，對(duì)子路徑隨機(jī)選擇兩個(gè)移出節(jié)點(diǎn)note1、note2間的路徑序列sq，隨機(jī)選擇一個(gè)插入節(jié)點(diǎn)note3，sq從原位置移出，插入到新的位置，如圖3。

子路徑間relocate算子（VNS3）：針對(duì)一條路徑1-6-2-4-1-7-3-8-10-1，隨機(jī)生成移出節(jié)點(diǎn)note1和插入節(jié)點(diǎn)note2，將note1位置對(duì)應(yīng)的元素插入到note2位置，如圖4。

子路徑間or-opt算子（VNS4）：針對(duì)一條路徑1-6-2-4-1-7-3-8-10-1，隨機(jī)選擇兩個(gè)移出節(jié)點(diǎn)note1、note2間的路徑序列sq，隨機(jī)選擇一個(gè)插入節(jié)點(diǎn)note3，sq從原位置移出，插入到新的位置，如圖5。

要注意的是，執(zhí)行子路徑內(nèi)的鄰域結(jié)構(gòu)不會(huì)破壞解的可行性，執(zhí)行子路徑間的鄰域結(jié)構(gòu)有可能會(huì)破壞解的可行性，即有可能會(huì)違背車(chē)輛容量約束，因此，需要檢查所得解是否可行，若不滿(mǎn)足可行性，對(duì)解進(jìn)行修復(fù)。

2.1.3 算法流程

算法迭代過(guò)程中，通過(guò)蟻群算法中的路徑啟發(fā)式信息和路徑信息素濃度反饋機(jī)制生成子代種群Pc，與父代種群Pp相結(jié)合生成本次迭代的種群集合P;對(duì)P執(zhí)行非支配排序并評(píng)估擁擠度，基于個(gè)體排序?qū)觬ank和擁擠度I執(zhí)行精英保留策略，得到下一迭代的父代種群Pp;基于Pp進(jìn)行路徑信息素濃度更新，為產(chǎn)生下一子代做準(zhǔn)備;當(dāng)執(zhí)行指定迭代次數(shù)后，所得可行解沒(méi)有改進(jìn)，則執(zhí)行變鄰域下降搜索擴(kuò)大搜索解空間，以期改善解的多樣性。不斷循環(huán)以上過(guò)程，直到滿(mǎn)足算法停止條件，算法流程如圖6所示。

2.1.4 算法主要環(huán)節(jié)

1）初始化可行解。車(chē)輛路徑采用自然數(shù)編碼，以距離當(dāng)前需求點(diǎn)里程最小為元啟發(fā)式策略，從未訪(fǎng)問(wèn)點(diǎn)集合中搜索下一要訪(fǎng)問(wèn)的需求點(diǎn)，采用基于貪心策略的調(diào)度中心插入方法，若車(chē)輛當(dāng)前載重與下一將要訪(fǎng)問(wèn)需求點(diǎn)的需求量之和違背車(chē)輛載重約束，則將調(diào)度中心編號(hào)插入，表明需要另一輛車(chē)完成后續(xù)配送任務(wù)，以此生成質(zhì)量較高的初始解集P0。

2）生成父代?；赑areto占優(yōu)執(zhí)行非支配排序策略模型，給種群P中每個(gè)個(gè)體p賦予排序?qū)觩rank和擁擠度I（p）兩個(gè)屬性，用于執(zhí)行精英保留策略，通過(guò)擇優(yōu)產(chǎn)生下一代的父代種群。

3）全局信息素更新?？紤]多目標(biāo)的不同量綱對(duì)信息素濃度更新結(jié)果的影響，對(duì)父代個(gè)體的每個(gè)適應(yīng)度值進(jìn)行無(wú)量綱化處理后，路徑（i， j）的信息素濃度更新規(guī)則為：

τij（t+1）=（1-ρ）τij（t）+∑Hh=1Δτhij（19）

Δτhij=Q/fh（p）， （i， j）∈p

0，（i， j）p（20）

其中：H為目標(biāo)數(shù); fh（p）為個(gè)體p第h個(gè)目標(biāo)無(wú)量綱化后的適應(yīng)度值。

4）生成子代。依據(jù)路徑（i， j）的啟發(fā)式信息ηij和信息素濃度τij計(jì)算未訪(fǎng)問(wèn)需求點(diǎn)的轉(zhuǎn)移概率Psij，輪盤(pán)賭選擇確定下一訪(fǎng)問(wèn)點(diǎn)，同時(shí)保證滿(mǎn)足車(chē)輛載重約束。采用同樣的方式依次生成子代種群所有個(gè)體。路徑（i， j）的選擇概率為：

Psi， j（t）=τij（t）α·ηij（t）β∑k∈Asτik（t）α·ηik（t）β， j∈Ak

0，jAk（21）

3 數(shù)值實(shí)驗(yàn)及分析

3.1 基礎(chǔ)算例實(shí)驗(yàn)

隨機(jī)生成20個(gè)節(jié)點(diǎn)，包含1個(gè)應(yīng)急調(diào)度中心和19個(gè)物資需求點(diǎn)。本算例設(shè)置節(jié)點(diǎn)1為調(diào)度中心，其他各需求點(diǎn)的需求量（噸）是區(qū)間[0，10]均勻分布的隨機(jī)整數(shù)，需求點(diǎn)時(shí)間窗（min）在區(qū)間[0，60]中隨機(jī)產(chǎn)生，違背時(shí)間窗單位懲罰成本為4元/min，需求點(diǎn)的服務(wù)持續(xù)時(shí)間為2min/t;運(yùn)輸商擁有2輛載重為25t的自有車(chē)，行駛速度v1=1.2km/min，啟用成本為每輛300元;租用車(chē)載重為15t，車(chē)輛數(shù)充足，行駛速度v2=1.5km/min，啟用成本為每輛200元/輛;配送過(guò)程中單位運(yùn)輸成本為5元/km;具體見(jiàn)表2。

采用本文提出的NSACO算法對(duì)算例進(jìn)行200次迭代求解。設(shè)置種群規(guī)模pop=50，最大迭代次數(shù)gen=200，允許可行解沒(méi)有改進(jìn)的最大迭代次數(shù)noimpro=10;蟻群優(yōu)化參數(shù)參考文獻(xiàn)[18]進(jìn)行設(shè)置，α=1， β=5， ρ=0.2;算法在一臺(tái)搭載1.6GHz的Intel Core i5處理器和4GB內(nèi)存的計(jì)算機(jī)平臺(tái)上實(shí)現(xiàn)。各目標(biāo)最優(yōu)時(shí)的車(chē)輛路徑如圖7所示，各目標(biāo)最優(yōu)時(shí)的非支配路徑集合和路徑屬性見(jiàn)表3。

運(yùn)輸商和需求點(diǎn)對(duì)應(yīng)急物資運(yùn)輸路徑的要求不同，相應(yīng)的優(yōu)化目標(biāo)并不統(tǒng)一，使各目標(biāo)同時(shí)達(dá)到最優(yōu)的解不存在。由表3和圖7可知：當(dāng)FC（x，y）取最優(yōu)時(shí)，車(chē)輛組合為2a+2b，平均滿(mǎn)載率為81.00%，配送路徑如圖7（a），F(xiàn)T（x，y）比F*T（x，y）增加15.42%，F(xiàn)S（y）比F*S（y）降低17.53%;當(dāng)FT（x，y）取最優(yōu)時(shí)，車(chē)輛組合為2a+2b，平均滿(mǎn)載率為83.67%，配送路徑如圖7（b），F(xiàn)C（x，y）比F*（x，y）增加9.51%，F(xiàn)S（y）比F*S（y）降低16.96%;當(dāng)FS（y）取最優(yōu)時(shí)，車(chē)輛組合為2a+2b，平均滿(mǎn)載率為82.33%，配送路徑如圖7（c），F(xiàn)C（x，y）比F*C（x，y）增加29.82%，F(xiàn)T（x，y）比F*T（x，y）增加53.71%。從企業(yè)角度考慮，需提高效益，加快設(shè)備周轉(zhuǎn)，為此，合理規(guī)劃路徑的同時(shí)，減少啟用車(chē)輛數(shù)，提高車(chē)輛滿(mǎn)載率，以期降低成本、減少系統(tǒng)配送時(shí)間;從需求點(diǎn)角度考慮，在盡量控制成本的基礎(chǔ)上，科學(xué)安排配送順序，以期滿(mǎn)足物資能盡早送達(dá)的要求?；谝陨戏治?，在不同的實(shí)際情境下，決策者可根據(jù)不同目標(biāo)偏好選擇配送路線(xiàn);若在不同目標(biāo)之間適當(dāng)妥協(xié)，則即能避免部分目標(biāo)取較劣值，又可兼顧多個(gè)方面。

3.2 算法性能分析

3.2.1 基礎(chǔ)算例分析

NSGA-Ⅱ算法作為較為廣泛應(yīng)用的多目標(biāo)求解算法，吸引了大批學(xué)者的關(guān)注，近幾年來(lái)，已有不少針對(duì)該算法的改進(jìn)算法，因此，本文擬將NSACO算法與Hassanzadeh等[20]于2017年提出的VNSGA-Ⅱ進(jìn)行比較。以基礎(chǔ)算例為實(shí)驗(yàn)數(shù)據(jù)，設(shè)置交叉概率為0.9，變異概率為0.1，其他實(shí)驗(yàn)條件及參數(shù)相同，NSACO與VNSGA-Ⅱ分別執(zhí)行10次算法程序，對(duì)二者計(jì)算結(jié)果進(jìn)行分析。為了便于比較，取系統(tǒng)滿(mǎn)意度的相反數(shù)統(tǒng)一各目標(biāo)優(yōu)化方向，生成的Pareto前沿空間分布見(jiàn)圖8，算法性能統(tǒng)計(jì)見(jiàn)表4。

比較圖8（a）和圖8（b）看出，NSACO算法得到的Pareto前沿中，Pareto最優(yōu)解的數(shù)量更多，重復(fù)數(shù)據(jù)點(diǎn)較少，Pareto前沿跨度更廣且空間分布均勻性更好，說(shuō)明算法具有較強(qiáng)的搜索性能，可以搜索更大的解空間。由表4可知，NSACO在算法性能上總體比VNSGA-Ⅱ更好。具體從以下三個(gè)方面分析：求解精度上，盡管NSACO求得的總成本在最優(yōu)解和平均解上分別比VNSGA-Ⅱ大0.48%和0.35%，但NSACO求得系統(tǒng)配送時(shí)間和系統(tǒng)滿(mǎn)意度均比VNSGA-Ⅱ更優(yōu)，系統(tǒng)配送時(shí)間的最優(yōu)解和平均解分別優(yōu)化了3.00%和4.51%，系統(tǒng)滿(mǎn)意度的最優(yōu)解和平均解分別優(yōu)化了8.30%和7.42%。收斂性上，由于ACO算法的信息素正反饋機(jī)制，相較于VNSGA-Ⅱ的隨機(jī)搜索，NSACO在三個(gè)目標(biāo)上分別提前了56、34、27個(gè)迭代循環(huán)，收斂性明顯優(yōu)于VNSGA-Ⅱ。算法穩(wěn)健性上，在三個(gè)優(yōu)化目標(biāo)上，NSACO的平均偏差分別為2.60%、1.76%、2.75%，最大偏差分別為3.43%、2.48%、4.98%;VNSGA-Ⅱ的平均偏差分別為2.39%、3.38%、1.95%，最大偏差分別為6.08%、5.48%、4.06%;表現(xiàn)出較好的穩(wěn)健性。由于NSACO算法在迭代過(guò)程中需要額外更新路徑的信息素濃度，算法運(yùn)行時(shí)間相對(duì)較長(zhǎng)。

3.2.2 測(cè)試算例分析

為了驗(yàn)證提出算法在求解VRP問(wèn)題的普適性，采用Solomon基準(zhǔn)算例對(duì)算法性能作進(jìn)一步測(cè)試分析，本文選取C101、R101、RC101三組不同類(lèi)別的算例作為測(cè)試數(shù)據(jù)，分別對(duì)NSACO算法與VNSGA-Ⅱ算法運(yùn)行10次，算法參數(shù)及實(shí)驗(yàn)條件與基礎(chǔ)算例相同，測(cè)試結(jié)果如表5所示。

由表4和表5可知，在小規(guī)模基礎(chǔ)算例實(shí)驗(yàn)中，僅時(shí)間和

滿(mǎn)意度在精度方面得到了改進(jìn)，而在大規(guī)模實(shí)例中，由于蟻群優(yōu)化

的信息素正反饋機(jī)制及輪盤(pán)賭選擇策略，使得NSACO算法相較于VNSGA-Ⅱ算法在三個(gè)優(yōu)化目標(biāo)的精度上均有提高，并且在不同類(lèi)型實(shí)例的求解中均表現(xiàn)出優(yōu)勢(shì)。分析NSACO在成本、時(shí)間、滿(mǎn)意度三個(gè)方面的改進(jìn)程度，聚集分布實(shí)例C101在最優(yōu)解上分別優(yōu)化了4.08%、4.52%、2.90%，在平均解上分別優(yōu)化了6.80%、5.17%、4.02%;隨機(jī)分布實(shí)例R101在最優(yōu)解上分別優(yōu)化了10.59%、8.99%、2.96%，在平均解上分別優(yōu)化了12.92%、8.79%、5.31%;混合分布實(shí)例RC101在最優(yōu)解上分別優(yōu)化了9.68%、9.47%、2.78%，在平均解上分別優(yōu)化了11.97%、10.10%、4.81%。由此可見(jiàn)，相較于聚集分布問(wèn)題，NSACO在解決隨機(jī)分布問(wèn)題和混合分布的問(wèn)題更能發(fā)揮其算法優(yōu)勢(shì)，具有更好的可行性和精確性。

4 結(jié)語(yǔ)

本文以應(yīng)急初期自有車(chē)和租用車(chē)混合配送為實(shí)際背景，建立多目標(biāo)HVRPSTW優(yōu)化模型，針對(duì)該問(wèn)題設(shè)計(jì)了求解多目標(biāo)的NSACO算法。通過(guò)基礎(chǔ)算例和測(cè)試算例對(duì)模型和算法進(jìn)行驗(yàn)證，結(jié)果表明：

1）針對(duì)應(yīng)急物資運(yùn)輸中企業(yè)私有車(chē)輛不足的一類(lèi)情況，對(duì)同一路網(wǎng)內(nèi)自有車(chē)和租用車(chē)共同完成配送的組合優(yōu)化問(wèn)題進(jìn)行了研究，對(duì)該實(shí)際背景下的配送路徑規(guī)劃工作具有很強(qiáng)借鑒意義。

2）模型考慮總成本、系統(tǒng)配送時(shí)間和系統(tǒng)滿(mǎn)意度三個(gè)方面，有效地平衡受災(zāi)點(diǎn)和運(yùn)輸企業(yè)雙方的利益，具有很強(qiáng)的實(shí)用性，可以給運(yùn)輸商在不同的應(yīng)急背景下根據(jù)不同優(yōu)化目標(biāo)選擇合理的運(yùn)輸路徑提供決策依據(jù)。

3）設(shè)計(jì)NSACO算法求解模型，與改進(jìn)VNSGA-Ⅱ算法相比，NSACO能快速搜索到最優(yōu)解，并改善Pareto前沿的分布均勻性。算例分析表明：NSACO算法在求解精度、收斂性及穩(wěn)健性上均表現(xiàn)出更好的性能。

本文僅從靜態(tài)路網(wǎng)的角度對(duì)應(yīng)急路徑的優(yōu)化作研究，而更符合實(shí)際的時(shí)間依賴(lài)性車(chē)輛路徑以及動(dòng)態(tài)車(chē)輛路徑將是下一步研究課題。

參考文獻(xiàn)

[1]何明珂.應(yīng)急物流的成本損失無(wú)處不在[J].中國(guó)物流與采購(gòu)，2003（23）：18-19.（HE M K. The cost loss of emergency logistics is ubiquitous[J]. China Logistics and Purchasing， 2003（23）：18-19.）

[2]王付宇，王濤，葉春明.突發(fā)災(zāi)害事件情景下應(yīng)急救援車(chē)輛調(diào)度問(wèn)題綜述[J].計(jì)算機(jī)應(yīng)用研究，2017，34（10）：2887-2891.（WANG F Y， WANG T， YE C M. Review of emergency rescue vehicle scheduling problem under sudden disaster [J]. Application Research of Computers， 2017， 34（10）： 2887-2891.）

[3]曹琦，曹陽(yáng).應(yīng)急物資配送車(chē)輛調(diào)度模型與優(yōu)化綜述[J]. 計(jì)算機(jī)應(yīng)用， 2018，38（8）：2416-2422.（CAO Q， CAO Y. Review of model and optimization of vehicle scheduling for emergency material distribution [J]. Journal of Computer Applications， 2018， 38（8）： 2416-2422.）

[4]ARDEKANI S A，HOBEIKA A G. Logistics problems in the aftermath of the 1985 Mexico city earth-quake[J]. Transportation Quarterly， 1988， 42（1）： 107-124.

[5]郭詠梅，胡大偉，陳翔.改進(jìn)蟻群算法求解帶時(shí)間窗的應(yīng)急物流開(kāi)環(huán)車(chē)輛路徑問(wèn)題[J].長(zhǎng)安大學(xué)學(xué)報(bào)（自然科學(xué)版），2017，37（6）：105-112.（GUO Y M， HU D W， CHEN X. Solution of emergency logistics open-loop vehicle routing problem with time window based on improved ant colony algorithm [J]. Journal of Changan University （Natural Science Edition）， 2017， 37（6）： 105-112.）

[6]程碧榮，趙曉波，秦進(jìn).考慮供應(yīng)不足的應(yīng)急物流車(chē)輛路徑優(yōu)化模型及算法[J].計(jì)算機(jī)應(yīng)用研究，2016，33（6）：1682-1685.（CHENG B R， ZHAO X B， QIN J. Optimization model and algorithm for emergency vehicle route with insufficiency supply [J]. Application Research of Computers， 2016， 33（6）： 1682-1685.）

[7]WOHLGEMUTH S， OLORUNTOBA R， CLAUSEN U. Dynamic vehicle routing with anticipation in disaster relief [J]. Socio-Economic Planning Sciences， 2012， 46（4）： 261-271.

[8]NOROUZI N， SADEGH-AMALNICK M， TAVAKKOLI-MOGHADDAM R. Modified particle swarm optimization in a time-dependent vehicle routing problem： minimizing fuel consumption [J]. Optimization Letters， 2016， 11（1）： 121-134.

[9]杜苗苗.基于應(yīng)急物資分類(lèi)—分批配送的應(yīng)急車(chē)輛路徑研究[D]. 北京：北京交通大學(xué)，2014： 27-36.（DU M M. Emergency vehicle routing problem research based on emergency relief classification-batches distribution [D]. Beijing： Beijing Jiaotong University， 2014： 27-36.）

[10]CHANG F， WU J， LEE C， et al. Greedy-search-based multi-objective genetic algorithm for emergency logistics scheduling [J]. Expert Systems with Applications， 2014， 41（6）： 2947-2956.

[11]ZHANG J， PENG J， XU Z， et al. SDVRP model for emergency logistics and evolutionary heuristic approach [C]// Proceedings of the 2013 International Conference on Automatic Control and Artificial Intelligence. Stevenage， UK： IET， 2013： 1809-1812.

[12]方金城，張岐山. 物流配送車(chē)輛路徑問(wèn)題（VRP）算法綜述[J]. 沈陽(yáng)工程學(xué)院學(xué)報(bào)（自然科學(xué)版）， 2006， 2（4）： 357-360.（FANG J C， ZHANG Q S. Algorithm review on vehicle routing problem in logistics distribution [J]. Journal of Shenyang Institute of Engineering （Natural Science）， 2006， 2（4）： 357-360.）

[13]da COSTA P R O， MAUCERI S， CARROLL P， et al. A genetic algorithm for a green vehicle routing problem [J]. Electronic Notes in Discrete Mathematics， 2018， 64： 65-74.

[14]STODOLA P， MAZAL J， PODHOREC M， et al. Using the ant colony optimization algorithm for the capacitated vehicle routing problem [C]// Proceedings of the 16th International Conference on Mechatronics—Mechatronika. Piscataway， NJ： IEEE， 2014： 503-510.

[15]BRANDO J. A tabu search algorithm for the heterogeneous fixed fleet vehicle routing problem [J]. Computers and Operations Research， 2011， 38（1）： 140-151.

[16]GOEL R， MAINI R. A Hybrid of Ant colony and Firefly Algorithms （HAFA） for solving vehicle routing problems [J]. Journal of Computational Science， 2018， 25： 28-37.

[17]KAABACHI I， JRIJI D， KRICHEN S. An improved ant colony optimization for green multi-depot vehicle routing problem with time windows[C]// Proceedings of the 18th IEEE/ACIS International Conference on Software Engineering， Artificial Intelligence， Networking and Parallel/Distributed Computing. Piscataway， NJ： IEEE， 2017： 339-344.

[18]萬(wàn)旭，林健良，楊曉偉.改進(jìn)的最大最小螞蟻算法在有時(shí)間窗車(chē)輛路徑問(wèn)題中的應(yīng)用[J].計(jì)算機(jī)集成制造系統(tǒng)，2005，11（4）：572-576.（WAN X， LIN J L， YANG X W. Improved MMAS for vehicle routing problem with time window [J]. Computer Integrated Manufacturing Systems， 2005， 11（4）： 572-576.）

[19]DEB K， PRATAP A， AGARWAL S， et al. A fast and elitist multiobjective genetic algorithm： NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation， 2002， 6（2）： 182-197.

[20]HASSANZADEH A， RASTI-BARZOKI M. Minimizing total resource consumption and total tardiness penalty in a resource allocation supply chain scheduling and vehicle routing problem [J]. Applied Soft Computing， 2017， 58： 307-323.

LI Zhuo， born in 1993， M. S. candidate. His research interests include transportation planning and management， network optimization.

LI Yinzhen， born in 1963， Ph. D.， professor. His research interests include transportation system analysis and decision-making.

LI Wenxia， born in 1993， M. S. candidate. Her research interests include operation management and decision optimization of rail transit， network optimization.