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

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

0 引言

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

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

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

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

1 時(shí)間依賴(lài)型同時(shí)取送貨的車(chē)輛路徑問(wèn)題

1.1 問(wèn)題描述

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

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

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

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

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

(3)節(jié)點(diǎn)約束。車(chē)輛進(jìn)入某個(gè)客戶(hù)節(jié)點(diǎn)，也必須從該節(jié)點(diǎn)離開(kāi)。

(4)配送車(chē)輛服務(wù)約束。一輛車(chē)可以為多個(gè)客戶(hù)服務(wù)，但一個(gè)客戶(hù)點(diǎn)只能被一輛車(chē)服務(wù)。

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

1.2 時(shí)間依賴(lài)型路網(wǎng)

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

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

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

因此，得到車(chē)輛從客戶(hù)點(diǎn)i離開(kāi)到達(dá)客戶(hù)j時(shí)跨越的w個(gè)時(shí)間段的速度、行駛距離以及配送時(shí)間為：

(1)

(2)

(3)

(4)

步驟4分段帶入計(jì)算車(chē)輛旅行成本以及車(chē)輛等待的懲罰成本。車(chē)輛離開(kāi)客戶(hù)點(diǎn)i到達(dá)客戶(hù)點(diǎn)j的旅行成本以及等待時(shí)間懲罰成本為

(5)

1.3 數(shù)學(xué)模型

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

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

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

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

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

一個(gè)完整的解表示全部路徑的集合，它包含所有客戶(hù)點(diǎn)，每個(gè)客戶(hù)點(diǎn)只出現(xiàn)一次，并劃分為k條路徑，由k輛車(chē)同時(shí)配送，每條路徑包含一定數(shù)量的客戶(hù)點(diǎn)，路徑的起始點(diǎn)都是配送中心?？尚薪庖笤诿織l路徑的任一時(shí)刻，配送車(chē)輛都要滿足容量約束以及客戶(hù)時(shí)間窗約束。

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

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

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

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

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

2.3 解的接受準(zhǔn)則及選擇策略設(shè)計(jì)

2.3.1 接受準(zhǔn)則

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

P=exp(ΔE/Tk)，

(17)

Tk+1=Tk·β。

(18)

2.3.2 選擇策略(Selection)

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

2.4 算法框架設(shè)計(jì)

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

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

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

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

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

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

(2)解的接收?qǐng)?zhí)行復(fù)雜度 與最優(yōu)解進(jìn)行比較，判斷是否接收，復(fù)雜度為O(NI·O(1))。

(3)算子評(píng)分 對(duì)每個(gè)算子進(jìn)行加分或扣分，復(fù)雜度為O(NI)。

(4)禁忌表更新執(zhí)行復(fù)雜度 按評(píng)價(jià)分?jǐn)?shù)將算子排序，直接插入排序的復(fù)雜度為O(NL)。

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

(6)適應(yīng)度計(jì)算復(fù)雜度 對(duì)于時(shí)間依賴(lài)型車(chē)輛路徑問(wèn)題，需要計(jì)算車(chē)輛由客戶(hù)點(diǎn)i出發(fā)到達(dá)下一個(gè)客戶(hù)點(diǎn)j所跨越的時(shí)間段R，分時(shí)段計(jì)算適應(yīng)度值再求和，因此適應(yīng)度計(jì)算的復(fù)雜度為O(R·N2)。

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

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

算法一次迭代的復(fù)雜度為：

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

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算子，復(fù)雜度為：

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)

則算法的總復(fù)雜度為：

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)

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

3 數(shù)值實(shí)驗(yàn)

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

3.1 算法性能測(cè)試

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

表3 參數(shù)選取

表4 配送車(chē)輛速度

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

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

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

3.2 超啟發(fā)式算法求解TDVRPSDP標(biāo)準(zhǔn)算例

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

表6 配送車(chē)輛速度

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

表7 TDVRPSDP實(shí)例測(cè)試

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

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

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

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

4 結(jié)束語(yǔ)

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