張玉州 徐廷政 鄭軍帥 饒舜

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

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

中圖分類號：?TP301.6

文獻標(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 引言

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

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

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

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

1 問題分析與建模

1.1 問題描述

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

1.2 問題建模

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

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

1）所有運輸車輛的容量和速度相同;

2）各安置點之間均有通路;

3）每個安置點只配送一次;

4）各安置點需求量已知;

5）各安置點截止時間已知;

6）每個安置點配送一次且僅配送一次完成;

7）各安置點對物資的需求量用若干個單位數(shù)量的物資表示;

8）任一運輸車配送路線上各安置點的合計需求量不能超過該運輸車的容量;

9）各安置點根據(jù)其緊急的程度上報截止時間，越緊急其截止時間越提前。

1.2.2 參數(shù)與變量

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

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

根據(jù)以上假設(shè)和定義，結(jié)合VRP模型，建立如下應(yīng)急救災(zāi)車輛路徑問題的數(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ù)，一般為車輛運輸距離的總里程;式（2）確保車輛總路線是閉合型的，從某點出發(fā)并最終返回該點;式（3）表示每個客戶有且只有一輛車對其進行服務(wù);式（4）表示每輛車不得超載;式（5）表示車隊總的配送延誤時間;

式（6）表示車隊總運輸時間，且式中0以及ki+1（當(dāng)j=ki時， j+1=ki+1）都代表物資儲備倉庫;

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

2 引入緊急度概念的改進遺傳算法

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

2.1 染色體編碼

1）給每個安置點分配一個序號，生成一個包含所有安置點的序列。

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

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

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

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

2.3 局部搜索算子TRUD

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

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

1）隨機選擇一個回路，找到其中被延誤時間最長的安置點。

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

3）將兩個安置點交由對方的車輛負責(zé)配送，若無改進，進入第4）步。

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

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

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

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

2.4 初始化種群

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

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

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

2.5 選擇

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

Pi=Fi / ∑ n i=1 Fi

（8）

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

2.6 交叉算子

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

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

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

1）在兩個染色體中各隨機選擇一個子集，得到集合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}。檢查兩個集合中元素4、6的先后順序是否一致，一致則轉(zhuǎn)到步驟1），否則轉(zhuǎn)到步驟4）。

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

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

3 實驗仿真及分析

3.1 算例描述與實驗設(shè)置

實驗數(shù)據(jù)集包括1個仿真算例和16個來自VRP標(biāo)準數(shù)據(jù)集的算例，其中仿真算例根據(jù)M地區(qū)地理條件模擬產(chǎn)生。

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

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

3.2 結(jié)果分析

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

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

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

其中：序號為0的點是出發(fā)點物資倉庫;對于提前到達或準時到達的安置點，其延誤時間均記為0;

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

表3中對比了四種算法的物資配送延誤時間。

對比算法包括：

先來先服務(wù)（First Come First Served， FCFS）算法，表示按照安置點報告的順序進行配送;

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

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

GA為TRUD-GA去除改進初始解和變異算子后的算法，用以驗證本文加入算子TRUD的有效性。

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

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

為列名的四列數(shù)據(jù)分別表示該算法求得的每一個安置點的延誤時間。對于提前到達或準時到達的安置點，其延誤時間均記為0。序號為0的點是出發(fā)點物資倉庫。X、Y單位為km，URG、FCFS、URGS、GA、TRUD-GA單位為min。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語

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

參考文獻

[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]??徐浩，李佳川，韓傳峰.震后運速受限條件下的多目標(biāo)定位：路徑問題研究[J].管理工程學(xué)報，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]?張國富，王永奇，蘇兆品，等.應(yīng)急救援物資多目標(biāo)分配與調(diào)度問題建模與求解[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]??石建力，張錦.需求點隨機的分批配送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]???易云飛，蔡永樂，董文永，等.求解帶用戶滿意度的多目標(biāo)實時車輛路徑問題的改進伊藤算法[J].電子學(xué)報，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]?任錫德，朱建明，王晶，等.考慮均衡性的不確定時間車輛調(diào)度問題研究[J].運籌與管理，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]??文仁強，鐘少波，袁宏永，等.應(yīng)急資源多目標(biāo)優(yōu)化調(diào)度模型與多蟻群優(yōu)化算法研究[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é)報，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].運籌與管理，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.）