基于改進(jìn)禁忌搜索算法的VRPSPDTW 研究

張 思，王 海 （上海大學(xué) 管理學(xué)院，上海 200444）

ZHANG Si， WANG Hai (School of Management, Shanghai University, Shanghai 200444, China)

0 引 言

近年來(lái)，隨著經(jīng)濟(jì)水平的快速發(fā)展，人們的生活條件不斷改善，對(duì)生鮮產(chǎn)品的需求量逐年上升。據(jù)統(tǒng)計(jì)2018 年生鮮市場(chǎng)交易額約為1.91 萬(wàn)億元，然而由于產(chǎn)品腐爛變質(zhì)造成的損失高達(dá)1.23 千億元[1]。所以為了保證產(chǎn)品新鮮度從而降低貨損成本，運(yùn)輸途中會(huì)全程低溫冷鏈，但這會(huì)大幅增加能耗成本。合理的車輛調(diào)度可以縮短產(chǎn)品的在途運(yùn)輸時(shí)間，保證生鮮產(chǎn)品的新鮮度，降低貨損率，減少燃油消耗量，降低運(yùn)輸成本。因此冷鏈物流的車輛路徑問(wèn)題成為新的研究熱點(diǎn)，引起了眾多學(xué)者的關(guān)注[2]。

為了提高客戶滿意度，產(chǎn)品需要在規(guī)定的時(shí)間窗內(nèi)交付客戶，然而由于生鮮產(chǎn)品的易腐性，因此客戶對(duì)產(chǎn)品新鮮度有一定要求，全程冷鏈降低了腐爛速度，但是會(huì)加大運(yùn)輸油耗，產(chǎn)生更多的二氧化碳，不利于環(huán)境保護(hù)?，F(xiàn)有的研究已經(jīng)考慮了時(shí)間窗[3-5]、碳排放[6-8]、產(chǎn)品新鮮度[9-10]等多種情況下的冷鏈物流車輛路徑問(wèn)題，但是在上述研究基礎(chǔ)上考慮同時(shí)取送貨情況下的冷鏈配送研究還相對(duì)比較少。生鮮產(chǎn)品要求在整個(gè)配送過(guò)程中保持恒定的低溫，車門的頻繁開(kāi)關(guān)和裝載貨物時(shí)頻繁搬動(dòng)會(huì)影響溫度控制，加速產(chǎn)品的腐爛變質(zhì)；同時(shí)，生鮮產(chǎn)品的逆向物流量主要為包裝物的回收和少量缺陷產(chǎn)品的退貨，比一般產(chǎn)品少。將正向的配送和逆向的回收單獨(dú)運(yùn)作，必然會(huì)增加制冷成本和運(yùn)輸成本。因此，采用同時(shí)取送貨策略，可以節(jié)約運(yùn)輸、制冷、回收等成本，有利于節(jié)約資源和保護(hù)環(huán)境。所以本文在前人的基礎(chǔ)上，考慮顧客同時(shí)有取貨和送貨的需求，建立帶時(shí)間窗的同時(shí)取送貨車輛路徑問(wèn)題（Vehicle Routing Problem with Simultaneous Pickup-Delivery with Time Windows， VRPSPDTW） 運(yùn)輸配送模型。

2003 年 Angelelli 等[11]首次提出 VRPSPDTW 問(wèn)題，Savelsbergh[12]證明了 VRPTW （Vehicle Routing Problem with Time Windows） 為NP-hard 問(wèn)題，那么它的拓展VRPSPDTW 也一定為NP-hard 問(wèn)題。由于精確算法僅適用于求解VRPSPDTW 的小規(guī)模問(wèn)題，而對(duì)于中大型規(guī)模，學(xué)者們更傾向于設(shè)計(jì)啟發(fā)式算法獲得最優(yōu)可行解。Lai 等[13]應(yīng)用改進(jìn)的差分進(jìn)化算法求解了一個(gè)8個(gè)顧客規(guī)模的算例。Wang 等[14]在Solomon[15]的VRPTW 測(cè)試算例的基礎(chǔ)上，提出了VRPSPDTW 的測(cè)試算例，并使用共同演化遺傳算法進(jìn)行求解。該算例囊括了9 個(gè)中小型算例（顧客規(guī)模為10，25，50 各3 個(gè)） 和56 個(gè)大規(guī)模算例（顧客規(guī)模為100），成為國(guó)際上針對(duì)VRPSPDTW 的通用算例。Wang 等[16]采用并行模擬退火算法，王超等[17]應(yīng)用離散布谷鳥(niǎo)算法，黃務(wù)蘭等[18]使用改進(jìn)全局人工魚(yú)群算法都對(duì)該算例進(jìn)行求解。

禁忌搜索算法（Tabu Search，TS） 是一種鄰域逐步尋優(yōu)的局部搜索算法，采用禁忌策略減少循環(huán)搜索，提高搜索效率。李相勇[19]在對(duì)VRP 問(wèn)題求解算法詳細(xì)綜述的基礎(chǔ)上指出，在各種啟發(fā)式算法中以禁忌搜索算法的求解質(zhì)量最高，是一種高效算法。本文選用標(biāo)準(zhǔn)TS 作為算法框架，加入多種性能提升策略，提高算法的尋優(yōu)能力，對(duì)VRPSPDTW 問(wèn)題進(jìn)行求解。

1 帶時(shí)間窗的同時(shí)取送貨車輛路徑問(wèn)題

1.1 問(wèn)題描述

冷鏈VRPSPDTW 可以被描述為：給定一個(gè)配送中心、一組位于不同位置的顧客以及一個(gè)冷藏車隊(duì)，每個(gè)顧客都有自己的服務(wù)時(shí)間窗以及取貨需求和送貨需求，管理者的決策是為車隊(duì)的每一輛車規(guī)劃服務(wù)顧客的行駛路徑，優(yōu)化總的物流成本。

1.2 假設(shè)

一個(gè)配送中心為若干個(gè)顧客提供服務(wù)，配送中心和顧客的位置都是確定的，各顧客的取貨需求和送貨需求都是已知的，每輛冷藏車的起始點(diǎn)和終止點(diǎn)都是配送中心；配送中心的冷藏車數(shù)量充足且為同一型號(hào)；冷藏車輛在運(yùn)輸過(guò)程中勻速行駛，不考慮交通情況的影響；每個(gè)顧客只允許被服務(wù)一次。

1.3 參數(shù)

（1） 集合。V 為顧客點(diǎn)集合，V=｛i ｝，i=1，2，…，n；i=0 表示配送中心，其中節(jié)點(diǎn)集合 U=V∪ ｛0 ｝；K 為冷藏配送車輛集合，K=｛k ｝，k=1，2，…，m。

（2） 參數(shù)。c1：每輛冷藏車的固定使用成本；c2：冷藏車行駛單位距離的運(yùn)輸成本；c3：冷藏車提前到達(dá)客戶點(diǎn)處的單位時(shí)間等待成本；c4：冷藏車延遲到達(dá)客戶點(diǎn)處的單位時(shí)間懲罰成本；c5：冷藏車排放單位重量二氧化碳的成本；c6：?jiǎn)挝恢亓恐评鋭┑氖褂贸杀荆籧7：?jiǎn)挝恢亓控浳锏膿p耗成本；Q：冷藏車的最大載重量；dij：客戶點(diǎn)i 與客戶點(diǎn)j 之間的距離；tij：從客戶點(diǎn)i 到客戶點(diǎn)j 所需的時(shí)間；pi：客戶點(diǎn)i 處的取貨需求量；qi：客戶點(diǎn)i 處的送貨需求量；ti：冷藏車在客戶點(diǎn)i 處裝卸貨所需的時(shí)間；f：燃料的消耗函數(shù)；σ1：運(yùn)輸過(guò)程中消耗單位體積的燃料產(chǎn)生的二氧化碳重量；σ2：運(yùn)輸過(guò)程中制冷設(shè)備單位時(shí)間內(nèi)產(chǎn)生的二氧化碳重量；g1：運(yùn)輸過(guò)程中產(chǎn)生的熱負(fù)荷函數(shù)；g2：裝卸貨過(guò)程中產(chǎn)生的熱負(fù)荷函數(shù)；α1：運(yùn)輸過(guò)程中單位時(shí)間內(nèi)單位貨物的損耗比例；α2：裝卸過(guò)程中單位時(shí)間內(nèi)單位貨物的損耗比例； ［ETi，LTi］：客戶點(diǎn)i 的時(shí)間窗。

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

1.4.1 碳排放成本

碳排放成本主要包括兩個(gè)方面：一是發(fā)動(dòng)設(shè)備產(chǎn)生的CO2成本，二是制冷設(shè)備產(chǎn)生的CO2成本。

（1） 發(fā)動(dòng)設(shè)備產(chǎn)生的碳排放成本。發(fā)動(dòng)設(shè)備產(chǎn)生的CO2主要通過(guò)燃油消耗量來(lái)計(jì)算，依據(jù)參考文獻(xiàn)[20]，冷藏車單位距離燃料消耗量為；

其中：ρ0、ρ*分別為空載、滿載下運(yùn)輸單位距離時(shí)燃料的消耗量，X 為冷藏車的載重量，Q 為最大載重量。

由于發(fā)動(dòng)設(shè)備只在運(yùn)輸過(guò)程中啟動(dòng)，所以發(fā)動(dòng)設(shè)備產(chǎn)生的碳排放成本為：

（2） 制冷設(shè)備產(chǎn)生的碳排放成本。由于冷藏車的制冷設(shè)備與發(fā)動(dòng)設(shè)備是相互獨(dú)立的，所以等待過(guò)程中發(fā)動(dòng)機(jī)熄火，而制冷設(shè)備仍繼續(xù)工作。冷藏車服務(wù)完最后一個(gè)顧客返回配送中心時(shí)，車上已沒(méi)有生鮮產(chǎn)品，因此會(huì)關(guān)閉制冷設(shè)備。所以制冷設(shè)備產(chǎn)生的碳排放成本為：

綜上，整個(gè)配送過(guò)程中的碳排放成本為：

1.4.2 制冷成本

制冷成本主要包括運(yùn)輸途中和等待過(guò)程中由于冷藏車內(nèi)外溫差不同所引起的傳熱，以及裝卸過(guò)程中的熱空氣對(duì)流，可以通過(guò)制冷劑的消耗進(jìn)行計(jì)算制冷成本。

（1） 運(yùn)輸過(guò)程。運(yùn)輸途中因?yàn)閮?nèi)外溫差單位時(shí)間產(chǎn)生的熱負(fù)荷為：

其中：β 表示車輛的折舊程度，R 為車輛的導(dǎo)熱率，S 為車輛平均受熱面積，可表示為分別表示車廂的內(nèi)外表面積，Tn、Tw分別表示車廂的內(nèi)外溫度。

所以，運(yùn)輸途中的制冷成本為：

（2） 等待過(guò)程。由于等待過(guò)程中并未打開(kāi)車門且制冷設(shè)備仍在工作，熱負(fù)荷產(chǎn)生函數(shù)不變，因此等待過(guò)程中的制冷成本為：

（3） 裝卸過(guò)程。冷藏車到達(dá)顧客進(jìn)行裝卸服務(wù)時(shí)需打開(kāi)車門，此時(shí)熱空氣對(duì)流，單位時(shí)間產(chǎn)生的熱負(fù)荷為：

其中：Vk表示車廂的體積，γ 表示開(kāi)門頻率系數(shù)。

所以，冷藏車在裝卸過(guò)程中的制冷成本為：

綜上，整個(gè)配送過(guò)程中的制冷成本為：

構(gòu)建冷鏈VRPSPDTW 的數(shù)學(xué)模型如下：

式（2） 保證每個(gè)客戶只能被一輛冷藏車服務(wù)，式（3） 和（4） 是兩個(gè)變量之間的關(guān)系，保證每輛冷藏車運(yùn)輸時(shí)的載重量不能超過(guò)它的最大載重量，式（5） 保證每輛冷藏車從配送中心出發(fā)服務(wù)完所有客戶后必須回到配送中心，式（6） 保證冷藏車從配送中心出發(fā)時(shí)的載貨量等于線路上顧客的送貨總需求，式（7） 表示冷藏車經(jīng)過(guò)顧客前后載重量變化，式（8） 保證冷藏車的載重量始終不超過(guò)最大容量，式（9） 和（10） 確保每輛冷藏車服務(wù)時(shí)間的連續(xù)性，式（11） 和（12） 表示兩個(gè)變量的取值范圍。

2 算法設(shè)計(jì)

TS 算法是一種逐步尋優(yōu)的鄰域搜索算法，從初始解出發(fā)，記憶搜索過(guò)程中局部最優(yōu)解，避免在下一次搜索過(guò)程中進(jìn)行重復(fù)搜索，盡可能多地?cái)U(kuò)大搜索范圍，利用局部最優(yōu)的信息逐步達(dá)到全局尋優(yōu)。然而，標(biāo)準(zhǔn)TS 算法對(duì)初始解的依賴性很強(qiáng)，且很難對(duì)某一特定問(wèn)題確定有效的禁忌長(zhǎng)度，難以避免搜索過(guò)早收斂，從而陷入局部最優(yōu)，錯(cuò)失全局最優(yōu)解。

本文設(shè)計(jì)改進(jìn)的TS 算法采用RCRS 算法生成較優(yōu)的初始解，保證解的質(zhì)量，鄰域變換時(shí)應(yīng)用了多鄰域隨機(jī)變換策略，實(shí)現(xiàn)對(duì)多個(gè)鄰域的快速搜索，有利于豐富鄰域解的多樣性，避免算法過(guò)早收斂，WTS 編碼方式縮短了鄰域運(yùn)算時(shí)間，減少了迭代次數(shù)，響應(yīng)性策略可以依據(jù)搜索進(jìn)程動(dòng)態(tài)地調(diào)整禁忌長(zhǎng)度，加強(qiáng)了TS 算法的搜索機(jī)制，使得求解更加全局性。

下面介紹改進(jìn)策略的具體流程。

2.1 路徑的編碼與解碼

VRP 問(wèn)題的常見(jiàn)編碼方式是以配送中心節(jié)點(diǎn)（一般用0 表示） 作為子路徑的分隔符，如0-1-2-3-0-4-5-6-0 表示0-1-2-3-0 和0-4-5-6-0 兩條子路徑。一方面，這種方法需預(yù)先估計(jì)最小車輛數(shù)（需求總重量/車輛最大載重量），然而在有時(shí)間窗約束的前提下，車輛在進(jìn)行服務(wù)時(shí)并不一定能滿載出發(fā)，易導(dǎo)致車輛的預(yù)估不足；另一方面，算法經(jīng)過(guò)鄰域交換產(chǎn)生的新解不一定是可行解，需要進(jìn)行檢驗(yàn)，增大算法運(yùn)行開(kāi)銷。

基于此，本文選用的編碼方法為首先生成一條主路徑，然后將主路徑劃分為幾條子路徑，所以劃分算法的優(yōu)劣對(duì)TS 算法的性能舉足輕重。Beasley[21]以車輛的載重量為劃分節(jié)點(diǎn)，若加上當(dāng)前顧客的需求，子路徑的總需求大于車輛的容量，則以當(dāng)前顧客為起點(diǎn)產(chǎn)生一條新的子路徑繼續(xù)進(jìn)行劃分，直到主路徑劃分完畢。這種方法雖然效率很高，但對(duì)主路徑的顧客順序依賴性很強(qiáng)。李進(jìn)等[22]繼承了Beasley 的劃分思想，提出了一種WSS（Weight and Speedbased Split） 劃分算法，但是對(duì)于VRPSPDTW 問(wèn)題來(lái)說(shuō)，這種方法沒(méi)有考慮時(shí)間窗以及顧客的取貨需求對(duì)路徑劃分的影響。因此本文對(duì)WSS 進(jìn)行改進(jìn)，提出適合VRPSPDTW 模型的WTS（Weight and Timebased Split） 算法，WTS 算法的具體步驟如下：

步驟1：初始化

假設(shè)節(jié)點(diǎn)i 的最小總費(fèi)用（指車輛從配送中心出發(fā)，依次完成該節(jié)點(diǎn)及其前面所有節(jié)點(diǎn)的任務(wù)后返回配送中心這一過(guò)程中所發(fā)生的費(fèi)用之和，包括固定成本和運(yùn)輸成本） 為V［i ］，節(jié)點(diǎn)i 的最小總費(fèi)用路徑的直接前繼節(jié)點(diǎn)（指上一輛車服務(wù)的最后一個(gè)客戶） 為P［i ］。

令V［i ］=∞，V［0 ］=0，P［i ］=i-1，?i∈V；

步驟2：最優(yōu)路徑劃分

計(jì)算每個(gè)客戶節(jié)點(diǎn)i （i=1，2，…，n ）的最小總費(fèi)用以及直接前繼節(jié)點(diǎn)，置i=1；

步驟2.1 令當(dāng)前車輛的載重量load=0，總費(fèi)用cost=0，令j=i；

步驟2.2 load=load+第j 個(gè)節(jié)點(diǎn)的需求量；

步驟2.3 若load＞Q 或不滿足時(shí)間窗，則i=i+1，轉(zhuǎn)步驟2.1；否則轉(zhuǎn)步驟2.4；

步驟2.4 若V ［j- 1 ］+cost＜V［j ］，則V［j ］=V ［j- 1 ］+cost，P［j ］=i-1；

步驟3 算法終止

所有顧客都被插入路徑中，若j＞n，則算法結(jié)束，否則令j=j+1，轉(zhuǎn)步驟2.2。

2.2 初始解的構(gòu)造

標(biāo)準(zhǔn)TS 算法隨機(jī)生成初始解進(jìn)行迭代搜索，這種生成方法雖然簡(jiǎn)單有效，但是Tan 等[23]研究發(fā)現(xiàn)TS 算法對(duì)初始解有一定的依賴性，初始解的優(yōu)劣將最終影響最優(yōu)解的質(zhì)量。為了保證初始解的質(zhì)量，本文對(duì)Dethloff[24]解決VRPSPD 問(wèn)題時(shí)提出的RCRS（Residual Capacity Radial Surcharge） 算法進(jìn)行改進(jìn)，加入時(shí)間窗約束，生成初始解。

RCRS 算法的具體步驟如下：

步驟1：選擇種子客戶

計(jì)算所有未路由的客戶的最早開(kāi)始服務(wù)時(shí)間 （=max ｛車輛從配送中心到達(dá)顧客的時(shí)間，顧客允許的最早時(shí)間窗｝），選擇開(kāi)始服務(wù)時(shí)間最小的客戶作為種子客戶。

步驟2：判斷是否有可插入位置

步驟2.1 種子客戶選好后，生成初始路徑（如0-1-0，該路徑有2 個(gè)插入位置）。判斷是否存在未路由客戶，若存在，繼續(xù)下述步驟，否則轉(zhuǎn)步驟4。

步驟2.2 依次判斷未路由客戶是否滿足插入位置的要求（載重量約束，時(shí)間窗約束），若存在可插入位置，轉(zhuǎn)步驟3，否則轉(zhuǎn)步驟1。

步驟3：計(jì)算可插入位置RCRS 標(biāo)準(zhǔn)值

計(jì)算可插入位置的RCRS 標(biāo)準(zhǔn)值，計(jì)算方法與文獻(xiàn)[24]相同，最后選擇RCRS 標(biāo)準(zhǔn)值最小的客戶插入，然后轉(zhuǎn)步驟2.2。

步驟4：算法終止

所有客戶都被插入路徑，算法終止。

2.3 鄰域結(jié)構(gòu)設(shè)計(jì)

禁忌搜索基于鄰域變換進(jìn)行搜索，確定鄰域操作至關(guān)重要。WTS 編碼方法使得鄰域操作時(shí)簡(jiǎn)單方便，只需進(jìn)行內(nèi)部操作即可。本文選用3 種廣泛應(yīng)用于車輛路徑問(wèn)題的鄰域結(jié)構(gòu)，操作時(shí)隨機(jī)選擇其中一種。例如解為123456，下劃線處為隨機(jī)選擇的兩個(gè)顧客i 和j，結(jié)果如下：

（1） 點(diǎn)交換。將顧客i 和j 的位置互換，得到：153426；

（2） 點(diǎn)插入。將顧客i 插入到j(luò) 后，得到：134526；

（3） 點(diǎn)逆序。將顧客i 和j 之間的顧客逆序，得到：124356。

2.4 禁忌對(duì)象及禁忌長(zhǎng)度

將移動(dòng)元素作為禁忌對(duì)象，對(duì)三種鄰域操作，建立三個(gè)禁忌表來(lái)存儲(chǔ)相應(yīng)的禁忌對(duì)象。禁忌長(zhǎng)度的確定是TS 算法的關(guān)鍵，決定了禁忌時(shí)間的長(zhǎng)短，從而影響解的搜索范圍和質(zhì)量，禁忌長(zhǎng)度過(guò)短則易陷入循環(huán)，算法難以跳出局部最優(yōu)點(diǎn)；過(guò)長(zhǎng)則會(huì)加大數(shù)據(jù)存儲(chǔ)量，甚至導(dǎo)致算法無(wú)法繼續(xù)進(jìn)行。標(biāo)準(zhǔn)TS 選用固定的禁忌長(zhǎng)度，然而對(duì)于不同的問(wèn)題很難確定統(tǒng)一的禁忌長(zhǎng)度。響應(yīng)性禁忌搜索算法（Reactive Tabu Search，RTS） 對(duì)標(biāo)準(zhǔn)禁忌搜索算法進(jìn)行改進(jìn)，基于解的重復(fù)次數(shù)和解的重復(fù)時(shí)間差在搜索過(guò)程中動(dòng)態(tài)調(diào)整禁忌長(zhǎng)度。調(diào)整規(guī)則有兩種方式，一是解重復(fù)出現(xiàn)的間隔在設(shè)定的最大間隔之內(nèi)，表明禁忌長(zhǎng)度過(guò)短，增大禁忌長(zhǎng)度；二是當(dāng)前時(shí)間距離上次禁忌長(zhǎng)度發(fā)生改變的時(shí)間超過(guò)預(yù)設(shè)值，表明搜索區(qū)域過(guò)大，減小禁忌長(zhǎng)度。若解的重復(fù)次數(shù)超過(guò)預(yù)設(shè)值，表明解陷入混沌，即陷入局部最優(yōu)，此時(shí)算法采用逃離機(jī)制，跳出當(dāng)前區(qū)域，重新進(jìn)行搜索。為了避免禁忌過(guò)度，每當(dāng)歷史最優(yōu)解被更新，清空禁忌表，使搜索更自由。RTS 算法具體步驟如下：

步驟1：初始化RTS 相關(guān)參數(shù)

步驟2：RTS 算法框架

步驟2.1：生成候選解，找出當(dāng)前最優(yōu)解；

步驟2.2：把當(dāng)前最優(yōu)解存入Hash 表，判斷是否重復(fù)，若重復(fù)，轉(zhuǎn)步驟2.3，反之轉(zhuǎn)步驟2.5；

步驟2.3：解重復(fù)次數(shù)chaotic=chaotic+1，若chaotic＞混沌標(biāo)志數(shù)chaos，轉(zhuǎn)步驟3，反之轉(zhuǎn)2.4；

步驟2.4：判斷重復(fù)間隔R 是否超過(guò)預(yù)設(shè)值Rave，若R＜Rave，禁忌長(zhǎng)度，L=1.1*L，Rave=0.1*R+0.9*Rave，反之轉(zhuǎn)步驟4；

步驟2.5：判斷當(dāng)前時(shí)間距離上次禁忌長(zhǎng)度發(fā)生改變的時(shí)間tT 是否超過(guò)預(yù)設(shè)值GapMax，若tT＞GapMax，L=0.9*L，轉(zhuǎn)步驟4，反之轉(zhuǎn)步驟4。

步驟3：逃離機(jī)制

跳出當(dāng)前搜索區(qū)域，重新生成初始解進(jìn)行搜索。

步驟4：算法終止

達(dá)到預(yù)先設(shè)定最大迭代步數(shù)，算法終止。

2.5 ITS 算法流程

下面給出ITS 算法的具體流程。

步驟1 初始化

輸入各改進(jìn)策略的算法參數(shù)；設(shè)置算法終止條件：迭代代數(shù)達(dá)到最大迭代數(shù)Nmax或者達(dá)到允許最優(yōu)解未改進(jìn)的最大次數(shù)Emax；設(shè)迭代計(jì)數(shù)器t=0，最好解未改進(jìn)次數(shù)t1=0；采用改進(jìn)RCRS 算法生成初始解S，并把該解置為Sbest和Snow，計(jì)算初始解的適應(yīng)度值F（S ）；當(dāng)前候選解數(shù)目n=0，最大候選解數(shù)目為nmax，候選集為C。

步驟2 生成候選解

從三種鄰域變換中隨機(jī)選取一種作用于當(dāng)前解Snow生成候選解S'，將S'置入候選集C 中，n=n+1；若n＞nmax，轉(zhuǎn)步驟3，反之轉(zhuǎn)步驟2。

步驟3 候選解排序

采用WTS 算法對(duì)C 集合中的候選解進(jìn)行解碼計(jì)算，選出當(dāng)前最優(yōu)解S*，記錄其適應(yīng)度值F （S*）。

步驟4 調(diào)整禁忌長(zhǎng)度

將F （S*）代入RTS 算法，動(dòng)態(tài)調(diào)整禁忌長(zhǎng)度L。

步驟5 更新統(tǒng)計(jì)信息

若F （S*）＞=F （Sbest），則t1=t1+1；否則Sbest=S*，t1=0，Snow=S*。

步驟6 更新禁忌表

將當(dāng)前解S*的禁忌對(duì)象放入禁忌表中。

步驟7 算法終止

若t＞Nmax或t1＞Emax，算法終止輸出最優(yōu)解Sbest，否則轉(zhuǎn)步驟2。

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

3.1 測(cè)試環(huán)境與測(cè)試數(shù)據(jù)

實(shí)驗(yàn)環(huán)境如下：Intel（R） Core（TM） i7-8550U CPU，8GB RAM，操作系統(tǒng)為Window 10，編程環(huán)境為C#。

Wang 等[14]提出的測(cè)試算例已成為求解VRPSPDTW 問(wèn)題的國(guó)際通用算例，本文亦選取該算例進(jìn)行實(shí)驗(yàn)。為避免偶然性，每個(gè)算例獨(dú)立運(yùn)行20 次，取其中的最優(yōu)值作為實(shí)驗(yàn)結(jié)果。

3.2 實(shí)驗(yàn)一

為驗(yàn)證改進(jìn)策略對(duì)TS 算法性能的提升，選取9 個(gè)小規(guī)模算例進(jìn)行實(shí)驗(yàn)，將結(jié)果與標(biāo)準(zhǔn)TS 算法進(jìn)行比較。實(shí)驗(yàn)對(duì)比結(jié)果如表1 所示，其中，NV（Number of Vehicle） 表示所需要的車輛數(shù)；TD（Travel Distance） 表示總運(yùn)輸距離；Gap 表示2 個(gè)算法的差距，其中TD%= （改進(jìn)TS-標(biāo)準(zhǔn)TS ）/改進(jìn)TS。觀察發(fā)現(xiàn)，9 組測(cè)試算例中，改進(jìn)TS 在NV 目標(biāo)值上有2 組優(yōu)于標(biāo)準(zhǔn)TS，而對(duì)于TD 目標(biāo)值，改進(jìn)效果明顯，共有6 組有較大改進(jìn)，最大改進(jìn)率為3.06%。

表1 小規(guī)?？蛻舾倪M(jìn)TS 與標(biāo)準(zhǔn)TS 實(shí)驗(yàn)結(jié)果對(duì)比

為了進(jìn)一步研究ITS 和TS 的算法的收斂性能，選取RCdp5001 算例，其最優(yōu)結(jié)果的迭代過(guò)程如圖1 所示，x 軸表示算法迭代次數(shù)，y 軸表示目標(biāo)函數(shù)TD 值。由圖1 中可以看出，RCRS 算法保證ITS 算法比TS 算法隨機(jī)生成的初始解更優(yōu)，更有利于接下來(lái)的搜索，RTS 算法動(dòng)態(tài)調(diào)整禁忌長(zhǎng)度，提高跳出局部最優(yōu)的可能性，ITS 算法可以更快的跳出局部最優(yōu)。

3.3 實(shí)驗(yàn)二

為進(jìn)一步測(cè)試ITS 算法的有效性，選取9 個(gè)小規(guī)模算例和10 個(gè)大規(guī)模算例進(jìn)行實(shí)驗(yàn)，將實(shí)驗(yàn)結(jié)果與Wang 等[14]設(shè)計(jì)的遺傳算法（Genetic Algorithm，GA）、Wang 等[16]設(shè)計(jì)的并行模擬退火算法（parallel-Simulated Annealing，p-SA）、王超等[17]設(shè)計(jì)的離散布谷鳥(niǎo)算法（Discrete Cuckoo Search，DCS） 取得的最優(yōu)實(shí)驗(yàn)結(jié)果進(jìn)行比較，對(duì)比結(jié)果如表2 所示。

觀察結(jié)果得出，9 組小規(guī)模算例中，1 組算例更新了最優(yōu)解，7 組算例達(dá)到最優(yōu)解，1 組算例略差于最優(yōu)解。對(duì)于10 組大規(guī)模算例，4 組算例更新了最優(yōu)解，最大改進(jìn)率為8.40%，2 組算例達(dá)到最優(yōu)解，1 組算例NV 多1 輛，但TD 改進(jìn)0.51%，剩余3 組算例結(jié)果略差于最優(yōu)解。通過(guò)實(shí)驗(yàn)可以看出，改進(jìn)禁忌搜索算法加入RCRS 算法和RTS 算法后，能更有效地跳出局部最優(yōu)進(jìn)行搜索，加快尋優(yōu)速度，驗(yàn)證了改進(jìn)策略的有效性。

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

本文研究了帶時(shí)間窗的同時(shí)取送貨車輛路徑問(wèn)題，以車輛的固定成本、運(yùn)輸成本、車輛超時(shí)的時(shí)間窗成本、貨物的貨損成本、保鮮的制冷成本以及考慮環(huán)保的碳排放成本之和為目標(biāo)構(gòu)建了配送模型?；跇?biāo)準(zhǔn)TS 的框架，采用RCRS 插入算法生成初始解，進(jìn)行鄰域搜索時(shí)，應(yīng)用WTS 算法進(jìn)行路徑劃分，減少了可行解的驗(yàn)證時(shí)間，RTS 算法動(dòng)態(tài)調(diào)整禁忌長(zhǎng)度，提高搜索的效率，通過(guò)與標(biāo)準(zhǔn)算例的對(duì)比，結(jié)果表明ITS 算法在求解該問(wèn)題上能得到可接受的可行解。

本文沒(méi)有考慮車輛行駛速度帶來(lái)的影響，后續(xù)研究中將考慮速度隨時(shí)間而變化，即解決時(shí)間依賴性帶時(shí)間窗的同時(shí)取送貨問(wèn)題（TDVRPSPDTW），對(duì)速度可變情況下車輛調(diào)度進(jìn)行規(guī)劃，來(lái)尋得最優(yōu)調(diào)度。

圖1 改進(jìn)TS 與標(biāo)準(zhǔn)TS 進(jìn)化過(guò)程比較

表2 比較GA、p-SA、DCS 和ITS 算法的結(jié)果