靳 鵬，張歆悅 （合肥工業(yè)大學(xué) 管理學(xué)院，安徽 合肥 230009）

0 引 言

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

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

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

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

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

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

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

約束條件如下：

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

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

圖1 速度時(shí)間函數(shù)

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

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

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

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

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

圖2 染色體編碼示意圖

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

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

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

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

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

圖3 種群初始化過(guò)程示意圖

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

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

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

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

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

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

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

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

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

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

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

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

2.6 種群更新。通過(guò)選擇部分父代種群中的精英染色體替代新產(chǎn)生的子代種群中相同數(shù)量的染色體來(lái)完成種群更新操作，選擇替代染色體的數(shù)量為：N=N× 1-Ga（ ）p ，其中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è)客戶點(diǎn)進(jìn)行交換，并將兩個(gè)客戶點(diǎn)中的客戶點(diǎn)反轉(zhuǎn)逆序排列，如圖6（a） 所示。（2） 單點(diǎn)交換算子：從原路徑中隨機(jī)選擇客戶點(diǎn)移除，插入到其它路徑中，如圖6（b） 所示。（3） 合并搜索算子：隨機(jī)選擇一條路徑，將該路徑上的客戶點(diǎn)插入到其它路徑中，如圖6（c） 所示。（4） 兩點(diǎn)交換算子：從兩條不同的路徑中分別各選擇一個(gè)客戶點(diǎn)，并交換他們的位置，如圖6（d） 所示。

圖6 領(lǐng)域算子示意圖

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

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

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

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

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

Step5：對(duì)交叉后的染色體使用修復(fù)算子進(jìn)行修復(fù)，補(bǔ)全因交叉過(guò)程缺失的客戶點(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＜L，則L=L+1，轉(zhuǎn)12，否則，L=0，T=T×R，轉(zhuǎn)Step10；

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

本文所有實(shí)驗(yàn)使用Java 語(yǔ)言進(jìn)行編寫，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 所示。

表1 算法的最佳參數(shù)值

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的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ù)集（地隨機(jī)分布） 和LRC 數(shù)據(jù)集（地點(diǎn)混合分布）。所有車輛行駛道路類型相同，且以速度為1 的恒定速度行駛，以車輛總行駛距為優(yōu)化目標(biāo)。表2 記錄了PDPTW 的已知最好解R、HGSA 算法的總距離S及其運(yùn)算時(shí)間，Gap 表示R與S之間的差百分比，Gap=（R-S）/S。增的 點(diǎn)離值

表2 PDPTW 數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

由表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ǎng)擴(kuò)充為5 個(gè)車場(chǎng)，每個(gè)車場(chǎng)位置隨機(jī)生成，且每個(gè)車場(chǎng)分配5 輛車用于完成任務(wù)，并增加路段中車輛行駛速度的波動(dòng)范圍，構(gòu)建STDPDPTW 測(cè)試實(shí)例。依據(jù)城市道路通行情況，將道路分為五種類型，總服務(wù)時(shí)域分為9 個(gè)等分的時(shí)間分段，依據(jù)圖1 將車輛的行駛速度時(shí)間函數(shù)設(shè)置為連續(xù)函數(shù)，不同的時(shí)段車輛的最高行駛速度和最低行駛速度不同，路段的道路類型由式（18） 判斷：

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

表3 表示不同道路類型在9 個(gè)等分的時(shí)間分段中車輛行駛速度的變化范圍。對(duì)各道路類型和時(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í)變車輛行駛時(shí)間的魯棒優(yōu)化方法將隨機(jī)時(shí)變路網(wǎng)轉(zhuǎn)化為確定型路網(wǎng)。

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

表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 STDPDPTW 數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

由表4 數(shù)據(jù)可知，考慮車輛行駛時(shí)間的時(shí)變性和隨機(jī)性，在車輛數(shù)量有限的情況下，通過(guò)優(yōu)化車輛的出發(fā)時(shí)間和出發(fā)的車場(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í)間窗的取送貨車輛路徑問(wèn)題模型，提出考慮車輛加速度的行駛時(shí)間計(jì)算方式，運(yùn)用隨機(jī)時(shí)變車輛行駛時(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)定性，能有效縮短車輛的總行駛時(shí)間，降低物流配送成本。