靳鵬 張歆悅

摘? 要：針對(duì)城市交通路網(wǎng)存在時(shí)變性和隨機(jī)性的特點(diǎn)，文章研究了隨機(jī)時(shí)變下帶時(shí)間窗的取送貨車(chē)輛路徑問(wèn)題，提出了隨機(jī)時(shí)變車(chē)輛行駛時(shí)間的魯棒優(yōu)化方法，考慮車(chē)載限制和客戶(hù)服務(wù)時(shí)間窗的約束，以總行駛時(shí)間最小化為目標(biāo)，建立混合整數(shù)規(guī)劃模型，并提出兩階段的混合遺傳模擬退火算法。使用三行染色體編碼方式、多段多點(diǎn)交叉算子和修復(fù)算子的遺傳算法獲得較優(yōu)解，使用模擬退火算法進(jìn)行優(yōu)化，獲得高質(zhì)量的解決方案。最后，基于PDPTW標(biāo)準(zhǔn)數(shù)據(jù)集和STDPDPTW測(cè)試算例對(duì)文章所提出的算法進(jìn)行了大量的數(shù)值實(shí)驗(yàn)，充分驗(yàn)證了模型及算法的有效性。

關(guān)鍵詞：車(chē)輛路徑問(wèn)題;隨機(jī)時(shí)變路網(wǎng);遺傳模擬退火算法;時(shí)間窗

中圖分類(lèi)號(hào)：U116? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

Abstract： Based on the time-varying and randomness of urban traffic network characteristics， this paper studies stochastic time-dependent pickup and delivery problem with time windows， puts forward the robust optimization method of random time-varying traffic time. Considering the vehicle restrictions and customer service time window constraints， a mixed integer programming model for minimizing total travel time is set up， and a two-stage hybrid genetic simulated annealing algorithm was proposed. The genetic algorithm used three-line chromosome coding， multi-segment multi-point crossover operator and repair operator was used to obtain a better solution， subsequently， the simulated annealing algorithm was used to optimize the solution to obtain a high quality solution. Finally， based on PDPTW benchmark dataset and STDPDPTW test examples， a large number of numerical experiments are carried out to verify the effectiveness of the proposed model and algorithm.

Key words： vehicle routing problem; stochastic time-dependent network; hybrid genetic simulated annealing algorithm; time windows

0? 引? 言

車(chē)輛路徑問(wèn)題（Vehicle Routing Problem，VRP）自提出以來(lái)，一直是物流組織優(yōu)化領(lǐng)域中的研究難點(diǎn)。在實(shí)際物流系統(tǒng)中，為滿(mǎn)足取貨或配送及服務(wù)時(shí)間窗限制的客戶(hù)需求，帶時(shí)間窗的取送貨車(chē)輛路徑問(wèn)題（Pickup and Delivery with Time

Windows，PDPTW）逐漸受到眾多學(xué)者的關(guān)注。然而，近年來(lái)城市交通日趨擁堵，受交通管制、交通事故等不確定因素的影響，城市交通路網(wǎng)存在一定的時(shí)變性和隨機(jī)性[1]，車(chē)輛的行駛速度是時(shí)變的[2]。在此背景下，研究隨機(jī)時(shí)變下帶時(shí)間窗的取送貨車(chē)輛路徑問(wèn)題（Stochastic Time-dependent Pickup and Delivery with Time Windows， STDPDPTW）具有重要意義。

帶時(shí)間窗的取送貨車(chē)輛路徑問(wèn)題（PDPTW）是經(jīng)典車(chē)輛路徑問(wèn)題（Vehicle Routing Problem， VRP）的擴(kuò)展，屬于NP-hard問(wèn)題，最早由Wilson[3]提出。Bent等人[4]首次提出兩階段混合算法，第一階段選用模擬退火算法優(yōu)化路徑數(shù)量，第二階段選用大鄰域搜索算法降低路徑成本，有效求解PDPTW問(wèn)題。Al Chami等人[5]使用貪婪隨機(jī)的自適應(yīng)搜索方法生成初始解，后使用遺傳算法優(yōu)化解決方案，有效提高求解PDPTW問(wèn)題的效率。目前用于求解帶時(shí)間窗的取送貨車(chē)輛路徑問(wèn)題的啟發(fā)式算法主要包括遺傳算法[6]、模擬退火算法[7]、自適應(yīng)大鄰域搜索算法[8]、蟻群算法[9]等。

然而，城市化進(jìn)程逐步加快，道路交通超負(fù)荷運(yùn)轉(zhuǎn)，加之交通管制和交通事故等因素的影響，在物流運(yùn)輸過(guò)程中，考慮車(chē)輛行駛時(shí)間的時(shí)變性和隨機(jī)性更貼近實(shí)際。隨機(jī)時(shí)變下車(chē)輛路徑問(wèn)題（Stochastic Time-dependent Vehicle Routing Problem， STDVRP）最早由隨機(jī)時(shí)變最優(yōu)路徑問(wèn)題（Stochastic Time-dependent Optimal Path Problem， STDOPP）發(fā)展而來(lái)，Hang等[10]以行駛時(shí)間負(fù)效用函數(shù)計(jì)算隨機(jī)時(shí)變路徑行駛時(shí)間，隨機(jī)路網(wǎng)中的最佳路徑受隨機(jī)依賴(lài)性影響。張春苗[11]指出以車(chē)輛行駛時(shí)間的概率分布為基礎(chǔ)，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)復(fù)雜，算法求解時(shí)間復(fù)雜度隨路網(wǎng)規(guī)模增大呈指數(shù)增長(zhǎng)。由Sim[12]提出魯棒優(yōu)化模型，將隨機(jī)時(shí)變路網(wǎng)轉(zhuǎn)化為確定型時(shí)變，曹慧等[13]將該方法應(yīng)用于隨機(jī)時(shí)變路網(wǎng)的最優(yōu)路徑問(wèn)題，結(jié)果證明滿(mǎn)足隨機(jī)一致性條件，車(chē)輛行駛時(shí)間可依據(jù)確定型時(shí)變路網(wǎng)計(jì)算。Duan[14]也指出魯棒優(yōu)化時(shí)間模型適用于實(shí)際的道路網(wǎng)絡(luò)。段征宇等人[1]建立STDVRP魯棒優(yōu)化模型，考慮客戶(hù)的時(shí)間窗約束，增大了求解的復(fù)雜度，并設(shè)計(jì)改進(jìn)蟻群算法進(jìn)行有效求解。

綜上，多數(shù)文獻(xiàn)獨(dú)立研究STDVRP和PDPTW，同時(shí)考慮隨機(jī)時(shí)變、時(shí)間窗約束和取送貨的車(chē)輛路徑問(wèn)題的研究較少，本文建立了隨機(jī)時(shí)變下帶時(shí)間窗的取送貨車(chē)輛路徑問(wèn)題（STDPDPTW）模型，基于魯棒優(yōu)化方法計(jì)算隨機(jī)時(shí)變路網(wǎng)下車(chē)輛行駛時(shí)間，為快速且按時(shí)滿(mǎn)足客戶(hù)需求，以車(chē)輛總行駛時(shí)間最小化為目標(biāo)函數(shù)建立混合整數(shù)規(guī)劃模型，并設(shè)計(jì)一種混合遺傳模擬退火算法進(jìn)行求解。

1? 問(wèn)題描述與數(shù)學(xué)模型

1.1? 問(wèn)題描述。STDPDPTW研究一定數(shù)量的車(chē)輛從地理位置不同的車(chē)場(chǎng)出發(fā)在客戶(hù)能接受的時(shí)間范圍內(nèi)為客戶(hù)提供取貨或配送服務(wù)，受道路類(lèi)型和行駛時(shí)段的影響，同一路段可能具有不同的行駛速度，制定總行駛時(shí)間最小的路徑規(guī)劃方案。對(duì)研究問(wèn)題做如下描述：（1）配送網(wǎng)絡(luò)中有多個(gè)車(chē)場(chǎng)，每個(gè)車(chē)場(chǎng)有一定數(shù)量相同類(lèi)型的運(yùn)輸車(chē)輛，每輛車(chē)的起止點(diǎn)為同一車(chē)場(chǎng);（2）每個(gè)客戶(hù)僅由一輛車(chē)進(jìn)行服務(wù);（3）客戶(hù)點(diǎn)的需求量不大于車(chē)輛載重量;（4）每個(gè)客戶(hù)點(diǎn)有服務(wù)時(shí)間窗的要求，車(chē)輛可早于最早開(kāi)始服務(wù)時(shí)間到達(dá)客戶(hù)點(diǎn)，等待直至最早開(kāi)始服務(wù)時(shí)間進(jìn)行服務(wù)，但不能晚于最遲開(kāi)始時(shí)間到達(dá)。

1.2? 符號(hào)及決策變量。配送網(wǎng)絡(luò)圖為G=V，A;節(jié)點(diǎn)集合為V，V=P∪D，配送中心節(jié)點(diǎn)集合為D=1，2，…，n，客戶(hù)點(diǎn)集合為P=P∪P，取貨點(diǎn)集合為P=n+1， n+2， …， n+m，送貨點(diǎn)集合為P=n+m+1， n+m+2， …， n+2m;弧集為A，其中表示節(jié)點(diǎn)i，j間的弧i，j∈V;一個(gè)時(shí)域的分段集合為T(mén)，T=τ

，τ

，…，

τ，…，

τ，時(shí)域分段總數(shù)為η;客戶(hù)點(diǎn)i的需求量為q;車(chē)輛集合為K，k∈K;車(chē)輛k能夠承載的最大容量為Q;客戶(hù)點(diǎn)i的時(shí)間窗為

a，

b，客戶(hù)點(diǎn)i的最早開(kāi)始服務(wù)時(shí)間為a，客戶(hù)點(diǎn)i的最遲開(kāi)始服務(wù)時(shí)間為b;客戶(hù)點(diǎn)i的服務(wù)時(shí)間為l;車(chē)輛k到達(dá)節(jié)點(diǎn)i的時(shí)間為e;車(chē)輛k到達(dá)節(jié)點(diǎn)i的開(kāi)始服務(wù)時(shí)間為s;車(chē)輛k離開(kāi)節(jié)點(diǎn)i的出發(fā)時(shí)刻為λ;車(chē)輛k到達(dá)節(jié)點(diǎn)i之后的承載貨物量為w;節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的距離為d;車(chē)輛k以出發(fā)時(shí)刻λ從節(jié)點(diǎn)i到節(jié)點(diǎn)j之間的時(shí)間為t，t≥0。

x=

1.3? 問(wèn)題建模。以服務(wù)完所有客戶(hù)所需的總行駛時(shí)間最小化為目標(biāo)函數(shù)，則隨機(jī)時(shí)變下帶時(shí)間窗的取送貨車(chē)輛路徑問(wèn)題的數(shù)學(xué)模型建立如下：

mintx? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （1）

約束條件如下：

x=1， ?j∈V， k∈K， τ∈T? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（2）

x=x， ?j∈P， k∈K， τ∈T? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（3）

x≤1， ?o∈D， i∈P， τ∈T? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （4）

e≤s， ?k∈K， i∈P? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（5）

a≤s≤b， ?k∈K， i∈P? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （6）

x-x=0， ?k∈K， i∈P， τ∈T? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（7）

x-x=0， ?k∈K， o∈D， τ∈T? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （8）

s+t≤Sn+m+i， k≤Sn+m+i， k， ?k∈K， i∈P， τ∈T? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （9）

w=w=0， ?k∈K? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（10）

0≤w≤Q， ?k∈K， i∈P? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（11）

x

w

+q

-w≤0， ?k∈K， i∈V， j∈P， τ∈T? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （12）

x

w

-q

-w≥0， ?k∈K， i∈P， i∈P， τ∈T? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （13）

x∈0，1， ?i∈V， j∈V， k∈K， i≠j， τ∈T? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （14）

式（1）表示最小化車(chē)輛總行駛時(shí)間;式（2）表示每個(gè)客戶(hù)點(diǎn)僅由一輛車(chē)進(jìn)行訪問(wèn);式（3）表示每個(gè)客戶(hù)點(diǎn)的流量平衡約束;式（4）表示每輛車(chē)僅使用一次;式（5）、式（6）表示車(chē)輛到達(dá)客戶(hù)點(diǎn)的時(shí)間和客戶(hù)點(diǎn)的開(kāi)始服務(wù)時(shí)間之間的關(guān)系;式（7）表示一個(gè)訂單包含的取貨和送貨請(qǐng)求均由同一輛車(chē)提供服務(wù);式（8）表示車(chē)輛從車(chē)場(chǎng)出發(fā)完成任務(wù)后并返回該車(chē)場(chǎng);式（9）表示完成客戶(hù)點(diǎn)i的取貨時(shí)間早于完成客戶(hù)點(diǎn)n+m+i的送貨時(shí)間;式（10）表示車(chē)輛從車(chē)場(chǎng)出發(fā)以及返回車(chē)場(chǎng)承載貨物量均為0;式（11）表示車(chē)輛在執(zhí)行任務(wù)過(guò)程中承載貨物容量不能超過(guò)車(chē)輛容量限制;式（12）、式（13）表示保證車(chē)輛離開(kāi)上一節(jié)點(diǎn)到下一節(jié)點(diǎn)之間容量的一致性，車(chē)輛在客戶(hù)點(diǎn)之間承載容量的變化;式（14）表示決策變量取值約束。

1.4? 時(shí)變路網(wǎng)下車(chē)輛行駛時(shí)間計(jì)算方法。在實(shí)際交通中，車(chē)輛在不同時(shí)間段內(nèi)道路的擁堵情況不同，因而車(chē)輛的行駛速度存在差異，考慮實(shí)際生活中城市路段早晚高峰的情況，車(chē)輛的行駛速度不是階躍變化，而是更近似平滑變化。將一天的工作時(shí)間等分為η個(gè)分段，改進(jìn)Figliozzi[15]的時(shí)間依賴(lài)函數(shù)，使用平滑變化的速度時(shí)間函數(shù)，如圖1表示車(chē)輛的行駛速度時(shí)間函數(shù)。

在不同的時(shí)間分段，車(chē)輛的行駛速度為勻速運(yùn)動(dòng)或勻變速運(yùn)動(dòng)，車(chē)輛行駛具有加速度，設(shè)計(jì)一種計(jì)算時(shí)間分段τ時(shí)段范圍為（ts，te]內(nèi)的車(chē)輛k以時(shí)刻λ從節(jié)點(diǎn)i到節(jié)點(diǎn)j的行駛時(shí)間t計(jì)算方法，步驟如下：

輸入：車(chē)輛k離開(kāi)節(jié)點(diǎn)i的出發(fā)時(shí)刻λ，時(shí)間分段τ，時(shí)段范圍（ts，te]，節(jié)點(diǎn)i與節(jié)點(diǎn)j的距離d。

輸出：從節(jié)點(diǎn)i到節(jié)點(diǎn)j的行駛時(shí)間t。

Step1：設(shè)置出發(fā)時(shí)刻λ=λ，車(chē)輛待行駛距離d=d;

Step2：行駛時(shí)間計(jì)算。如果時(shí)間分段τ的加速度a為0，當(dāng)前時(shí)間分段的行駛速度v，到達(dá)下一節(jié)點(diǎn)的時(shí)間為T(mén)e=λ

+，行駛時(shí)間為t=;否則，到達(dá)下一節(jié)點(diǎn)的時(shí)間為T(mén)e=λ+，行駛時(shí)間為T(mén)=;

Step3：時(shí)間分段判斷。如果Te屬于時(shí)間分段τ，則t=t，輸出從節(jié)點(diǎn)i到節(jié)點(diǎn)j的行駛時(shí)間t;否則，轉(zhuǎn)Step4;

Step4：更新距離計(jì)算。如果時(shí)間分段τ的加速度a為0，則更新車(chē)輛待行駛距離d=d-

te-

λv，出發(fā)時(shí)刻λ=te，轉(zhuǎn)Step2;否則，更新車(chē)輛待行駛距離d=d-

v

te-

λ

+，出發(fā)時(shí)刻λ=te，轉(zhuǎn)Step2。

1.5? 隨機(jī)時(shí)變車(chē)輛行駛時(shí)間的魯棒優(yōu)化。隨機(jī)時(shí)變路網(wǎng)的車(chē)輛行駛時(shí)間可以通過(guò)路段概率分布函數(shù)以及期望估算模型進(jìn)行優(yōu)化[16]，然而車(chē)輛必須在客戶(hù)規(guī)定的時(shí)間窗內(nèi)進(jìn)行服務(wù)，完成所有客戶(hù)的需求，而不是以一定概率進(jìn)行滿(mǎn)足。因此，選用最大最小準(zhǔn)則作為車(chē)輛行駛時(shí)間的魯棒優(yōu)化方法[17]，對(duì)于車(chē)輛k以時(shí)刻λ從節(jié)點(diǎn)i到節(jié)點(diǎn)j的最壞情況發(fā)生，從最壞的情況中找到最優(yōu)路徑的行駛時(shí)間為：

t=minf

x，

λ=minmax

ε

+u

y=min

ε+

θ

y? ? ? ? ? ? ? ? ? ? ?（15）

在式（15）中，χ為從節(jié)點(diǎn)i到節(jié)點(diǎn)j的可行路徑;d為路徑χ中的有向路段

d∈

χ;ε為時(shí)間分段τ內(nèi)從節(jié)點(diǎn)α到節(jié)點(diǎn)β的確定行駛時(shí)間;y為在時(shí)間分段τ內(nèi)車(chē)輛經(jīng)過(guò)路段d，值為1，否則為0;u為時(shí)間分段τ內(nèi)經(jīng)過(guò)路段d的行駛時(shí)間波動(dòng)范圍0，

θ的隨機(jī)變量。隨機(jī)時(shí)變路網(wǎng)中，路段d在時(shí)間分段τ內(nèi)最大行駛時(shí)間為確定值ε+θ，根據(jù)最大最小準(zhǔn)則，兩節(jié)點(diǎn)之間的行駛時(shí)間可魯棒為確定的時(shí)間，則隨機(jī)時(shí)變路網(wǎng)轉(zhuǎn)換為確定型時(shí)變路網(wǎng)。

2? 遺傳模擬退火算法設(shè)計(jì)

遺傳算法通過(guò)適應(yīng)度函數(shù)對(duì)搜索空間中的多個(gè)解進(jìn)行評(píng)估，能夠快速搜索到新解，適用于本文組合優(yōu)化問(wèn)題的求解[6]，但后期搜索能力減弱致使該算法易過(guò)早收斂。本文針對(duì)問(wèn)題特點(diǎn)和遺傳算法的不足，結(jié)合模擬退火算法能有效跳出局部循環(huán)的特點(diǎn)，提出了一種高效求解STDPDPTW模型的混合遺傳模擬退火算法（Hybrid Genetic Simulated Annealing Algorithm， HGSA）。

2.1? 染色體編碼方式。本文設(shè)計(jì)了一種三行染色體編碼方式，染色體的第一行為車(chē)輛訪問(wèn)的客戶(hù)點(diǎn)，第二行為與第一行對(duì)應(yīng)的車(chē)輛編號(hào)，第三行為客戶(hù)點(diǎn)的需求類(lèi)型，1為取貨點(diǎn)，-1為送貨點(diǎn)，0為車(chē)場(chǎng)。每條染色體的編碼方式如圖2所示，以8個(gè)客戶(hù)點(diǎn)為例，車(chē)輛1的路徑為D-8-3-1-5-D，車(chē)輛2的路徑為D-2-4-7-6-D。

2.2? 初始種群的生成。根據(jù)客戶(hù)點(diǎn)的需求類(lèi)型和車(chē)輛的容量約束，按照以下5個(gè)步驟生成初始種群：

Step1：從客戶(hù)點(diǎn)集合P中隨機(jī)選擇一個(gè)取貨點(diǎn)和一個(gè)送貨點(diǎn)進(jìn)行兩兩組合形成待插入客戶(hù)點(diǎn)序列P;

Step2：根據(jù)車(chē)輛容量約束，按待插入客戶(hù)點(diǎn)序列P順序?yàn)檐?chē)輛劃分客戶(hù)點(diǎn)，得到車(chē)輛所訪問(wèn)的客戶(hù)點(diǎn)序列H，形成染色體的第一行編碼;

Step3：在每輛車(chē)所訪問(wèn)的客戶(hù)點(diǎn)序列H的最前面和最后面加入該車(chē)輛對(duì)應(yīng)的車(chē)場(chǎng)編號(hào)，用來(lái)表示車(chē)輛出發(fā)的起點(diǎn)和返回的終點(diǎn)，得到每輛車(chē)輛的初始路徑訪問(wèn)的客戶(hù)點(diǎn)序列P，形成染色體的第一行編碼;

Step4：在每輛車(chē)的初始路徑的編碼的第二行添加對(duì)應(yīng)的車(chē)輛編號(hào)，在第三行添加客戶(hù)點(diǎn)對(duì)應(yīng)的任務(wù)類(lèi)型編號(hào)，形成一條完整的染色體，如圖3所示;

Step5：根據(jù)預(yù)設(shè)的種群規(guī)模N重復(fù)Step1～Step4，得到初始種群。

2.3? 多段多點(diǎn)交叉算子。多點(diǎn)交叉操作不僅增加染色體的多樣性，而且能夠有效避免個(gè)體過(guò)早收斂，根據(jù)染色體編碼方式的特點(diǎn)，染色體中的每一段代表一輛車(chē)訪問(wèn)的客戶(hù)點(diǎn)序列，本文設(shè)計(jì)了多段多點(diǎn)交叉算子，算法步驟如下：

Step1：采用輪盤(pán)賭方式從種群中選擇兩條染色體作為父代染色體F和F;

Step2：根據(jù)染色體第二行的車(chē)輛編號(hào)將父代染色體F和F分別分成K段;

Step3：分別從父代染色體F和F中相同車(chē)輛編號(hào)的分段F和F中隨機(jī)選擇連續(xù)的多個(gè)基因進(jìn)行交換;

Step4：根據(jù)車(chē)輛數(shù)量K重復(fù)Step3，完成所有分段的交叉操作，并進(jìn)行拼接得到兩條染色體F和F，交叉操作如圖4所示。

2.4? 修復(fù)算子。使用多段多點(diǎn)交叉方式后的染色體可能存在部分客戶(hù)點(diǎn)缺失和重復(fù)的問(wèn)題，則需要將未訪問(wèn)的客戶(hù)點(diǎn)插入到路徑規(guī)劃方案中，且為縮短車(chē)輛的行駛時(shí)間，加快全局尋優(yōu)過(guò)程，設(shè)計(jì)了修復(fù)算子，算法步驟如下：

Step1：從交叉操作后的染色體中標(biāo)記出所有重復(fù)訪問(wèn)的客戶(hù)點(diǎn)，利用公式（16）依次計(jì)算染色體中重復(fù)點(diǎn)位上一位客戶(hù)點(diǎn)n到達(dá)該客戶(hù)點(diǎn)n的行駛時(shí)間與等待時(shí)間之和st;

Step2：重復(fù)訪問(wèn)客戶(hù)點(diǎn)中相同編號(hào)的客戶(hù)點(diǎn)兩兩比較st的大小，保留st較小的客戶(hù)點(diǎn)，并去除標(biāo)記;

Step3：利用公式（17）從未訪問(wèn)客戶(hù)點(diǎn)集合N中選擇客戶(hù)點(diǎn)依次替換標(biāo)記出的重復(fù)訪問(wèn)客戶(hù)點(diǎn)，生成修復(fù)后的新子代個(gè)體。

st=t+max

a

-e，0? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （16）

=arg

t+max

a

-e，0? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （17）

式（16）表示染色體中重復(fù)點(diǎn)位上一位客戶(hù)點(diǎn)n到達(dá)該客戶(hù)點(diǎn)n的行駛時(shí)間與等待時(shí)間之和。式（17）表示從未訪問(wèn)客戶(hù)點(diǎn)集合N中選擇待插入客戶(hù)點(diǎn)n，以依次待替換的染色體中重復(fù)點(diǎn)位的上一位客戶(hù)點(diǎn)n到達(dá)未插入的客戶(hù)點(diǎn)n之間的行駛時(shí)間和等待時(shí)間最小化為替換客戶(hù)點(diǎn)的選擇準(zhǔn)則。

2.5? 變異算子。變異操作有助于提升該算法的全局搜索能力，避免陷入局部最優(yōu)的困境。本文選擇兩點(diǎn)交換變異方式，隨機(jī)從染色體中選擇兩個(gè)客戶(hù)點(diǎn)進(jìn)行位置交換，得到新的子代染色體，具體操作如圖5所示。

2.6? 種群更新。通過(guò)選擇部分父代種群中的精英染色體替代新產(chǎn)生的子代種群中相同數(shù)量的染色體來(lái)完成種群更新操作，選擇替代染色體的數(shù)量為：N=N×1-Gap，其中N為種群規(guī)模，Gap為代溝。具體操作如下：一個(gè)新的種群由父代種群中適應(yīng)度值前N位的染色體和子代種群中前

N

-N位的染色體組成，作為遺傳算法下一輪迭代的新種群。

2.7? 鄰域結(jié)構(gòu)。鄰域搜索操作可以擴(kuò)大搜索范圍增加解的多樣性，避免算法陷入局部最優(yōu)，增大算法找到全局最優(yōu)解的可能性。本文采用了四種鄰域搜索算子，包括逆序搜索算子、單點(diǎn)交換算子、合并搜索算子和兩點(diǎn)交換算子，鄰域算子操作如下：（1）逆序搜索算子：隨機(jī)選擇兩個(gè)客戶(hù)點(diǎn)進(jìn)行交換，并將兩個(gè)客戶(hù)點(diǎn)中的客戶(hù)點(diǎn)反轉(zhuǎn)逆序排列，如圖6（a）所示。（2）單點(diǎn)交換算子：從原路徑中隨機(jī)選擇客戶(hù)點(diǎn)移除，插入到其它路徑中，如圖6（b）所示。（3）合并搜索算子：隨機(jī)選擇一條路徑，將該路徑上的客戶(hù)點(diǎn)插入到其它路徑中，如圖6（c）所示。（4）兩點(diǎn)交換算子：從兩條不同的路徑中分別各選擇一個(gè)客戶(hù)點(diǎn)，并交換他們的位置，如圖6（d）所示。

2.8? 混合遺傳模擬退火算法求解步驟?；旌线z傳模擬退火算法將遺傳算法與模擬退火算法結(jié)合，通過(guò)遺傳算法得到較優(yōu)解，以此作為模擬退火算法的初始解，再通過(guò)鄰域搜索最終得到近似最優(yōu)路徑方案。具體算法步驟如下：

Step1：初始化混合遺傳模擬退火算法的參數(shù)，種群規(guī)模N、代溝Gap、交叉概率P、變異概率P、初始溫度T、終止溫度T、步長(zhǎng)L、冷卻速率R;

Step2：種群初始化，獲得車(chē)輛初始路徑序列方案集合;

Step3：通過(guò)式（1）計(jì)算染色體的適應(yīng)度;

Step4：根據(jù)交叉概率P對(duì)選擇的兩條父代染色體進(jìn)行交叉操作生成交叉后的子代染色體;

Step5：對(duì)交叉后的染色體使用修復(fù)算子進(jìn)行修復(fù)，補(bǔ)全因交叉過(guò)程缺失的客戶(hù)點(diǎn);

Step6：根據(jù)變異概率P對(duì)交叉后的子代染色體進(jìn)行變異操作生成變異后的子代染色體;

Step7：種群更新操作;

Step8：判斷種群中最優(yōu)解的適應(yīng)度值連續(xù)10代是否下降，若沒(méi)有下降，則輸出遺傳算法的當(dāng)前最優(yōu)解S，轉(zhuǎn)Step9，否則，轉(zhuǎn)Step4;

Step9：初始化當(dāng)前溫度T=T，當(dāng)前溫度下迭代次數(shù)L=0，將Step8輸出的當(dāng)前最優(yōu)解S作為當(dāng)前解S;

Step10：如果溫度T>T，轉(zhuǎn)Step11，否則，輸出算法終止輸出最優(yōu)解;

Step11：如果迭代次數(shù)L

Step12：4種鄰域算子隨機(jī)協(xié)作生成鄰域解S;

Step13：如果鄰域解S優(yōu)于當(dāng)前解S，則用鄰域解S替代當(dāng)前解S，否則，轉(zhuǎn)Step14;

Step14：如果e>δ，δ為0，1的隨機(jī)數(shù)據(jù)，則用鄰域解S替代當(dāng)前解S，否則，保留S，轉(zhuǎn)Step11。

3? 實(shí)驗(yàn)分析

本文所有實(shí)驗(yàn)使用Java語(yǔ)言進(jìn)行編寫(xiě)，eclipse2018-12的編程環(huán)境，Windows 10操作系統(tǒng)，Intel Core i7-7700 CPU@3.60

GHz 16.0 GB的運(yùn)行環(huán)境。

3.1? 參數(shù)設(shè)置。通過(guò)合理的參數(shù)設(shè)置能夠有效提高算法的求解質(zhì)量，考慮到實(shí)際應(yīng)用需求，選取多個(gè)不同算例，在合理的時(shí)間范圍內(nèi)，采用控制變量法，最終確定一個(gè)最佳的參數(shù)組合。首先根據(jù)經(jīng)驗(yàn)確定參數(shù)的測(cè)試區(qū)間，再通過(guò)更改參數(shù)組合進(jìn)行多組數(shù)值實(shí)驗(yàn)，記錄實(shí)驗(yàn)結(jié)果和CPU運(yùn)行時(shí)間，最終確定HGSA參數(shù)設(shè)置最佳組合如表1所示。

3.2? PDPTW算例。目前關(guān)于STDPDPTW研究所進(jìn)行的實(shí)驗(yàn)并沒(méi)有公認(rèn)的數(shù)據(jù)集，且STDPDPTW是在經(jīng)典的PDPTW問(wèn)題中增加部分約束形成的衍生問(wèn)題。因此，選取Li & Lim PDPTW標(biāo)準(zhǔn)數(shù)據(jù)集pdp_100[18]的56個(gè)算例進(jìn)行數(shù)值實(shí)驗(yàn)，驗(yàn)證本文算法的有效性。

本實(shí)驗(yàn)選用Li & Lim PDPTW標(biāo)準(zhǔn)數(shù)據(jù)集中的56個(gè)算例實(shí)驗(yàn)，算例包括LC數(shù)據(jù)集（地點(diǎn)規(guī)則分布）、LR數(shù)據(jù)集（地點(diǎn)隨機(jī)分布）和LRC數(shù)據(jù)集（地點(diǎn)混合分布）。所有車(chē)輛行駛道路類(lèi)型相同，且以速度為1的恒定速度行駛，以車(chē)輛總行駛距離為優(yōu)化目標(biāo)。表2記錄了PDPTW的已知最好解R、HGSA算法的總距離S及其運(yùn)算時(shí)間，Gap表示R與S之間的差值百分比，Gap=

R

-S/S。

由表2中數(shù)據(jù)可知，HGSA算法更新了5個(gè)PDPTW算例分別為lc109、lc203、lr108、lrc106和lrc204的已知最好解。在其它的51個(gè)PDPTW算例中，HGSA算法的求解結(jié)果劣于算例已知最好解，但與已知最好解的差距均值在1%之內(nèi)，實(shí)驗(yàn)數(shù)據(jù)說(shuō)明了HGSA算法求解PDPTW的有效性。

3.3? STDPDPTW算例?；贚i & Lim基準(zhǔn)測(cè)試實(shí)例，根據(jù)實(shí)例規(guī)模將單一車(chē)場(chǎng)擴(kuò)充為5個(gè)車(chē)場(chǎng)，每個(gè)車(chē)場(chǎng)位置隨機(jī)生成，且每個(gè)車(chē)場(chǎng)分配5輛車(chē)用于完成任務(wù)，并增加路段中車(chē)輛行駛速度的波動(dòng)范圍，構(gòu)建STDPDPTW測(cè)試實(shí)例。依據(jù)城市道路通行情況，將道路分為五種類(lèi)型，總服務(wù)時(shí)域分為9個(gè)等分的時(shí)間分段，依據(jù)圖1將車(chē)輛的行駛速度時(shí)間函數(shù)設(shè)置為連續(xù)函數(shù)，不同的時(shí)段車(chē)輛的最高行駛速度和最低行駛速度不同，路段的道路類(lèi)型由式（18）判斷：

typei，j=modi+j， 5+1? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（18）

式（18）中，mod為取余計(jì)算，例如從7號(hào)節(jié)點(diǎn)到9號(hào)節(jié)點(diǎn)的道路類(lèi)型為2。

表3表示不同道路類(lèi)型在9個(gè)等分的時(shí)間分段中車(chē)輛行駛速度的變化范圍。對(duì)各道路類(lèi)型和時(shí)間分段設(shè)置高、中、低三種波動(dòng)范圍，對(duì)于時(shí)間分段τ、τ和τ中行駛速度增加±15%的波動(dòng)范圍，對(duì)于時(shí)間分段τ、τ和τ中行駛速度增加±20%的波動(dòng)范圍，對(duì)于時(shí)間分段τ、τ和τ中行駛速度增加±10%的波動(dòng)范圍。根據(jù)行駛速度波動(dòng)范圍通過(guò)隨機(jī)時(shí)變車(chē)輛行駛時(shí)間的魯棒優(yōu)化方法將隨機(jī)時(shí)變路網(wǎng)轉(zhuǎn)化為確定型路網(wǎng)。

表4記錄了隨機(jī)選取的10個(gè)STDPDPTW算例的實(shí)驗(yàn)結(jié)果，在相同實(shí)驗(yàn)條件下每個(gè)算例運(yùn)行20次。其中，20次運(yùn)行結(jié)果的最大值記錄在C列中，平均值記錄在C列中，最小值記錄在C列中，20次運(yùn)行的平均運(yùn)行時(shí)間記錄在CPU列中，Gap表示C與C之間的差值百分比，Gap表示C與C之間的差值百分比。其中，Gap=C

-

C/C，Gap

=C

-

C/C。

由表4數(shù)據(jù)可知，考慮車(chē)輛行駛時(shí)間的時(shí)變性和隨機(jī)性，在車(chē)輛數(shù)量有限的情況下，通過(guò)優(yōu)化車(chē)輛的出發(fā)時(shí)間和出發(fā)的車(chē)場(chǎng)位置可以縮短完成配送任務(wù)的時(shí)間。10個(gè)STPDPTW算例均在較短的時(shí)間內(nèi)獲得近似最優(yōu)解，將引入多段多點(diǎn)交叉算子和修復(fù)算子的遺傳算法與模擬退火算法結(jié)合，有效提高了局部尋優(yōu)能力和收斂速度。另外，表4的C與C之間的差值百分比的平均值僅相差2.01%，C與C之間的差值百分比的平均值僅相差1.68%，表明HGSA具有較強(qiáng)的穩(wěn)定性和尋優(yōu)能力。

4? 結(jié)? 論

本文考慮城市交通擁堵、交通管制等不確定因素的影響，建立了隨機(jī)時(shí)變下帶時(shí)間窗的取送貨車(chē)輛路徑問(wèn)題模型，提出考慮車(chē)輛加速度的行駛時(shí)間計(jì)算方式，運(yùn)用隨機(jī)時(shí)變車(chē)輛行駛時(shí)間的魯棒優(yōu)化方法將隨機(jī)性時(shí)變轉(zhuǎn)化為確定型時(shí)變，根據(jù)

STDPDPTW模型特點(diǎn)，設(shè)計(jì)了兩階段的混合遺傳模擬退火算法，引入多段多點(diǎn)交叉算子和修復(fù)算子，保證了前期迭代的收斂速度后使用多領(lǐng)域搜索算子，提高了算法的搜索效率。通過(guò)標(biāo)準(zhǔn)數(shù)據(jù)集進(jìn)行驗(yàn)證，HGSA算法更新了56個(gè)PDPTW算例中5個(gè)已知最好解，其余算例與已知最好解的差距均值在1%之內(nèi)，同時(shí)STDPDPTW算例表明，HGSA算法求解STDPDPTW具有較強(qiáng)的穩(wěn)定性，能有效縮短車(chē)輛的總行駛時(shí)間，降低物流配送成本。

參考文獻(xiàn)：

[1]? 段征宇，雷曾翔，孫碩，等. 隨機(jī)時(shí)變車(chē)輛路徑問(wèn)題的多目標(biāo)魯棒優(yōu)化方法[J]. 西南交通大學(xué)學(xué)報(bào)，2019，54（3）：565-572.

[2]? 蔡延光，湯雅連，蔡顥. 時(shí)變路網(wǎng)條件下車(chē)輛路徑問(wèn)題的自適應(yīng)蟻群算法[J]. 計(jì)算機(jī)應(yīng)用研究，2005，32（8）：? 2309-2312.

[3]? Wilson N H M， Weissberg R W， Hauser J. Advanced Dial-a-Ride Algorithms Research Project[Z]. 1976.

[4]? Bent R， Hentenryck P V. A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows[J]. Computers & Operations Research， 2006，33（4）：875-893.

[5]? Al Chami Z， Manier H， Manier M A， et al. An advanced GRASP-HGA combination to solve a multi-period Pickup and Delivery Problem[J]. Expert Systems with Applications， 2018，105：262-272.

[6] 鮑偉，賈江鳴，李湘生，等. 考慮軟時(shí)間窗的多車(chē)型車(chē)輛配送路徑優(yōu)化[J]. 物流科技，2020，43（6）：76-82.

[7] 張凱，靳鵬，崔勇. 帶時(shí)間窗的多車(chē)型需求可拆分?jǐn)埵张渌蛦?wèn)題[J]. 計(jì)算機(jī)工程與應(yīng)用，2021（14）：281-288.

[8]? Naccache S， C?té J F， Coelho L C. The multi-pickup and delivery problem with time windows[J]. European Journal of Operational Research， 2008，269（1）：353-362.

[9]? Tchoupo M N， Yalaoui A， Amodeo L， et al. Ant Colony Optimization Algorithm for Pickup and Delivery Problem with Time Windows[J]. In Optimization and Decision Science： Methodologies and Applications， 2017：181-191.

[10]? Huang H， Gao S. Optimal paths in dynamic networks with dependent random link travel times[J]. Transportation Research Part B： Methodological， 2012，46（5）：579-598.

[11] 張春苗. 時(shí)間依賴(lài)綠色選址—車(chē)輛路徑問(wèn)題及算法研究[D]. 杭州：浙江工業(yè)大學(xué)（博士學(xué)位論文），2020.

[12] Sim M. Robust Optimization[D]. Massachuseetts Institute of Technology， Cambridge， MA， USA， 2004.

[13] 曹慧，段征宇，陳川. 隨機(jī)時(shí)變路網(wǎng)環(huán)境下穩(wěn)健路徑選擇及實(shí)證研究[J]. 交通運(yùn)輸系統(tǒng)工程與信息，2014：14（5）：194-201.

[14]? Duan Zhengyu， Sun Shichao， Sun Shuo， et al. Stochastic time-dependent vehicle routing problem： Mathematical models and ant colony algorithm[J]. Advances in Mechanical Engineering， 2015，7（11）：1-16.

[15]? Andres Figliozzi M. The time dependent vehicle routing problem with time windows： Benchmark problems， an efficient solution algorithm， and solution characteristics[J]. Transportation Research Part E： Logistics and Transportation Review， 2012，48（3）：616-636.

[16]? Kim Y K， Park K， Ko J. A symbiotic evolutionary algorithm for the integration of process planning and job shop scheduling[J]. Computers & Operations Research， 2003，30（8）：1151-1171.

[17] 吳俏. 基于城市路網(wǎng)的行程時(shí)間估計(jì)及預(yù)測(cè)方法研究[D]. 杭州：浙江大學(xué)（碩士學(xué)位論文），2015.

[18]? Li H， Lim A. A Metaheuristic for the Pickup and Delivery Problem with Time Windows[J]. International journal on Artificial Intelligence Tools， 2003，12（2）：173-186.