隨機時變下帶時間窗的 取送貨車輛路徑問題優化研究

靳鵬 張歆悅

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

關鍵詞：車輛路徑問題;隨機時變路網;遺傳模擬退火算法;時間窗

中圖分類號：U116? ? ? 文獻標識碼：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? 引? 言

車輛路徑問題（Vehicle Routing Problem，VRP）自提出以來，一直是物流組織優化領域中的研究難點。在實際物流系統中，為滿足取貨或配送及服務時間窗限制的客戶需求，帶時間窗的取送貨車輛路徑問題（Pickup and Delivery with Time

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

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

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

綜上，多數文獻獨立研究STDVRP和PDPTW，同時考慮隨機時變、時間窗約束和取送貨的車輛路徑問題的研究較少，本文建立了隨機時變下帶時間窗的取送貨車輛路徑問題（STDPDPTW）模型，基于魯棒優化方法計算隨機時變路網下車輛行駛時間，為快速且按時滿足客戶需求，以車輛總行駛時間最小化為目標函數建立混合整數規劃模型，并設計一種混合遺傳模擬退火算法進行求解。

1? 問題描述與數學模型

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

1.2? 符號及決策變量。配送網絡圖為G=V，A;節點集合為V，V=P∪D，配送中心節點集合為D=1，2，…，n，客戶點集合為P=P∪P，取貨點集合為P=n+1， n+2， …， n+m，送貨點集合為P=n+m+1， n+m+2， …， n+2m;弧集為A，其中表示節點i，j間的弧i，j∈V;一個時域的分段集合為T，T=τ

，τ

，…，

τ，…，

τ，時域分段總數為η;客戶點i的需求量為q;車輛集合為K，k∈K;車輛k能夠承載的最大容量為Q;客戶點i的時間窗為

a，

b，客戶點i的最早開始服務時間為a，客戶點i的最遲開始服務時間為b;客戶點i的服務時間為l;車輛k到達節點i的時間為e;車輛k到達節點i的開始服務時間為s;車輛k離開節點i的出發時刻為λ;車輛k到達節點i之后的承載貨物量為w;節點i與節點j之間的距離為d;車輛k以出發時刻λ從節點i到節點j之間的時間為t，t≥0。

x=

1.3? 問題建模。以服務完所有客戶所需的總行駛時間最小化為目標函數，則隨機時變下帶時間窗的取送貨車輛路徑問題的數學模型建立如下：

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）表示最小化車輛總行駛時間;式（2）表示每個客戶點僅由一輛車進行訪問;式（3）表示每個客戶點的流量平衡約束;式（4）表示每輛車僅使用一次;式（5）、式（6）表示車輛到達客戶點的時間和客戶點的開始服務時間之間的關系;式（7）表示一個訂單包含的取貨和送貨請求均由同一輛車提供服務;式（8）表示車輛從車場出發完成任務后并返回該車場;式（9）表示完成客戶點i的取貨時間早于完成客戶點n+m+i的送貨時間;式（10）表示車輛從車場出發以及返回車場承載貨物量均為0;式（11）表示車輛在執行任務過程中承載貨物容量不能超過車輛容量限制;式（12）、式（13）表示保證車輛離開上一節點到下一節點之間容量的一致性，車輛在客戶點之間承載容量的變化;式（14）表示決策變量取值約束。

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

在不同的時間分段，車輛的行駛速度為勻速運動或勻變速運動，車輛行駛具有加速度，設計一種計算時間分段τ時段范圍為（ts，te]內的車輛k以時刻λ從節點i到節點j的行駛時間t計算方法，步驟如下：

輸入：車輛k離開節點i的出發時刻λ，時間分段τ，時段范圍（ts，te]，節點i與節點j的距離d。

輸出：從節點i到節點j的行駛時間t。

Step1：設置出發時刻λ=λ，車輛待行駛距離d=d;

Step2：行駛時間計算。如果時間分段τ的加速度a為0，當前時間分段的行駛速度v，到達下一節點的時間為Te=λ

+，行駛時間為t=;否則，到達下一節點的時間為Te=λ+，行駛時間為T=;

Step3：時間分段判斷。如果Te屬于時間分段τ，則t=t，輸出從節點i到節點j的行駛時間t;否則，轉Step4;

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

te-

λv，出發時刻λ=te，轉Step2;否則，更新車輛待行駛距離d=d-

v

te-

λ

+，出發時刻λ=te，轉Step2。

1.5? 隨機時變車輛行駛時間的魯棒優化。隨機時變路網的車輛行駛時間可以通過路段概率分布函數以及期望估算模型進行優化[16]，然而車輛必須在客戶規定的時間窗內進行服務，完成所有客戶的需求，而不是以一定概率進行滿足。因此，選用最大最小準則作為車輛行駛時間的魯棒優化方法[17]，對于車輛k以時刻λ從節點i到節點j的最壞情況發生，從最壞的情況中找到最優路徑的行駛時間為：

t=minf

x，

λ=minmax

ε

+u

y=min

ε+

θ

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

在式（15）中，χ為從節點i到節點j的可行路徑;d為路徑χ中的有向路段

d∈

χ;ε為時間分段τ內從節點α到節點β的確定行駛時間;y為在時間分段τ內車輛經過路段d，值為1，否則為0;u為時間分段τ內經過路段d的行駛時間波動范圍0，

θ的隨機變量。隨機時變路網中，路段d在時間分段τ內最大行駛時間為確定值ε+θ，根據最大最小準則，兩節點之間的行駛時間可魯棒為確定的時間，則隨機時變路網轉換為確定型時變路網。

2? 遺傳模擬退火算法設計

遺傳算法通過適應度函數對搜索空間中的多個解進行評估，能夠快速搜索到新解，適用于本文組合優化問題的求解[6]，但后期搜索能力減弱致使該算法易過早收斂。本文針對問題特點和遺傳算法的不足，結合模擬退火算法能有效跳出局部循環的特點，提出了一種高效求解STDPDPTW模型的混合遺傳模擬退火算法（Hybrid Genetic Simulated Annealing Algorithm， HGSA）。

2.1? 染色體編碼方式。本文設計了一種三行染色體編碼方式，染色體的第一行為車輛訪問的客戶點，第二行為與第一行對應的車輛編號，第三行為客戶點的需求類型，1為取貨點，-1為送貨點，0為車場。每條染色體的編碼方式如圖2所示，以8個客戶點為例，車輛1的路徑為D-8-3-1-5-D，車輛2的路徑為D-2-4-7-6-D。

2.2? 初始種群的生成。根據客戶點的需求類型和車輛的容量約束，按照以下5個步驟生成初始種群：

Step1：從客戶點集合P中隨機選擇一個取貨點和一個送貨點進行兩兩組合形成待插入客戶點序列P;

Step2：根據車輛容量約束，按待插入客戶點序列P順序為車輛劃分客戶點，得到車輛所訪問的客戶點序列H，形成染色體的第一行編碼;

Step3：在每輛車所訪問的客戶點序列H的最前面和最后面加入該車輛對應的車場編號，用來表示車輛出發的起點和返回的終點，得到每輛車輛的初始路徑訪問的客戶點序列P，形成染色體的第一行編碼;

Step4：在每輛車的初始路徑的編碼的第二行添加對應的車輛編號，在第三行添加客戶點對應的任務類型編號，形成一條完整的染色體，如圖3所示;

Step5：根據預設的種群規模N重復Step1～Step4，得到初始種群。

2.3? 多段多點交叉算子。多點交叉操作不僅增加染色體的多樣性，而且能夠有效避免個體過早收斂，根據染色體編碼方式的特點，染色體中的每一段代表一輛車訪問的客戶點序列，本文設計了多段多點交叉算子，算法步驟如下：

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

Step2：根據染色體第二行的車輛編號將父代染色體F和F分別分成K段;

Step3：分別從父代染色體F和F中相同車輛編號的分段F和F中隨機選擇連續的多個基因進行交換;

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

2.4? 修復算子。使用多段多點交叉方式后的染色體可能存在部分客戶點缺失和重復的問題，則需要將未訪問的客戶點插入到路徑規劃方案中，且為縮短車輛的行駛時間，加快全局尋優過程，設計了修復算子，算法步驟如下：

Step1：從交叉操作后的染色體中標記出所有重復訪問的客戶點，利用公式（16）依次計算染色體中重復點位上一位客戶點n到達該客戶點n的行駛時間與等待時間之和st;

Step2：重復訪問客戶點中相同編號的客戶點兩兩比較st的大小，保留st較小的客戶點，并去除標記;

Step3：利用公式（17）從未訪問客戶點集合N中選擇客戶點依次替換標記出的重復訪問客戶點，生成修復后的新子代個體。

st=t+max

a

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

=arg

t+max

a

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

式（16）表示染色體中重復點位上一位客戶點n到達該客戶點n的行駛時間與等待時間之和。式（17）表示從未訪問客戶點集合N中選擇待插入客戶點n，以依次待替換的染色體中重復點位的上一位客戶點n到達未插入的客戶點n之間的行駛時間和等待時間最小化為替換客戶點的選擇準則。

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

2.6? 種群更新。通過選擇部分父代種群中的精英染色體替代新產生的子代種群中相同數量的染色體來完成種群更新操作，選擇替代染色體的數量為：N=N×1-Gap，其中N為種群規模，Gap為代溝。具體操作如下：一個新的種群由父代種群中適應度值前N位的染色體和子代種群中前

N

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

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

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

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

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

Step3：通過式（1）計算染色體的適應度;

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

Step5：對交叉后的染色體使用修復算子進行修復，補全因交叉過程缺失的客戶點;

Step6：根據變異概率P對交叉后的子代染色體進行變異操作生成變異后的子代染色體;

Step7：種群更新操作;

Step8：判斷種群中最優解的適應度值連續10代是否下降，若沒有下降，則輸出遺傳算法的當前最優解S，轉Step9，否則，轉Step4;

Step9：初始化當前溫度T=T，當前溫度下迭代次數L=0，將Step8輸出的當前最優解S作為當前解S;

Step10：如果溫度T>T，轉Step11，否則，輸出算法終止輸出最優解;

Step11：如果迭代次數L

Step12：4種鄰域算子隨機協作生成鄰域解S;

Step13：如果鄰域解S優于當前解S，則用鄰域解S替代當前解S，否則，轉Step14;

Step14：如果e>δ，δ為0，1的隨機數據，則用鄰域解S替代當前解S，否則，保留S，轉Step11。

3? 實驗分析

本文所有實驗使用Java語言進行編寫，eclipse2018-12的編程環境，Windows 10操作系統，Intel Core i7-7700 CPU@3.60

GHz 16.0 GB的運行環境。

3.1? 參數設置。通過合理的參數設置能夠有效提高算法的求解質量，考慮到實際應用需求，選取多個不同算例，在合理的時間范圍內，采用控制變量法，最終確定一個最佳的參數組合。首先根據經驗確定參數的測試區間，再通過更改參數組合進行多組數值實驗，記錄實驗結果和CPU運行時間，最終確定HGSA參數設置最佳組合如表1所示。

3.2? PDPTW算例。目前關于STDPDPTW研究所進行的實驗并沒有公認的數據集，且STDPDPTW是在經典的PDPTW問題中增加部分約束形成的衍生問題。因此，選取Li & Lim PDPTW標準數據集pdp_100[18]的56個算例進行數值實驗，驗證本文算法的有效性。

本實驗選用Li & Lim PDPTW標準數據集中的56個算例實驗，算例包括LC數據集（地點規則分布）、LR數據集（地點隨機分布）和LRC數據集（地點混合分布）。所有車輛行駛道路類型相同，且以速度為1的恒定速度行駛，以車輛總行駛距離為優化目標。表2記錄了PDPTW的已知最好解R、HGSA算法的總距離S及其運算時間，Gap表示R與S之間的差值百分比，Gap=

R

-S/S。

由表2中數據可知，HGSA算法更新了5個PDPTW算例分別為lc109、lc203、lr108、lrc106和lrc204的已知最好解。在其它的51個PDPTW算例中，HGSA算法的求解結果劣于算例已知最好解，但與已知最好解的差距均值在1%之內，實驗數據說明了HGSA算法求解PDPTW的有效性。

3.3? STDPDPTW算例。基于Li & Lim基準測試實例，根據實例規模將單一車場擴充為5個車場，每個車場位置隨機生成，且每個車場分配5輛車用于完成任務，并增加路段中車輛行駛速度的波動范圍，構建STDPDPTW測試實例。依據城市道路通行情況，將道路分為五種類型，總服務時域分為9個等分的時間分段，依據圖1將車輛的行駛速度時間函數設置為連續函數，不同的時段車輛的最高行駛速度和最低行駛速度不同，路段的道路類型由式（18）判斷：

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

式（18）中，mod為取余計算，例如從7號節點到9號節點的道路類型為2。

表3表示不同道路類型在9個等分的時間分段中車輛行駛速度的變化范圍。對各道路類型和時間分段設置高、中、低三種波動范圍，對于時間分段τ、τ和τ中行駛速度增加±15%的波動范圍，對于時間分段τ、τ和τ中行駛速度增加±20%的波動范圍，對于時間分段τ、τ和τ中行駛速度增加±10%的波動范圍。根據行駛速度波動范圍通過隨機時變車輛行駛時間的魯棒優化方法將隨機時變路網轉化為確定型路網。

表4記錄了隨機選取的10個STDPDPTW算例的實驗結果，在相同實驗條件下每個算例運行20次。其中，20次運行結果的最大值記錄在C列中，平均值記錄在C列中，最小值記錄在C列中，20次運行的平均運行時間記錄在CPU列中，Gap表示C與C之間的差值百分比，Gap表示C與C之間的差值百分比。其中，Gap=C

-

C/C，Gap

=C

-

C/C。

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

4? 結? 論

本文考慮城市交通擁堵、交通管制等不確定因素的影響，建立了隨機時變下帶時間窗的取送貨車輛路徑問題模型，提出考慮車輛加速度的行駛時間計算方式，運用隨機時變車輛行駛時間的魯棒優化方法將隨機性時變轉化為確定型時變，根據

STDPDPTW模型特點，設計了兩階段的混合遺傳模擬退火算法，引入多段多點交叉算子和修復算子，保證了前期迭代的收斂速度后使用多領域搜索算子，提高了算法的搜索效率。通過標準數據集進行驗證，HGSA算法更新了56個PDPTW算例中5個已知最好解，其余算例與已知最好解的差距均值在1%之內，同時STDPDPTW算例表明，HGSA算法求解STDPDPTW具有較強的穩定性，能有效縮短車輛的總行駛時間，降低物流配送成本。

參考文獻：

[1]? 段征宇，雷曾翔，孫碩，等. 隨機時變車輛路徑問題的多目標魯棒優化方法[J]. 西南交通大學學報，2019，54（3）：565-572.

[2]? 蔡延光，湯雅連，蔡顥. 時變路網條件下車輛路徑問題的自適應蟻群算法[J]. 計算機應用研究，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] 鮑偉，賈江鳴，李湘生，等. 考慮軟時間窗的多車型車輛配送路徑優化[J]. 物流科技，2020，43（6）：76-82.

[7] 張凱，靳鵬，崔勇. 帶時間窗的多車型需求可拆分攬收配送問題[J]. 計算機工程與應用，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] 張春苗. 時間依賴綠色選址—車輛路徑問題及算法研究[D]. 杭州：浙江工業大學（博士學位論文），2020.

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

[13] 曹慧，段征宇，陳川. 隨機時變路網環境下穩健路徑選擇及實證研究[J]. 交通運輸系統工程與信息，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] 吳俏. 基于城市路網的行程時間估計及預測方法研究[D]. 杭州：浙江大學（碩士學位論文），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.