時間依賴型同時取送貨VRP及超啟發(fā)式算法

張景玲，劉金龍，趙燕偉，王宏偉，冷龍龍, 馮勤炳

(浙江工業(yè)大學 特種裝備制造與先進加工技術(shù)教育部重點實驗室，浙江 杭州 310014)

0 引言

在當今激烈的市場競爭中，越來越多的企業(yè)趨向為客戶提供全生命周期的產(chǎn)品及服務(wù)，如家電、食品、汽車行業(yè)，這就要求企業(yè)在保證配送時效的同時，對客戶點進行配送與回收服務(wù)。傳統(tǒng)車輛路徑問題(Vehicle Routing Problem, VRP)的研究不能描述城市物流配送過程中同時取送貨的特點，越來越多的學者轉(zhuǎn)向?qū)ζ浞种栴}——同時取送貨的車輛路徑問題(Vehicle Routing Problem with Simultaneous Delivery and Pickup, VRPSDP)進行研究。

Min[1]于1989年首次提出VRPSDP用于解決公共圖書館問題;Poonthalir等[2]從路徑最短的角度對混合回程的車輛路徑問題進行建模，并考慮車輛巡航以及空載時燃油消耗及碳排放;Ninikas等[3]研究了一種動態(tài)VRPSDP，在執(zhí)行預制定的配送方案過程中實時接收動態(tài)的取貨請求;Lin等[4]提出一個集成了混合鄰域搜索算法的決策支持系統(tǒng)(Decision Support System, DSS)原型來解決離線和在線需求的動態(tài)車輛路徑問題;Hu等[5]研究了貨物不兼容情況下，具有不確定性送貨和確定性取貨的動態(tài)閉環(huán)VRP;Wang等[6]等以降低人力成本、運輸成本以及提高客戶滿意度為目標，采用鄰域搜索算法對帶軟時間窗的VRPSDP進行多目標優(yōu)化;王超等[7]提出一種離散布谷鳥算法(Discrete Cuckoo Search, DCS)算法，以最小化分配成本與行駛成本之和為目標對硬時間窗的VRPSDP進行建模并求解。上述研究很少涉及時間依賴型的VRPSDP，現(xiàn)有時間依賴型車輛路徑問題的研究多集中在無取貨的VRP。Malandraki等[8]對時間依賴型車輛路徑問題(Time Dependent Vehicle Routing Problem, TDVRP)做出了具體描述，首次提出了三段的行程速度分段函數(shù)，將VRP擴展為TDVRP，揭開了對時間依賴型問題的研究的序幕;Figliozzi[9]分析了市區(qū)的早晚交通高峰，引入了1～2.5的旅行速度，使得TDVRP更具有實際的應用價值;穆東等[10]在主從式并行模擬退火算法框架下，使用4種鄰域搜索法求解TDVRP，優(yōu)化目標為最小化配送車輛數(shù)量與總行駛距離;Zhang等[11]將行程速度分段函數(shù)引入VRPSDP，并設(shè)計了集成蟻群與禁忌搜索的新型算法(Ant Colony System and Tabu Search algorithms, ACS-TS)求解該問題?，F(xiàn)有VRPSDP研究假設(shè)車輛勻速行駛，忽略了車速對配送活動的影響，導致VRPSDP模型不能很好地描述城市物流配送速度時變的特點，因此本文研究時變車速對配送成本的影響，建立了時間依賴型同時取送貨車輛路徑問題(Time Dependent Vehicle Routing Problem with Simultaneous Delivery and Pickup, TDVRPSDP)模型。

超啟發(fā)式(Hyper-Heuristics, HH)算法因其具有一定的通用性可用來求解不同領(lǐng)域的組合優(yōu)化問題[12]，獲得了越來越多研究者的關(guān)注。HH算法框架包含高層啟發(fā)式策略(High-Level Heuristic, HLH)和底層啟發(fā)式算子(Low-Level Heuristics, LLH)兩個層次。HLH包含LLH的選擇策略(Selection)以及解的接受準則(acceptance criterion)。通過HLH管理或操縱一系列LLH以選擇和產(chǎn)生新的啟發(fā)式算法對解空間進行搜索。Chen等[13]提出了基于蟻群的HH算法用于解決錦標賽問題，采用蟻群算法來管理和操縱LLH以獲得新的啟發(fā)式算法;Burke等[14]針對教育時間表問題提出了基于禁忌搜索的HH算法，采用禁忌搜索(Tabu Search, TS)方法來獲得新的LLH的組合而成的新的啟發(fā)式算法;Dokeroglu等[15]提出了一種集成模擬退火、禁忌搜索和蟻群優(yōu)化算法尋找最優(yōu)解的HH算法去解決二次分配的問題(Quadratic Assignment Problem, QAP);Sabar等[16]使用一種基因表達編程算法，根據(jù)解的評價自動選擇高層啟發(fā)算法控制LLH搜索最優(yōu)解;Zamli等[17]提出一種集成的HH算法，采用禁忌搜索作為高級元啟發(fā)式和4種低級元啟發(fā)式的強度，包括基于教學優(yōu)化、全局鄰域算法、粒子群算法和布谷鳥搜索算法選擇最適合LLH;Asta等[18]提出多級選擇的超啟發(fā)算法，且引入了學習機制;?zcan等[19]使用群體決策策略作為超啟發(fā)算法的移動接受準則，且每次迭代的接受準則不限于一種。HH算法不但可求解問題種類廣泛，框架設(shè)計靈活多樣，而且求解組合優(yōu)化問題時，可以在較短的時間獲得可接受解。冷龍龍等[20]以量子進化策略作為超啟發(fā)式算法的高層學習策略，并結(jié)合滑動窗口機制實現(xiàn)底層算子的準確搜索，提高算法性能。

鑒于超啟發(fā)式算法在求解組合優(yōu)化問題上的優(yōu)良性能，本文提出了基于禁忌搜索的超啟發(fā)式算法，將禁忌搜索機制作為高層選擇策略用于搜索LLH空間，根據(jù)LLH歷史表現(xiàn)進行評分并逐代更新禁忌表，每次迭代選取最佳算子對解空間進行搜索，從而實現(xiàn)高層策略對底層算子的有效控制。

1 時間依賴型同時取送貨的車輛路徑問題

1.1 問題描述

TDVRPSDP描述如下：給定一個配送中心，一個車輛集合，一個客戶點集合。車輛從配送中心出發(fā)為同一城市不同位置的客戶點進行配送與回收服務(wù)。配送過程中，車輛按順序依次訪問各客戶點，車輛到達客戶點進行配送的同時完成客戶點的回收取貨需求。車輛應在客戶允許的時間范圍內(nèi)提供服務(wù)，完成客戶點的訪問任務(wù)后最終返回配送中心。所有車輛具有相同的容量，且配送車輛在不同的配送時間段有不同的旅行速度。當車輛早于客戶點的時間窗要求到達該客戶點時，配送車輛進行等待，產(chǎn)生懲罰成本計入總成本。

構(gòu)建模型要求滿足以下條件，模型參數(shù)如表1所示。

表1 參數(shù)符號定義

(1)裝載量限制。在任何時刻，車輛的載重量不得超過車輛的最大載重。

(2)車輛路線約束。車輛從配送中心出發(fā)，完成配送后回到配送中心。

(3)節(jié)點約束。車輛進入某個客戶節(jié)點，也必須從該節(jié)點離開。

(4)配送車輛服務(wù)約束。一輛車可以為多個客戶服務(wù)，但一個客戶點只能被一輛車服務(wù)。

(5)客戶點時間窗約束。配送車輛必須在客戶點的時間窗要求內(nèi)訪問該客戶點，提前到達客戶點進行等待產(chǎn)生懲罰成本。

1.2 時間依賴型路網(wǎng)

TDVRPSDP是研究車輛旅行速度隨時間變化的一類車輛路徑問題，同樣屬于NP-Hard問題，其求解更為復雜。本文采用了Zhang等[11]的行程速度分段函數(shù)，將總配送時段分為早高峰(morning Rush hour)、中午平峰(non-rush hour)、晚高峰(evening rush hour)三段，且三時段時長相同，每個時段車速不變，行程距離隨不同的旅行速度線性變化，如圖1所示。

本文對TDVRPSDP的目標函數(shù)值提出如下計算方法，具體步驟為：

步驟1將配送時間段[e0，l0]以時間一定的間隔等分為R個時段，每個時段上對應于車輛的行駛速度，即分段函數(shù)形式的速度時間函數(shù)。

因此，得到車輛從客戶點i離開到達客戶j時跨越的w個時間段的速度、行駛距離以及配送時間為：

(1)

(2)

(3)

(4)

步驟4分段帶入計算車輛旅行成本以及車輛等待的懲罰成本。車輛離開客戶點i到達客戶點j的旅行成本以及等待時間懲罰成本為

(5)

1.3 數(shù)學模型

本文采用文獻[11]所建立的TDVRPSDP模型，其目標函數(shù)是總成本最小，包括車輛租賃成本、旅行成本以及懲罰成本。數(shù)學模型如下：

(6)

s.t.

?k∈V,?r∈W；

(7)

0≤Lijk≤Q,?i,j∈U,?k∈V；

(8)

(9)

(10)

ei≤tik≤li，?i∈U,?k∈V；

(11)

(12)

(13)

(14)

?i,j∈U,?k∈V；

(15)

?j∈U,?k∈V。

(16)

其中：式(6)為TDVRPSDP的目標函數(shù)，表示總成本最小化，包括車輛租賃成本、車輛旅行成本以及車輛等待的懲罰成本；約束(7)保證了客戶在特定的時間間隔內(nèi)被訪問；約束(8)配送車輛在任意的時刻都滿足容量約束；約束(9)車輛出發(fā)時的載重等于所有要訪問的客戶點的需求量總和；約束(10)車輛回到配送中心的時的載重量等于所有已訪問的客戶點的回收量的總和；約束(11)車輛訪問客戶點的時間窗約束；約束(12)保證每個客戶點必須且僅僅被訪問一次；約束(13)保證每條路徑，從配送中心出發(fā)回到配送中心的是同一輛車；約束(14)保證每輛車僅被使用一次；約束(15)保證了車輛從客戶點i出發(fā)到到達客戶點j的時間等于車輛旅行時間加上等待時間；約束(16)保證配送車輛訪問客戶點i前后載重的變化等于需求量減去回收量。

2 基于禁忌搜索的超啟發(fā)式算法設(shè)計

超啟發(fā)式算法通過管理或操縱一系列LLH，以選擇和產(chǎn)生新的啟發(fā)式算法對解空間進行搜索。因此，算法的關(guān)鍵是如何設(shè)計高層策略和底層算子。本文提出的基于禁忌搜索的超啟發(fā)式算法將從以下5個方面開展研究：①初始解的構(gòu)成；②底層啟發(fā)式算子設(shè)計；③算法高層接收準則及選擇策略設(shè)計；④超啟發(fā)式算法框架設(shè)計；⑤算法復雜性的計算。

2.1 初始解的構(gòu)成

一個完整的解表示全部路徑的集合，它包含所有客戶點，每個客戶點只出現(xiàn)一次，并劃分為k條路徑，由k輛車同時配送，每條路徑包含一定數(shù)量的客戶點，路徑的起始點都是配送中心。可行解要求在每條路徑的任一時刻，配送車輛都要滿足容量約束以及客戶時間窗約束。

以配送中心為起點構(gòu)造初始路徑。判斷最近的客戶點是否符合時間窗以及車輛容量約束，若不滿足則隔離該客戶點并選擇下一個最近的客戶點，否則將其納入當前路徑，并將所有隔離客戶點解除隔離，重復此步驟直至所有客戶點都不滿足約束，關(guān)閉該路徑并開啟新的路徑。當所有客戶點都被安排到路徑內(nèi)時，關(guān)閉最后一條路徑。最后對產(chǎn)生的可行解執(zhí)行若干次變異，得到豐富多樣的種群，再選擇較優(yōu)的解作為初始解組。

2.2 底層啟發(fā)式算子設(shè)計

LLH要根據(jù)具體的問題進行設(shè)計，一般分為3類：局部優(yōu)化算子(Local Research, LLH-L)、變異算子(Mutation, LLH-M)和破壞與重構(gòu)算子(Location-based Radial Ruin, LLH-LR)。VRP問題中底層啟發(fā)式算子設(shè)計如表2所示。

表2 底層啟發(fā)式算子設(shè)計

表2中:Adjacent(General)Swap表示相鄰(不相鄰)節(jié)點交換位置;Single(Block)Insertion表示一個(兩個相鄰)節(jié)點移動到兩相鄰節(jié)點之間;Shift(m,0)表示當前路徑中m個相鄰節(jié)點插入另一條路徑中;Swap(m,n)表示當前路徑中的m個相鄰節(jié)點和另一條路徑中的n個相鄰節(jié)點互換位置;Inside-2opt表示連接兩客戶節(jié)點的路線反向后替換原來的路線。

2.3 解的接受準則及選擇策略設(shè)計

2.3.1 接受準則

接受準則(acceptance criterion)用于判斷是否接收子代解取代種群中的個體。接收準則設(shè)計的合理與否直接影響超啟發(fā)算法收斂速度與優(yōu)化精度，若執(zhí)行算子后得到改進解，則總是接收；若得到非改進解，則以一定的概率接收。本文高層策略選擇模擬退火(Simulated Annealing, SA)作為接收準則，非改進解以概率P接收，

P=exp(ΔE/Tk)，

(17)

Tk+1=Tk·β。

(18)

2.3.2 選擇策略(Selection)

同時，本文使用以下兩種選擇策略作為對比：①簡單隨機(Simple Random, SR)，每次迭代隨機選取算子；②隨機下降(Random Descent, RD)，隨機選擇一個算子，一直重復使用該算子直到解沒有改進，然后再選擇其他算子進行搜索直到滿足停止條件。

2.4 算法框架設(shè)計

算法采用種群機制，種群規(guī)模NI，為保證每次迭代以合理的概率選擇LLH、接受非改進解，設(shè)計出如圖2所示算法流程，具體步驟如下：

步驟6更新禁忌表。根據(jù)算子得分SG=[S1,S2,…,S20],計算評價分數(shù)SL、α·SM、α·SLR，更新算子禁忌表，并根據(jù)不在禁忌表內(nèi)的算子的得分，使用輪盤賭策略選擇算子hG。

步驟7退出迭代。若G>Gmax，算法結(jié)束，輸出最優(yōu)解，否則轉(zhuǎn)步驟2。

2.4 基于禁忌搜索的超啟發(fā)式算法復雜度分析

根據(jù)上述流程，算法的復雜度包括：底層算子執(zhí)行復雜度、解的接收執(zhí)行復雜度、算子評分與禁忌表更新執(zhí)行復雜度、選擇策略執(zhí)行復雜度、適應度值計算執(zhí)行復雜度、最優(yōu)解更新執(zhí)行復雜度和初始化操作執(zhí)行復雜度。本文基于禁忌搜索的超啟發(fā)式算法參數(shù)如下：種群規(guī)模為NI、迭代次數(shù)Gmax、客戶數(shù)量為N、車輛數(shù)量為K、底層算子個數(shù)為NL以及配送時間分段數(shù)量R。

(1)底層算子執(zhí)行復雜度 LLH-L和LLH-M算子完成客戶點的插入操作，并計算適應度值，因此復雜度為O(O(1)+O(R·N2));LLH-LR算子重構(gòu)一個可行解，則復雜度為O(O(N2)+O(R·N2))。算法采用種群機制，因此對于LLH-L和LLH-M的執(zhí)行復雜度為O(NI·(O(1)+O(R·N2)))，對于LLH-LR執(zhí)行復雜度為O(NI·(O(N2)+O(R·N2)))。

(2)解的接收執(zhí)行復雜度 與最優(yōu)解進行比較，判斷是否接收，復雜度為O(NI·O(1))。

(3)算子評分 對每個算子進行加分或扣分，復雜度為O(NI)。

(4)禁忌表更新執(zhí)行復雜度 按評價分數(shù)將算子排序，直接插入排序的復雜度為O(NL)。

(5)選擇策略執(zhí)行復雜度 輪盤賭選擇算子，復雜度為O(NL)。

(6)適應度計算復雜度 對于時間依賴型車輛路徑問題，需要計算車輛由客戶點i出發(fā)到達下一個客戶點j所跨越的時間段R，分時段計算適應度值再求和，因此適應度計算的復雜度為O(R·N2)。

(7)最優(yōu)解更新執(zhí)行復雜度 將種群的解進行比較，取最優(yōu)，復雜度為O(NI)。

(8)初始化操作 初始化解與算子得分，復雜度為O(N2)。

算法一次迭代的復雜度為：

若選擇LLH-L或LLH-M算子，復雜度為：

O(HH)=O(O(NI·(O(1)+O(R·N2)))+

O(NI·O(1))+O(NI)+O(NL)+O(NL))

=O(NI·R·N2)；

(19)

若選擇LLH-LR算子，復雜度為：

O(HH)=O(O(NI·(O(N2)+O(R·N2)))+

O(NI·O(1))+O(NI)+O(NL)+O(NL))

=O(NI·R·N2)。

(20)

則算法的總復雜度為：

O(HH)=O(N2)+Gmax·O(O(NI·(O(N2)+

O(R·N2)))+O(NI·O(1))+O(NI)+

O(NL)+O(NL))=O(Gmax·

NI·R·N2)。

(21)

由上述分析可知，算法的整體計算復雜度約為O(Gmax·R·NI·N2)，即算法上層策略包括選擇函數(shù)以及接受準則的復雜度可以忽略不計。影響算法復雜度因素主要包括：算法的迭代次數(shù)Gmax、種群規(guī)模NI、時間分段R以及客戶點規(guī)模N。對于一般的用于解決旅行商問題的基于種群的算法，復雜度為O(Gmax·NI·N2)，如劉欣欣[21]提出的基于片段插入的類粒群算法，其復雜度為O(Gmax·N3)(其種群規(guī)模NI=2N);冷龍龍等[20]提出量子超啟發(fā)式算法用于解決低碳選址—路徑問題，其算法復雜度約為Gmax·NI·O(N2)。根據(jù)算法的復雜度判斷，本文所提出的基于禁忌搜索的超啟發(fā)式算法屬于多項式級的算法，其復雜度處于計算機可承受范圍之內(nèi)。

3 數(shù)值實驗

實驗環(huán)境Intel(R)core-i5-8250U,8 GB RAM，程序獨立運行10次，并計算最優(yōu)解目標函數(shù)值(Min)，最優(yōu)解目標函數(shù)值方差(s2)，最優(yōu)解目標函數(shù)值平均值(Avg)、算法運行時間(CT)和最優(yōu)解改進(gM)和算法運行時間改進(gC)。

3.1 算法性能測試

為測試算法的實際性能，設(shè)計了第一個對比實驗。對比數(shù)據(jù)來自于文獻[11]中對TDVRPSDP算例所得的測試結(jié)果。本實驗中，將基于禁忌搜索的超啟發(fā)式算法(Hype-Heuristics—Tabu Search, HH-TS)和簡單隨機作為選擇策略的超啟發(fā)式算法(Hyper-Heuristics—Simple Random, HH-SR)的求解結(jié)果進行比較以評估算法高層選擇策略對算法性能的影響。實驗設(shè)置參數(shù)CF=100，CT=1，CW=1，迭代次數(shù)Gmax=20 000。本文采用試取法選擇參數(shù)，如表3所示。實驗中的速度時間分段函數(shù)如表4所示。同時，將HH-TS與文獻[11]的求解結(jié)果做比較以評估算法獲得最優(yōu)解的能力，如表5所示。表5中左側(cè)給出文獻[11]設(shè)計的集成蟻群與禁忌搜索的新型算法(ACS-TS)所得56個測試算例最優(yōu)解，其中螞蟻數(shù)量為20，TS迭代次數(shù)為60，ACS迭代次數(shù)為300，計算機配置：Window XP.Intel(R)Core(TM)Celeron M.1.67 GHz。

表3 參數(shù)選取

表4 配送車輛速度

表5 基于禁忌搜索的超啟發(fā)式算法性能測試

表5中，gM項下展示了HH-TS與ACS-TS算法所得最優(yōu)解相比較所取得的改進gM-T/A。在56個算例中，相較于ACS-TS，使用HH-TS有55個算例取得了大幅度改進。在55個取得改進的算例中，最大改進達到了58.0%，最小改進為0.8%，平均取得改進31.2%。另外，文獻[11]給出了多次求解的平均值，如表5第2列。平均值只能在一定程度上反映算法的求解能力，但不能體現(xiàn)數(shù)據(jù)的離散程度。為保持完整性，本實驗也給出了多次運行算法求解的平均值。HH-SR、HH-TS相較于ACS-TS，平均值分別取得了平均28.81%、32.02%的改進。

表5中,gM項下展示了HH-TS較HH-SR所取得的最優(yōu)解改進gM-T/S，gC項下展示了HH-TS較HH-SR所取得的算法運行時間的改進gC-T/S。在56個算例中，相較于HH-SR，使用HH-TS 52個算例取得了目標函數(shù)值最大16.9%，平均4.9%的改進，此外的4個算例也取得了最差-0.5%的相對較劣的解。由此可見，超啟發(fā)式算法在標準算例的求解上具有較好的優(yōu)化精度。另外，HH-SR采用隨機的選擇函數(shù)與模擬退火接受準則作為上層策略，對3個類型底層算子進行隨機的調(diào)用。HH-SR相較于HH-TS，執(zhí)行無效的算子耗費了大量的時間。因此，對于同樣的迭代次數(shù)，HH-TS耗時相對HH-SR大幅減少，最大92%，平均68.5%，如表5第13列所示。因此，超啟發(fā)式算法較優(yōu)的上層策略設(shè)計能在一定程度上，調(diào)用底層算子向函數(shù)值下降最快的方向高效地進行最優(yōu)解搜索，可以保證一定的收斂速度和跳出局部最優(yōu)的能力。在求解TDVRSDP時，往往超啟發(fā)算法擁有更好的優(yōu)勢，能在短時間內(nèi)求得可接受的解。

3.2 超啟發(fā)式算法求解TDVRPSDP標準算例

實驗增加了基于隨機下降選擇策略的超啟發(fā)式算法(Hyper-Heuristics—Random Descent, HH-RD)實驗數(shù)據(jù)，將HH-TS求解TDVRPSDP的結(jié)果與HH-SR、HH-RD對比。實驗的測試實例來自于文獻[22]，并構(gòu)造了高峰、平峰車速不同于文獻[11]的速度時間分段函數(shù)，以一定的比率提高車輛速度，比率為0.5～5(如表6)，得到TDVRPSDP的測試實例，如表7所示。

表6 配送車輛速度

文獻[22]在Solomon的56個VRPTW標準測試實例的基礎(chǔ)上，構(gòu)造了6類VRPSPDPTW標準測試實例(LR1,LR2，LC1,LC2,LRC1,LRC2)并提供最優(yōu)解：車輛數(shù)量(Veh)和行駛距離(Dis)，如表7左側(cè)第1和第2列所示。

表7 TDVRPSDP實例測試

下面從模型的角度分析數(shù)據(jù)結(jié)果。表8列舉了配送車輛速度變化對車輛數(shù)量及車輛總行駛距離的影響。相較于最優(yōu)解，當車速增加時，配送車輛數(shù)量隨車速增加而減少，但車輛的行駛距離并沒有隨之減少，而是微量增加。當車速取0.5和1的倍率時，較慢的車速使得配送車輛滿足客戶點時間窗的能力降低，車輛最大容量在一定程度上已不再是限制單車配送多個客戶點的關(guān)鍵因素。因此，單車可訪問客戶點的數(shù)量下降，需要派發(fā)更多車輛才能保證每個客戶點的配送時效。例如，在0.5倍速時，對于LC1算例，車輛數(shù)量增加41.67%，車輛行駛距離增加21.37%，如表8第2行。因此，車輛的出發(fā)成本與旅行成本較高，總成本較高。反之，車速取2、4和5倍速率時，配送車輛滿足客戶點時效要求的能力升高，單車可訪問客戶點數(shù)量上升，但是受限于車輛的最大容量，單車可訪問客戶點數(shù)量少量增加，使用車輛數(shù)量不會大量減少。同時，隨著車速提高，單位時間車輛使用成本不變(CT=1)，單位時間車輛可行駛距離變?yōu)樵瓉淼?.5、1、2、4、5倍。車輛的行駛時間大幅減少，因此車輛的旅行成本大幅降低，總成本降低。總結(jié)如下：①當車速提高時，使用車輛數(shù)量逐漸減少，受限于車輛最大容量，車輛數(shù)量減少數(shù)量終將到達一個固定的極限；②隨車速提高，車輛行駛距離少量增加，車輛的旅行成本大幅降低，物流配送成本大幅降低，如表7第8列。因此，由實驗結(jié)果可知：當車速提高時，增大車輛容量將有效減少車輛的使用數(shù)量，減少所有車輛總的行駛時間，有效地降低成本。

表8 配送車輛速度對車輛數(shù)量及總行駛距離的影響

從算法角度分析，HH-TS取得最優(yōu)的計算結(jié)果。表7Min項下分別展示了HH-TS與HH-SR算法所的最優(yōu)解相比較所取得的改進gM-T/S，HH-TS與HH-RD比較所取得的改進gM-T/R。在56個算例中，HH-TS相對于HH-SR，全部算例均取得了更優(yōu)的解，最大改進43.4%，平均改進12.9%。同時，相較于HH-RD，53個算例取得了更優(yōu)的解，最大改進27.2%，平均改進9.1%。HH-SR、HH-RD和HH-TS在全部算例的計算結(jié)果得到的平均方差分別為230、282和205。可以從方差的角度分析3種策略算法對求解TDVRPSDP最優(yōu)解的離散程度。SR策略因其隨機地選擇LLH對最優(yōu)解進行搜索，在有限的迭代之后通常得不到最優(yōu)解，而RD策略具有一定的避免選擇無效LLH的能力，但無法選擇最有效的那些算子，所以僅具有微弱的跳出局部最優(yōu)的能力，求解結(jié)果波動較大。TS策略根據(jù)評分選擇禁忌表外的LLH，且以輪盤賭方式分配L、M和LR被選擇的概率。因此，HH-TS每次求得最優(yōu)解的波動也最小，性能也最好。

由此可見，上層策略的設(shè)計對解空間的搜索效率起著至關(guān)重要的作用，較好的上層策略不但能取得更好的解，而且所得結(jié)果波動較小，可以獲得更好地收斂曲線并保證跳出局部最優(yōu)的能力。因此，計算結(jié)果說明了禁忌搜索為選擇策略的超啟發(fā)式算法在求解TDVRPSDP上的有效性。

4 結(jié)束語

本文研究了時間依賴型同時取送貨車輛路徑問題，將配送中心的開放時間等分為3段，每段對應不同的車輛旅行速度，以車輛的租賃成本、車輛旅行成本以及車輛等待的懲罰成本之和為目標建模。設(shè)計了基于禁忌搜索的超啟發(fā)式算法，高層選擇策略采用禁忌搜索機制，依據(jù)算子的性能選擇最有希望改進當代解的算子進行搜索，算子性能的評分由其歷史表現(xiàn)決定，并逐代更新；高層接收準則采用模擬退火機制，保證了算法前期的快速收斂，算法中后期以一定的概率接受非改進解，使算法具備了跳出局部最優(yōu)的能力。最后，通過標準算例及實驗對比表明，算法在求解該問題上能較快速地取得可接受的解。對于時間依賴型車輛路徑問題，車速與配送成本的關(guān)系較為復雜，后續(xù)將圍繞更加復雜的車輛旅行速度以及可變車速下客戶滿意度、配送成本、能源消耗與行車路徑之間的關(guān)系對問題模型展開研究。此外，盡管超啟發(fā)式算法在求解TDVRPSDP上表現(xiàn)出良好的性能，但仍然具有一定的改進空間，未來考慮將超啟發(fā)式算法與其他策略結(jié)合，開發(fā)出更加高效的上層策略。