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

靳 鵬，張歆悅 （合肥工業大學 管理學院，安徽 合肥 230009）

0 引 言

車輛路徑問題（Vehicle Routing Problem，VRP） 自提出以來，一直是物流組織優化領域中的研究難點。在實際物流系統中，為滿足取貨或配送及服務時間窗限制的客戶需求，帶時間窗的取送貨車輛路徑問題（Pickup and Delivery with Time Windows，PDPTW） 逐漸受到眾多學者的關注。然而，近年來城市交通日趨擁堵，受交通管制、交通事故等不確定因素的影響，城市交通路網存在一定的時變性和隨機性，車輛的行駛速度是時變的。在此背景下，研究隨機時變下帶時間窗的取送貨車輛路徑問題（Stochastic Time-dependent Pickup and Delivery with Time Windows, STDPDPTW） 具有重要意義。

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

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

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

1 問題描述與數學模型

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

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

約束條件如下：

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

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

圖1 速度時間函數

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

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

2 遺傳模擬退火算法設計

遺傳算法通過適應度函數對搜索空間中的多個解進行評估，能夠快速搜索到新解，適用于本文組合優化問題的求解，但后期搜索能力減弱致使該算法易過早收斂。本文針對問題特點和遺傳算法的不足，結合模擬退火算法能有效跳出局部循環的特點，提出了一種高效求解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.2 初始種群的生成。根據客戶點的需求類型和車輛的容量約束，按照以下5 個步驟生成初始種群：

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

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

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

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

圖3 種群初始化過程示意圖

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

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

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

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

圖4 染色體交叉操作示意圖

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

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

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

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

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

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

圖5 染色體變異操作示意圖

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

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

圖6 領域算子示意圖

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

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＜L，則L=L+1，轉12，否則，L=0，T=T×R，轉Step10；

3 實驗分析

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

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

表1 算法的最佳參數值

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

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

表2 PDPTW 數據集實驗結果

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

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

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

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

表3 各道路類型車輛行駛速度變化范圍

表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 STDPDPTW 數據集實驗結果

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

4 結 論

本文考慮城市交通擁堵、交通管制等不確定因素的影響，建立了隨機時變下帶時間窗的取送貨車輛路徑問題模型，提出考慮車輛加速度的行駛時間計算方式，運用隨機時變車輛行駛時間的魯棒優化方法將隨機性時變轉化為確定型時變，根據STDPDPTW 模型特點，設計了兩階段的混合遺傳模擬退火算法，引入多段多點交叉算子和修復算子，保證了前期迭代的收斂速度后使用多領域搜索算子，提高了算法的搜索效率。通過標準數據集進行驗證，HGSA 算法更新了56 個PDPTW 算例中5 個已知最好解，其余算例與已知最好解的差距均值在1%之內，同時STDPDPTW 算例表明，HGSA 算法求解STDPDPTW 具有較強的穩定性，能有效縮短車輛的總行駛時間，降低物流配送成本。