張玉州 徐廷政 鄭軍帥 饒舜

摘 要：為了減少救災(zāi)物資配送的延誤時(shí)間和救災(zāi)車(chē)輛的總運(yùn)輸時(shí)間，引入緊急度的概念，建立了基于緊急度的救災(zāi)物資車(chē)輛路徑問(wèn)題模型，并設(shè)計(jì)了一種改進(jìn)遺傳算法對(duì)該模型進(jìn)行求解。首先，采用多種策略生成初始種群;然后，提出一種基于緊急度的任務(wù)再分配算法作為局部搜索算子，該算法依據(jù)緊急度為延誤安置點(diǎn)重新安排配送車(chē)輛或調(diào)整配送順序從而減少延誤時(shí)間，對(duì)無(wú)延誤的車(chē)輛優(yōu)化其路線從而減少總運(yùn)輸時(shí)間，以達(dá)到延誤時(shí)間和總運(yùn)輸時(shí)間兩者最優(yōu)。在17個(gè)數(shù)據(jù)集上與先來(lái)先服務(wù)（FCFS）算法、按緊急度排序（URGS）算法和遺傳算法（GA）三種算法進(jìn)行了對(duì)比。實(shí)驗(yàn)結(jié)果表明，具有基于緊急度的任務(wù)再分配策略的遺傳算法（TRUD-GA）與GA相比，平均延誤時(shí)間減少25.0%，平均運(yùn)輸時(shí)間減少1.9%，與FCFS、URGS算法相比改進(jìn)則更加明顯。

關(guān)鍵詞：緊急度;優(yōu)化;車(chē)輛路徑問(wèn)題;遺傳算法;局部搜索

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

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

Modeling and optimization of disaster relief vehicle routing problem considering urgency

ZHANG Yuzhou1，2， XU Tingzheng1，2*， ZHENG Junshuai1，2， RAO Shun1，2

1.School of Computer and Information， Anqing Normal University， Anqing Anhui 246133， China?;

2.Key Laboratory of Intelligent Perception and Computing in Anhui Province， Anqing Anhui 246011， China

Abstract：?In order to reduce the delay time of disaster relief materials distribution and the total transportation time of disaster relief vehicles， the concept of urgency was introduced to establish a vehicle routing problem model of disaster relief vehicles based on urgency， and an improved Genetic Algorithm （GA） was designed to solve the model. Firstly， multiple strategies were used to generate the initial population. Then， an urgency-based task redistribution algorithm was proposed as local search operator. The proposed algorithm achieved the optimal delay time and total transportation time based on urgency. The delay time was reduced by rescheduling the vehicle or adjusting the delivery sequence for delay placements. The routes of the vehicles without delay were optimized to reduce the total transportation time. In the experiments， the proposed algorithm was compared with First-Come-First-Served （FCFS） algorithm， Sort by URGency （URGS） and GA on 17 datasets. Results show that the Genetic Algorithm with Task Redistribution strategy based on Urgency Degree （TRUD-GA） reduces the average delay time by 25.0% and decreases the average transportation time by 1.9% compared with GA， and has more obvious improvement compared with FCFS and URGS algorithms.

Key words：?urgency; optimization; Vehicle Routing Problem （VRP）; Genetic Algorithm （GA）; local search

0 引言

我國(guó)是世界范圍內(nèi)自然災(zāi)害最嚴(yán)重的國(guó)家之一，發(fā)生災(zāi)害種類(lèi)多、頻率高，造成的人民生命財(cái)產(chǎn)損失巨大。災(zāi)害發(fā)生后的72小時(shí)被稱為“72小時(shí)黃金救援期”，說(shuō)明了救災(zāi)工作的緊迫性，因此，最大限度節(jié)省救災(zāi)物資配送時(shí)間具有重要的現(xiàn)實(shí)意義。應(yīng)急物流路徑規(guī)劃已經(jīng)成為一個(gè)研究熱點(diǎn)[1-5]。

目前，國(guó)內(nèi)外學(xué)者在救災(zāi)物資配送路徑規(guī)劃方面進(jìn)行了相關(guān)研究。如根據(jù)應(yīng)急救災(zāi)中的物資需求和道路通行時(shí)間等信息動(dòng)態(tài)更新的情況，對(duì)車(chē)輛行駛路徑動(dòng)態(tài)規(guī)劃進(jìn)行求解[6-9]。Zheng等[10]針對(duì)路況信息不確定的情況，采取模糊的方法求解。在實(shí)際生活中的確存在路況不確定情況，而使用模糊求解方式能大幅減小不確定因素的干擾，效果較好。易云飛等[11]討論了物流配送中考慮用戶滿意度、需求動(dòng)態(tài)改變的多目標(biāo)車(chē)輛路徑問(wèn)題模型的建立和優(yōu)化，并設(shè)計(jì)伊藤算法結(jié)合蟻群算法等進(jìn)行多目標(biāo)優(yōu)化求解。這種模型適用于一些不緊急的應(yīng)用場(chǎng)景，如超市供貨、快遞員取件等。任錫德等[12]考慮受災(zāi)點(diǎn)物資配送的路徑長(zhǎng)度均衡性和總時(shí)間兩個(gè)目標(biāo)，這種優(yōu)化目標(biāo)可使送貨車(chē)隊(duì)的各車(chē)工作量較為均衡，重點(diǎn)主要是在送貨方角度考慮問(wèn)題。文仁強(qiáng)等[13]考慮了多供應(yīng)點(diǎn)、多種物資類(lèi)型的情況，提出了多物資點(diǎn)為多個(gè)資源需求點(diǎn)協(xié)同配送物資的多目標(biāo)優(yōu)化模型，其優(yōu)勢(shì)在于將問(wèn)題情況細(xì)化，加入了多物資類(lèi)型和多供應(yīng)點(diǎn)要素。徐志宇等[14]以供需差異最小化、配送時(shí)間最短化、各災(zāi)點(diǎn)失衡度最低化為目標(biāo)。朱建明等[15]以未滿足的需求量和總的物資延誤時(shí)間最小為目標(biāo)。

綜上，目前應(yīng)急救災(zāi)車(chē)輛路徑問(wèn)題的研究常見(jiàn)多種因素綜合考慮，如：總運(yùn)輸時(shí)間與受災(zāi)點(diǎn)失衡度、信息不確定性與客戶滿意度等。雖然在考慮求解目標(biāo)上具有一定廣度，但缺乏對(duì)“救災(zāi)時(shí)效性”這一目標(biāo)的研究深度。從災(zāi)民的角度看，必然希望第一時(shí)間得到救助，因此要盡可能地提高救災(zāi)時(shí)效性。提高時(shí)效性就需要綜合考慮總延誤時(shí)間與總運(yùn)輸時(shí)間，只考慮總時(shí)間可能會(huì)為了整體時(shí)間的減少而犧牲掉某一個(gè)安置點(diǎn)的及時(shí)配送;以延誤時(shí)間為單一優(yōu)化目標(biāo)的算法則可能導(dǎo)致總體運(yùn)輸時(shí)間的增加，推遲了每個(gè)安置點(diǎn)獲得物資的時(shí)間，導(dǎo)致災(zāi)民的風(fēng)險(xiǎn)增大。

為提高救災(zāi)的及時(shí)性，降低運(yùn)輸風(fēng)險(xiǎn)，本文從救災(zāi)實(shí)際出發(fā)，提出了總運(yùn)輸時(shí)間和總延誤時(shí)間雙目標(biāo)的優(yōu)化模型，并設(shè)計(jì)了一種遺傳算法（Genetic Algorithm， GA）對(duì)問(wèn)題進(jìn)行求解，其中包括一種局部搜索算法，即基于緊急度的任務(wù)再分配（Task Reassignment with Urgency Degree，TRUD）算子，同時(shí)在生成初始解階段采用多種優(yōu)化策略生成，以提高初始種群的質(zhì)量。經(jīng)過(guò)仿真實(shí)驗(yàn)的驗(yàn)證，本文模型及求解算法在保證延誤時(shí)間最小化的同時(shí)縮短了總運(yùn)輸路徑長(zhǎng)度，與一些經(jīng)典算法對(duì)比優(yōu)勢(shì)明顯。

1 問(wèn)題分析與建模

1.1 問(wèn)題描述

災(zāi)害發(fā)生后，受災(zāi)群眾被安置在n個(gè)臨時(shí)安置點(diǎn)，每個(gè)安置點(diǎn)需要救災(zāi)物資的數(shù)量和需求的急迫程度不同。為了使問(wèn)題更易于求解，引入緊急度的概念，其數(shù)值為某個(gè)安置點(diǎn)的截止時(shí)間和救災(zāi)車(chē)隊(duì)出發(fā)時(shí)間所相差的分鐘數(shù)。假設(shè)當(dāng)前時(shí)間為8：00，救災(zāi)車(chē)隊(duì)即將出發(fā)。甲村情況非常緊急，要求3h內(nèi)獲得50單位物資;乙村形勢(shì)相對(duì)緩和，要求8h獲得100單位物資。此時(shí)稱甲村緊急度為180，截止時(shí)間為11：00;乙村緊急度為480，截止時(shí)間為14：00。在配送救災(zāi)物資時(shí)，將以緊急度作為確定安置點(diǎn)配送順序和路徑改進(jìn)的重要依據(jù)。救災(zāi)車(chē)隊(duì)必須盡最大可能減少物資配送到各安置點(diǎn)的延誤時(shí)間，最小化車(chē)隊(duì)總行駛時(shí)間，即同時(shí)優(yōu)化總延誤時(shí)間和總運(yùn)輸時(shí)間兩目標(biāo)。

1.2 問(wèn)題建模

1.2.1 模型設(shè)計(jì)與約定

應(yīng)急救災(zāi)的物流路徑規(guī)劃問(wèn)題可以抽象為車(chē)輛路徑問(wèn)題（Vehicle Routing Problem， VRP）。災(zāi)民分布在n個(gè)安置點(diǎn)，各安置點(diǎn)的物資需求量為qi， m輛車(chē)從物資儲(chǔ)備倉(cāng)庫(kù)（Depot）出發(fā)，各自配送一定數(shù)量的安置點(diǎn)，n個(gè)安置點(diǎn)全部配送完成后車(chē)輛空載返回，此過(guò)程形成m條回路。根據(jù)實(shí)際情況設(shè)置下列規(guī)定和限制條件：

1）所有運(yùn)輸車(chē)輛的容量和速度相同;

2）各安置點(diǎn)之間均有通路;

3）每個(gè)安置點(diǎn)只配送一次;

4）各安置點(diǎn)需求量已知;

5）各安置點(diǎn)截止時(shí)間已知;

6）每個(gè)安置點(diǎn)配送一次且僅配送一次完成;

7）各安置點(diǎn)對(duì)物資的需求量用若干個(gè)單位數(shù)量的物資表示;

8）任一運(yùn)輸車(chē)配送路線上各安置點(diǎn)的合計(jì)需求量不能超過(guò)該運(yùn)輸車(chē)的容量;

9）各安置點(diǎn)根據(jù)其緊急的程度上報(bào)截止時(shí)間，越緊急其截止時(shí)間越提前。

1.2.2 參數(shù)與變量

本文所用參數(shù)與變量如表1所示。

1.2.3 數(shù)學(xué)模型

根據(jù)以上假設(shè)和定義，結(jié)合VRP模型，建立如下應(yīng)急救災(zāi)車(chē)輛路徑問(wèn)題的數(shù)學(xué)模型及目標(biāo)函數(shù)。

min Z=∑ n i=0 ∑ n j=0 ∑ m k=1 disti，j·χijk

（1）

s.t.

∑ n j=1 χijk=∑ n j=1 χjik≤1; k∈{1，2，…，m}

（2）

∑ n j=0 ∑ m k=1 χijk=1; i∈{1，2，…，n}

（3）

∑ n i=1 ∑ n j=1 qi·χijk≤c; k∈{1，2，…，m}

（4）

min z1=∑ m i=1 ∑ ki j=1 （atj-dtj）

（5）

min z2= 1 v? ∑ m i=1 ∑ ki j=0 distj， j+1

（6）

min z3=? 1-α v? ∑ m i=1 ∑ ki j=0 distj， j+1+α∑ m i=1 ∑ ki j=1 （atj-dtj）

（7）

上述建立的數(shù)學(xué)模型中：式（1）為基本VRP模型的目標(biāo)函數(shù)，一般為車(chē)輛運(yùn)輸距離的總里程;式（2）確保車(chē)輛總路線是閉合型的，從某點(diǎn)出發(fā)并最終返回該點(diǎn);式（3）表示每個(gè)客戶有且只有一輛車(chē)對(duì)其進(jìn)行服務(wù);式（4）表示每輛車(chē)不得超載;式（5）表示車(chē)隊(duì)總的配送延誤時(shí)間;

式（6）表示車(chē)隊(duì)總運(yùn)輸時(shí)間，且式中0以及ki+1（當(dāng)j=ki時(shí)， j+1=ki+1）都代表物資儲(chǔ)備倉(cāng)庫(kù);

式（7）表示兩目標(biāo)協(xié)同優(yōu)化，通過(guò)系數(shù)α調(diào)節(jié)總運(yùn)輸時(shí)間和總延誤時(shí)間的權(quán)重，以確定算法優(yōu)化的方向偏好，在0到1之間，α取值越大，函數(shù)越偏向于優(yōu)化延誤時(shí)間，反之偏向于優(yōu)化總運(yùn)輸時(shí)間。

2 引入緊急度概念的改進(jìn)遺傳算法

遺傳算法是一種有代表性的元啟發(fā)式算法，具有良好的魯棒性和擴(kuò)展性，廣泛應(yīng)用于復(fù)雜組合優(yōu)化問(wèn)題的求解。遺傳算法在VRP解空間中選取若干個(gè)解組成一個(gè)集合，這些解稱為個(gè)體，即染色體，該集合稱為種群。根據(jù)達(dá)爾文進(jìn)化論的思想，在種群內(nèi)部選擇優(yōu)秀個(gè)體，進(jìn)行染色體交叉、變異等操作，經(jīng)過(guò)n次迭代優(yōu)化，求得最優(yōu)解。本文在傳統(tǒng)遺傳算法的基礎(chǔ)上改進(jìn)了其初始解生成策略，提高了前期收斂速度，同時(shí)根據(jù)問(wèn)題特性，提出了一種局部搜索算子TRUD，增強(qiáng)其局部搜索能力，在出現(xiàn)延誤點(diǎn)時(shí)還具有定向搜索能力，避免陷入局部最優(yōu)解和早熟。

2.1 染色體編碼

1）給每個(gè)安置點(diǎn)分配一個(gè)序號(hào)，生成一個(gè)包含所有安置點(diǎn)的序列。

2）將安置點(diǎn)逐個(gè)分配給某輛車(chē)，直至達(dá)到容量限制;剩下的安置點(diǎn)繼續(xù)分配給下一輛車(chē)，直至所有安置點(diǎn)都分配完成。

2.2 適應(yīng)度函數(shù)

本文中的一條染色體包含m條回路，適應(yīng)度函數(shù)的目標(biāo)是

總運(yùn)輸時(shí)間和總延誤時(shí)間的協(xié)同優(yōu)化。α表示決策偏好參數(shù)，取值在0到1之間：取值越大，物資延誤時(shí)間所占的權(quán)重越大，則越不能容忍延誤情況的發(fā)生;若α取較小值，則意味著在減少安置點(diǎn)平均等待時(shí)間的前提下，可以容忍少量延誤。適應(yīng)度函數(shù)如式 （7）。由于本文的目標(biāo)是時(shí)間的最小化，所以適應(yīng)度函數(shù)是極小化的，其函數(shù)值越小表示適應(yīng)度越高。

2.3 局部搜索算子TRUD

對(duì)于傳統(tǒng)VRP，由于適應(yīng)度評(píng)價(jià)對(duì)象是一整條基因序列，而對(duì)單個(gè)基因位不能做出評(píng)價(jià)，因此傳統(tǒng)的變異算子通過(guò)無(wú)方向性地隨機(jī)改變基因位，以求得更好的解;但該方法在大規(guī)模的解空間中搜索能力較弱，對(duì)總體改進(jìn)較小且效率低。而本文模型中的基因位具有緊急度和延誤時(shí)間的屬性，可根據(jù)單個(gè)基因位的延誤時(shí)間進(jìn)行定向的優(yōu)化，使之向延誤時(shí)間減小的方向快速改進(jìn)?；诖耍疚奶岢龌诰o急度的任務(wù)再分配策略（TRUD），對(duì)延誤安置點(diǎn)重新安排配送車(chē)輛或順序，減少延誤時(shí)間，并對(duì)無(wú)延誤的車(chē)輛進(jìn)行運(yùn)輸距離上的優(yōu)化;同時(shí)，以TRUD作為遺傳算法的變異算子，來(lái)提高局部搜索能力。

局部搜索算子TRUD主要算法步驟如下：

1）隨機(jī)選擇一個(gè)回路，找到其中被延誤時(shí)間最長(zhǎng)的安置點(diǎn)。

2）在其他回路中尋找被延誤的安置點(diǎn)，若存在，跳轉(zhuǎn)到第3）步，否則跳轉(zhuǎn)到第4）步。

3）將兩個(gè)安置點(diǎn)交由對(duì)方的車(chē)輛負(fù)責(zé)配送，若無(wú)改進(jìn)，進(jìn)入第4）步。

4）將延誤的安置點(diǎn)交由車(chē)隊(duì)中運(yùn)輸時(shí)間最短的車(chē)輛進(jìn)行配送（滿足容量限制的條件下）。首先將其放在隊(duì)列末尾，計(jì)算適應(yīng)度函數(shù)，若無(wú)改進(jìn)，前移一位，直至取得更優(yōu)解或移動(dòng)到首位停止。檢查染色體中各基因位（即各安置點(diǎn)）的緊急度，若同一個(gè)回路內(nèi)存在緊急度高的點(diǎn)位于緊急度低的點(diǎn)后面，調(diào)換其位置。若換位后總延誤時(shí)間下降，則繼續(xù)向前進(jìn)行換位，直到無(wú)改進(jìn)為止。緊急度值越小表示越緊急，圖1中2號(hào)安置點(diǎn)緊急度高于1號(hào)安置點(diǎn)，應(yīng)對(duì)其進(jìn)行換位。

5）隨機(jī)選擇一個(gè)回路檢測(cè)其延誤情況，若有延誤則跳轉(zhuǎn)到第6）步，否則跳轉(zhuǎn)到第7）步。

6）檢查位于當(dāng)前延誤點(diǎn)之前一個(gè)安置點(diǎn)的緊急度，若較當(dāng)前延誤點(diǎn)緊急，則無(wú)需調(diào)整;相反，若比延誤點(diǎn)小則二者換位。若換位后總延誤時(shí)間和總運(yùn)輸時(shí)間均更優(yōu)，則繼續(xù)向前換位，直至無(wú)改進(jìn)為止。

7）隨機(jī)選擇本回路內(nèi)兩個(gè)安置點(diǎn)進(jìn)行換位操作，若有改進(jìn)則保留，若無(wú)改進(jìn)則結(jié)束本次變異。

2.4 初始化種群

在解決基本的VRP時(shí)，初始種群一般采用隨機(jī)產(chǎn)生所有個(gè)體，該方法存在初始種群優(yōu)秀個(gè)體數(shù)量少、整體適應(yīng)度低、算法搜索時(shí)間長(zhǎng)、收斂速度慢等問(wèn)題。針對(duì)上述情況，本文在初始化種群階段綜合使用三種算法：隨機(jī)生成、按緊急度排序和最近鄰域（Nearest Neighborhood）優(yōu)化。

1）隨機(jī)產(chǎn)生一個(gè)安置點(diǎn)序列，將其按順序逐個(gè)安排給第一輛車(chē)，同時(shí)計(jì)算其需求量累加之和，一旦達(dá)到一輛車(chē)的車(chē)輛容量限制即停止加入，保留這輛車(chē)最大能承載的需求點(diǎn)集合，則該車(chē)配送方案生成。將剩余未安排的安置點(diǎn)繼續(xù)按順序安排到下一輛車(chē)，直至所有安置點(diǎn)均安排完畢。

2）使用最近鄰域算法和緊急度排序法各生成5～10個(gè)較優(yōu)解，替換掉種群中適應(yīng)度最差的幾個(gè)個(gè)體。

2.5 選擇

使用輪盤(pán)賭算法選擇優(yōu)秀的個(gè)體和基因，其基本思想是個(gè)體被選中的概率與其適應(yīng)度函數(shù)值成正比，而非機(jī)械地按照適應(yīng)度大小來(lái)選擇。這種做法可保持種群的基因多樣性，避免早熟。設(shè)群體大小為n， 個(gè)體i的適應(yīng)度為Fi， 則個(gè)體i被選中遺傳到下一代群體的概率為：

Pi=Fi / ∑ n i=1 Fi

（8）

在迭代過(guò)程中采用精英策略，本代最好的個(gè)體直接復(fù)制到下一代種群中，保證優(yōu)秀基因的延續(xù)。

2.6 交叉算子

交叉操作是將兩條染色體選取一點(diǎn)，對(duì)換選定區(qū)域，以達(dá)到產(chǎn)生基因型不同的新個(gè)體的效果。本文采用的交叉方法是交換父代雙方的部分序列順序信息。

交叉算子具體算法步驟如下：

圖2所示兩個(gè)染色體P1和P2，每個(gè)染色體含有3輛車(chē)產(chǎn)生的3個(gè)子集回路。

1）在兩個(gè)染色體中各隨機(jī)選擇一個(gè)子集，得到集合a和b。

2）若 | a∩b | ≥2，轉(zhuǎn)步驟3），否則返回步驟1）。

3）以子集a={4， 5， 6， 10}和子集b={8， 6， 4， 9}為例，a∩b={4， 6}。檢查兩個(gè)集合中元素4、6的先后順序是否一致，一致則轉(zhuǎn)到步驟1），否則轉(zhuǎn)到步驟4）。

4）分別將兩個(gè)集合中元素4、6的順序按對(duì)方的元素順序進(jìn)行調(diào)換，交叉后所得個(gè)體如圖3所示，可以看出子代染色體C1、C2具有融合后的父代遺傳信息。

算法步驟在哪里，不可能是圖2吧？

3 實(shí)驗(yàn)仿真及分析

3.1 算例描述與實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)數(shù)據(jù)集包括1個(gè)仿真算例和16個(gè)來(lái)自VRP標(biāo)準(zhǔn)數(shù)據(jù)集的算例，其中仿真算例根據(jù)M地區(qū)地理?xiàng)l件模擬產(chǎn)生。

實(shí)驗(yàn)中提到的總運(yùn)輸時(shí)間指車(chē)隊(duì)所有車(chē)輛各自運(yùn)輸時(shí)間的數(shù)值之和，總延誤時(shí)間同理。

本文中所有算法均采用Java語(yǔ)言實(shí)現(xiàn)，實(shí)驗(yàn)環(huán)境為主頻3.4GHz的Intel Core i5-7500 CPU，內(nèi)存8GB的硬件平臺(tái)，種群規(guī)模200，適應(yīng)度參數(shù)α=0.75，交叉概率08，局部搜索概率01，設(shè)置最大迭代次數(shù)為600，每個(gè)算例均進(jìn)行30次獨(dú)立的計(jì)算取平均值。

3.2 結(jié)果分析

1）M地區(qū)救災(zāi)路徑規(guī)劃仿真實(shí)驗(yàn)結(jié)果分析。

M地區(qū)地理?xiàng)l件易發(fā)生泥石流災(zāi)害，現(xiàn)模擬M地區(qū)發(fā)生特大泥石流，在當(dāng)?shù)卦O(shè)置19個(gè)災(zāi)民安置點(diǎn)，救災(zāi)部門(mén)派出3輛容量為100的救災(zāi)車(chē)裝載物資運(yùn)往災(zāi)區(qū)，車(chē)速設(shè)置為30km/h。安置點(diǎn)位置和緊急度已知，見(jiàn)表2。

表2列出了每個(gè)安置點(diǎn)的編號(hào)、坐標(biāo)（X、Y為安置點(diǎn)橫縱坐標(biāo)，單位為km）、物資需求量（Q）、緊急度（URG）和使用四種算法各自求得的延誤時(shí)間（單位為min）。

其中：序號(hào)為0的點(diǎn)是出發(fā)點(diǎn)物資倉(cāng)庫(kù);對(duì)于提前到達(dá)或準(zhǔn)時(shí)到達(dá)的安置點(diǎn)，其延誤時(shí)間均記為0;

URG的數(shù)值模擬災(zāi)民的不同需求，設(shè)置在180～600min區(qū)間。

表3中對(duì)比了四種算法的物資配送延誤時(shí)間。

對(duì)比算法包括：

先來(lái)先服務(wù)（First Come First Served， FCFS）算法，表示按照安置點(diǎn)報(bào)告的順序進(jìn)行配送;

按緊急度排序（Sort by URGency， URGS）算法，對(duì)救災(zāi)車(chē)輛分配到的任務(wù)嚴(yán)格按照各安置點(diǎn)的緊急度進(jìn)行配送，而且不考慮距離的遠(yuǎn)近;

TRUD-GA為本文算法，對(duì)延誤時(shí)間和總運(yùn)輸時(shí)間加權(quán)求解;

GA為T(mén)RUD-GA去除改進(jìn)初始解和變異算子后的算法，用以驗(yàn)證本文加入算子TRUD的有效性。

其中：FCFS表示按照安置點(diǎn)報(bào)告的順序進(jìn)行配送;URGS表示對(duì)救災(zāi)車(chē)輛分配到的任務(wù)嚴(yán)格按照各安置點(diǎn)的緊急度進(jìn)行配送，而且不考慮距離的遠(yuǎn)近;TRUD-GA為本文算法，對(duì)延誤時(shí)間和總運(yùn)輸時(shí)間加權(quán)求解;GA為T(mén)RUD-GA去除改進(jìn)初始解和變異算子后的算法，用以驗(yàn)證本文加入算子TRUD的有效性。

以先來(lái)先服務(wù)（First Come First Served， FCFS）、按緊急度排序（Sorting algorithm based on URGency， URGS）、GA 、TRUD-GA（GA with TRUD）

為列名的四列數(shù)據(jù)分別表示該算法求得的每一個(gè)安置點(diǎn)的延誤時(shí)間。對(duì)于提前到達(dá)或準(zhǔn)時(shí)到達(dá)的安置點(diǎn)，其延誤時(shí)間均記為0。序號(hào)為0的點(diǎn)是出發(fā)點(diǎn)物資倉(cāng)庫(kù)。X、Y單位為km，URG、FCFS、URGS、GA、TRUD-GA單位為min。

從表2和表3可以看出：在四種算法中，F(xiàn)CFS算法延誤時(shí)間中位數(shù)接近2h，最長(zhǎng)延誤時(shí)間甚至達(dá)到2.5h以上，延誤點(diǎn)數(shù)也多達(dá)7個(gè);而URGS算法雖然總延誤時(shí)間和延誤點(diǎn)數(shù)比FCFS算法有所減少，但總體效果依然不理想，尤其是最長(zhǎng)延誤時(shí)間仍接近2h;GA有1個(gè)安置點(diǎn)延誤，延誤時(shí)間為8.6min;而算法TRUD-GA則做到了沒(méi)有任何延誤。由此可見(jiàn)TRUD-GA在總延誤時(shí)間、最長(zhǎng)延誤時(shí)間上均優(yōu)于FCFS、URGS和GA。

2）CVRP標(biāo)準(zhǔn)數(shù)據(jù)集實(shí)驗(yàn)結(jié)果分析及TRUD算子局部搜索性能驗(yàn)證。

實(shí)驗(yàn)數(shù)據(jù)來(lái)自VRP國(guó)際標(biāo)準(zhǔn)數(shù)據(jù)集，可從網(wǎng)站http：//neo.lcc.uma.es/vrp/vrp-instances/下載。數(shù)據(jù)集包含不同需求點(diǎn)數(shù)量、需求點(diǎn)位置、車(chē)輛數(shù)量和容量的多個(gè)算例。由于標(biāo)準(zhǔn)算例中無(wú)截止時(shí)間參數(shù)，因此本實(shí)驗(yàn)使用隨機(jī)函數(shù)給每個(gè)需求點(diǎn)設(shè)置了物資配送的截止時(shí)間。設(shè)定車(chē)輛行駛速度為60km/h，并求出救災(zāi)車(chē)輛到達(dá)每個(gè)安置點(diǎn)的時(shí)間，統(tǒng)計(jì)總延誤時(shí)間和總行駛時(shí)間。表4列出了相關(guān)算例的具體參數(shù)，其中：n表示安置點(diǎn)數(shù)量，m表示車(chē)輛數(shù)，c表示車(chē)輛容量。

為了驗(yàn)證算法的魯棒性，每個(gè)算例進(jìn)行2次不同截止時(shí)間參數(shù)設(shè)置，共16組仿真實(shí)驗(yàn)，同一算例因緊急度設(shè)置不同而分別編號(hào)，例如A-n32-k5-u1與A-n32-k5-u2，結(jié)果如表5所示。URG的數(shù)值在90～840min隨機(jī)生成。實(shí)驗(yàn)對(duì)比了FCFS、URGS、GA和本文算法TRUD-GA，對(duì)每種算法記錄以下三個(gè)指標(biāo)：TPT表示車(chē)隊(duì)總的運(yùn)輸時(shí)間，DEL表示車(chē)隊(duì)總延誤時(shí)間，單位均為min;NUM表示配送延誤的安置點(diǎn)數(shù)量。這三個(gè)指標(biāo)的數(shù)值均越小越好。

由表5可知，在大多數(shù)算例中，TRUD-GA與其他對(duì)比算法相比延誤時(shí)間最小，雖然在一些算例中延誤時(shí)間比URGS算法略有增加，但總運(yùn)輸時(shí)間與URGS算法相比則大量減少。如算例A-n61-k9-u1，URGS算法總運(yùn)輸時(shí)間為3034min，延誤時(shí)間為0，而TRUD-GA總運(yùn)輸時(shí)間為1996min，延誤時(shí)間為1.8min，僅增加了1.8min延誤，而總時(shí)間降低了34.2%。

由表6可知，與FCFS算法相比，TRUD-GA的平均延誤時(shí)間降低了99.7%，平均延誤點(diǎn)數(shù)降低了96.1%，平均運(yùn)輸時(shí)間降低了40.2%;

與URGS算法相比，TRUD-GA的平均延誤時(shí)間降低了97.1%，平均延誤點(diǎn)數(shù)降低了78.9%，平均運(yùn)輸時(shí)間降低了38.9%;

與GA相比，TRUD-GA的平均延誤時(shí)間降低了25.0%，平均延誤點(diǎn)數(shù)降低了16.7%，而平均運(yùn)輸時(shí)間降低了1.9%。

表6還統(tǒng)計(jì)了各算法的延誤時(shí)間標(biāo)準(zhǔn)差，TRUD-GA為1.35，小于FCFS、URGS和GA，可見(jiàn)其求解性能穩(wěn)定，對(duì)不同算例求解時(shí)魯棒性優(yōu)于對(duì)比算法。

由表2、3、5、6中TRUD-GA與GA的實(shí)驗(yàn)結(jié)果對(duì)比可知，本文提出的局部搜索算子TRUD對(duì)實(shí)驗(yàn)結(jié)果起到了比較明顯的改進(jìn)作用。

為了進(jìn)一步直觀地驗(yàn)證TRUD算子的局部搜索性能，對(duì)TRUD-GA與無(wú)TRUD算子的遺傳算法GA的迭代過(guò)程進(jìn)行比較，它們?cè)谒憷鼳-n39-k6、A-n45-k6、A-n69-k9、 A-n80-k10上的運(yùn)行結(jié)果如圖4。由于適應(yīng)度函數(shù)是極小化的，所以適應(yīng)度函數(shù)值越小越好。從圖4中可以看出，在600代迭代過(guò)程中，TRUD-GA一直保持著持續(xù)收斂的趨勢(shì)，且不同規(guī)模的4個(gè)算例中取得的最優(yōu)解均好于GA。由此可見(jiàn)TRUD算子具有優(yōu)秀的局部搜索性能和全局收斂能力，同時(shí)也表現(xiàn)出了良好的魯棒性。

3.3 決策偏好參數(shù)分析

適應(yīng)度函數(shù)中的決策偏好參數(shù)α決定了算法優(yōu)化的方向：取值趨向0時(shí)偏好于總運(yùn)輸時(shí)間最小化，也即總距離最小化;取值趨向1時(shí)偏好總延誤時(shí)間最小化。緊急度和系數(shù)α都是算法優(yōu)化時(shí)的重要參數(shù)，緊急度是算法使用者無(wú)法控制的，而α可由使用者調(diào)節(jié)，在不增加延誤時(shí)間的前提下降低總運(yùn)輸距離和時(shí)間。為驗(yàn)證參數(shù)α的應(yīng)用效果，現(xiàn)對(duì)所有算例進(jìn)行不同α取值的對(duì)比實(shí)驗(yàn)。每組實(shí)驗(yàn)運(yùn)行30次取平均值，結(jié)果如表7所示。

可以看出，隨著α取值的增大，總延誤時(shí)間逐漸減小，延誤點(diǎn)數(shù)逐漸減少，總運(yùn)輸時(shí)間逐漸增加。對(duì)于大多數(shù)算例，例如A-n45-k6，在α=0.75時(shí)平均延誤時(shí)間為1.2min，因?yàn)樯鲜鼋Y(jié)果是運(yùn)行30次的平均值，此時(shí)已經(jīng)能以較大概率取得最優(yōu)解;而在α=0.99時(shí)，其延誤時(shí)間為0，但總運(yùn)輸時(shí)間卻比α=0.75時(shí)有一定程度的增加，因此驗(yàn)證了參數(shù)α取0.75的合理性。而對(duì)于個(gè)別特殊的算例，其安置點(diǎn)間距很大，難以在規(guī)定截止時(shí)間內(nèi)配送，α=0.75時(shí)物資配送仍有較為明顯的延誤情況發(fā)生，例如算例A-n80-k10，此時(shí)設(shè)置α=099可減少平均延誤時(shí)間12.4min，延誤安置點(diǎn)數(shù)量減少平均1.1個(gè)，說(shuō)明了決策偏好參數(shù)α對(duì)優(yōu)化方向起到的作用。

通過(guò)以上對(duì)比實(shí)驗(yàn)可以得出結(jié)論：使用TRUD-GA求解考慮緊急度的應(yīng)急救災(zāi)車(chē)輛路徑問(wèn)題，災(zāi)區(qū)安置點(diǎn)的物資配送總延誤時(shí)間、延誤安置點(diǎn)數(shù)量、車(chē)輛總運(yùn)輸時(shí)間相比其他算法均有明顯下降，求解過(guò)程說(shuō)明TRUD-GA具有良好的收斂性以及尋優(yōu)能力。通過(guò)對(duì)決策偏好參數(shù)α的不同設(shè)置分析，說(shuō)明了TRUD-GA具有良好的適用性。

4 結(jié)語(yǔ)

本文依據(jù)救災(zāi)工作的現(xiàn)實(shí)要求——最小化救災(zāi)車(chē)輛延誤時(shí)間和最小化總運(yùn)輸時(shí)間的兩個(gè)目標(biāo)，設(shè)計(jì)了基于緊急度的混合遺傳算法，提出了基于緊急度的任務(wù)再分配算子TRUD，對(duì)應(yīng)急物資調(diào)度路線進(jìn)行有針對(duì)性的優(yōu)化。對(duì)實(shí)驗(yàn)結(jié)果的分析表明，TRUD算子有著良好的局部搜索能力，以TRUD為局部搜索算子的混合遺傳算法TRUD-GA可以顯著降低物資配送延誤時(shí)間和總體運(yùn)輸時(shí)間。本文模型中的路徑狀態(tài)為完全暢通，而在災(zāi)情突發(fā)的情況下會(huì)存在路徑擁堵，因此如何在災(zāi)區(qū)路況不同的情況下設(shè)計(jì)動(dòng)態(tài)的救災(zāi)物資調(diào)度策略還需進(jìn)一步的研究。

參考文獻(xiàn)

[1]?LI Q， TU W， ZHUO L. Reliable rescue routing optimization for urban emergency logistics under travel time uncertainty [J]. International Journal of Geo-Information， 2018， 77（7）： 1-21.

[2]??徐浩，李佳川，韓傳峰.震后運(yùn)速受限條件下的多目標(biāo)定位：路徑問(wèn)題研究[J].管理工程學(xué)報(bào)，2017，31（4）：147-155. （XU H， LI J C， HAN C F. Multi-target localization under the condition of limited speed after earthquake： research on path problem[J].Journal of Industrial Engineering/Engineering Management，2017，31（4）：147-155.）

[3]?張國(guó)富，王永奇，蘇兆品，等.應(yīng)急救援物資多目標(biāo)分配與調(diào)度問(wèn)題建模與求解[J].控制與決策，2017，32（1）：86-92. （ZHANG G F， WANG Y Q， SU Z P， et al. Modeling and solving multi-objective allocations-cheduling problem for emergency relief materials[J]. Control and Decision， 2017， 32（1）： 86-92.）

[4]?SHAHPARVARI S， ABBASI B， CHHETRI P， et al. Vehicle routing and scheduling for bushfire emergency evacuation [C]// Proceedings of the 2015 IEEE International Conference on Industrial Engineering and Engineering Management. Piscataway， NJ： IEEE， 2015： 696-700.

[5]?HE Y， WEN J， HUANG M. Study on emergency relief VRP based on clustering and PSO [C]// Proceedings of the 11th International Conference on Computational Intelligence and Security. Washington， DC： IEEE Computer Society， 2015： 43-47.

[6]??石建力，張錦.需求點(diǎn)隨機(jī)的分批配送VRP模型與算法研究[J].控制與決策，2017，32（2）：213-222. （SHI J L，ZHANG J.Model and algorithm for split delivery vehicle routing problem with stochastic customers[J].Control and Decision，2017，32（2）：213-222.）

[7]?ZHAO J， GUO Y， DUAN X. Dynamic path planning of emergency vehicles based on travel time prediction [J]. International Journal of Communications， Network and System Sciences， 2018， 11（2）： Article ID： 9184891.

[8]?LIU J， XIE K. Emergency materials transportation model in disasters based on dynamic programming and ant colony optimization [J]. Kybernetes， 2017， 46（4）： 656-671.

[9]?QIN J， YE Y， CHENG B， et al. The emergency vehicle routing problem with uncertain demand under sustainability environments [J]. Sustainability， 2017， 9（3）： 1-24.

[10]?ZHENG Y， LING H. Emergency transportation planning in disaster relief supply chain management： a cooperative fuzzy optimization approach [J]. Soft Computing， 2013， 17（7）： 1301-1314.

[11]???易云飛，蔡永樂(lè)，董文永，等.求解帶用戶滿意度的多目標(biāo)實(shí)時(shí)車(chē)輛路徑問(wèn)題的改進(jìn)伊藤算法[J].電子學(xué)報(bào)，2015，43（10）：2053-2061. （YI Y F， CAI Y L， DONG W Y， et al. Improved ITO algorithm for multiobjective real-time vehicle routing problem with customers satisfaction [J].Acta Electronica Sinica，2015，43（10）：2053-2061.）

[12]?任錫德，朱建明，王晶，等.考慮均衡性的不確定時(shí)間車(chē)輛調(diào)度問(wèn)題研究[J].運(yùn)籌與管理，2013，22（2）：86-91. （REN X D， ZHU J M， WANG J， et al. Research on load-balancing vehicle routing problem with uncertain travel time [J]. Operations Research and Management Science， 2013， 22（02）： 86-91.）

[13]??文仁強(qiáng)，鐘少波，袁宏永，等.應(yīng)急資源多目標(biāo)優(yōu)化調(diào)度模型與多蟻群優(yōu)化算法研究[J].計(jì)算機(jī)研究與發(fā)展，2013，50（7）：1464-1472. （WEN R Q， ZHONG S B， YUAN H Y， et al. Emergency resource multi-objective optimization scheduling model and multic-olony ant optimization algorithm for emergency resources [J].Journal of Computer Research and Development，2013，50（7）：1464-1472.）

[14]?徐志宇，張杰，彭嘉臻，等.應(yīng)急物流的分批配送模型及亞啟發(fā)式算法求解[J].系統(tǒng)仿真學(xué)報(bào)，2012，24（12）：2500-2505， 2510. （XU Z Y， ZHANG J， PENG J Z， et al. Split delivery model and metaheuristic approach for emergency logistics [J]. Journal of System Simulation， 2012， 24（12）： 2500-2505， 2510.）

[15]?朱建明，黃鈞，劉德剛，等.突發(fā)事件應(yīng)急醫(yī)療物資調(diào)度的隨機(jī)算法[J].運(yùn)籌與管理，2010，19（1）：9-14. （ZHU J M， HUANG J， LIU D G， et al. Randomized algorithm for vehicle routing model for medical supplies in large-scale emergencies [J]. Operations Research and Management Science， 2010， 19（1）： 9-14.）