李國明，李軍華

(南昌航空大學(xué) 江西省圖像處理與模式識別重點(diǎn)實(shí)驗(yàn)室，江西 南昌 330063)

0 引言

物流配送線路規(guī)劃問題(logistics distribution route planning problem)是目前大型物流配送管理中的核心問題之一，通常歸結(jié)為車輛路徑問題(Vehicle Routing Problem, VRP)。該問題指配送中心根據(jù)客戶需求安排車輛對貨物進(jìn)行派發(fā)，車輛從配送中心出發(fā)，到達(dá)指定地點(diǎn)，最后回到配送中心，其中需要考慮車輛的時間約束、容量約束等約束條件。因?yàn)檠芯縑RP能有效處理運(yùn)輸過程中訂單分配不合理、運(yùn)輸延誤率高等情況，所以該問題自提出以來就受到國內(nèi)外眾多學(xué)者的廣泛關(guān)注，并提出基于VRP的精確算法[1-3]和基于VRP的啟發(fā)式算法[4-7]。VRP主要有3個不同的研究角度：

(1)帶時間窗的車輛路徑問題

在實(shí)際配送中，客戶會對貨物送達(dá)時間區(qū)間提出嚴(yán)格要求。針對此類問題，XU等[8]提出混合遺傳算法和粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法，利用粒子實(shí)數(shù)編碼方法對路徑進(jìn)行解碼來減輕計(jì)算負(fù)擔(dān)，同時與遺傳算法的交叉算子相結(jié)合，避免陷入局部最優(yōu)。NIU等[9]提出基于膜計(jì)算(membrane computing)的混合進(jìn)化算法，將遺傳算法中常用的二進(jìn)制編碼改進(jìn)為整數(shù)編碼，既可避免編碼冗余問題，又可提高算法的實(shí)用性和計(jì)算效率。該方法在單次配送VRP中效果較好，但未考慮多個配送中心同時配送的情景。戚遠(yuǎn)航等[10]提出一種離散蝙蝠算法(Discrete Bat Algorithm,DBA)，利用DBA尋優(yōu)能力強(qiáng)、魯棒性好等特性來解決帶時間窗的VRP，然而該算法未考慮客戶需求的隨機(jī)性。

(2)隨機(jī)需求車輛路徑問題

在實(shí)際配送中，若設(shè)定客戶需求為隨機(jī)變量，則稱為隨機(jī)需求車輛路徑問題(Vehicle Routing Problem with Stochastic Demand,VRPSD)。為了解決這一問題，GUTIERREZ等[11]設(shè)計(jì)了一種混合元啟發(fā)式算法，該算法結(jié)合了文化基因算法和貪婪隨機(jī)算法，通過與現(xiàn)有的元啟發(fā)式方法比較，驗(yàn)證了該方法的有效性；李陽等[12]根據(jù)先預(yù)優(yōu)化后重調(diào)度的思想，提出兩階段混合變鄰域分散搜索(Variable Neighborhood Scatter Search, VNSS)算法，該算法求解穩(wěn)定且平均誤差小，但求解大規(guī)模問題的能力較差，耗時較長。

(3)帶時間窗的隨機(jī)需求車輛路徑問題

在實(shí)際配送中，若設(shè)定客戶需求為隨機(jī)變量，且客戶對貨物送達(dá)時間區(qū)間提出要求，則稱為帶時間窗的隨機(jī)需求車輛路徑問題(Vehicle Routing Problem with Stochastic Demand and Time Window, VRPSD-TW)，目前求解VRPSD-TW問題均采用兩階段帶修正隨機(jī)規(guī)劃模型。第一階段，制定一組預(yù)計(jì)送貨路線；第二階段，顯示客戶實(shí)際需求，采用修正算法對第一階段所得解進(jìn)行修正。修正算法主要包括兩種：①車輛到達(dá)指定地點(diǎn)A后，直接回到配送中心重新對B點(diǎn)進(jìn)行貨物派送；②車輛到達(dá)B點(diǎn)后，才發(fā)現(xiàn)剩余容量不足，需要回配送中心重新裝載貨物。顯然，情況②下的成本更大。

近年來，由于快遞物流業(yè)飛速發(fā)展，帶軟時間窗的隨機(jī)需求車輛路徑問題(Vehicle Routing Problem with Stochastic Demand and Soft Time Window, VRPSD-STW)更符合實(shí)際。針對此類問題中的客戶需求是隨機(jī)的，LEI等[13]提出DTD(detour-to-depot)修正算法，即只有當(dāng)車輛剩余容量為零時，車輛才會回配送點(diǎn)重新裝載貨物，否則繼續(xù)為下一客戶提供服務(wù)。該方法忽略了下一個客戶的實(shí)際需求，導(dǎo)致車輛必須回配送中心重新裝載貨物，造成巨額成本。ZHANG等[14]提出一種預(yù)防性補(bǔ)貨思想，即根據(jù)公式預(yù)先設(shè)定一個閾值，當(dāng)車輛服務(wù)完一個客戶后，如果剩余容量小于或等于該閾值，則回配送中心重新裝載貨物，然后為下一客戶提供服務(wù)，否則直接為下一客戶提供服務(wù)。文獻(xiàn)[15-16]對預(yù)防性補(bǔ)貨策略進(jìn)行了進(jìn)一步改進(jìn)，文獻(xiàn)[15]提出當(dāng)車輛服務(wù)完當(dāng)前客戶后，若其剩余容量低于路線上下一個客戶預(yù)期需求的η倍時(η通常取1)，則回到配送中心重新裝載貨物，否則繼續(xù)為下一個客戶提供服務(wù)，該策略進(jìn)一步降低了修正成本；文獻(xiàn)[16]提出一種混合算法，設(shè)定最大行進(jìn)閾值和最小補(bǔ)貨閾值，根據(jù)公式得出風(fēng)險(xiǎn)確定值，若該值大于最小補(bǔ)貨閾值，則回配送中心重新裝載貨物，否則繼續(xù)對下一個客戶服務(wù)。本文在ZHANG等[14]提出的模型上進(jìn)行擴(kuò)展，在第一階段制定車輛預(yù)計(jì)送貨路線時便加入了軟時間窗約束，并令客戶需求服從離散均勻分布。

上述文獻(xiàn)中，針對小規(guī)模隨機(jī)需求車輛問題的求解效果較好，大規(guī)模隨機(jī)需求車輛問題的求解過程則十分復(fù)雜，而且效果不是很好。目前，求解VRPSD-STW的啟發(fā)式算法[4-7]較少，該類算法可以解決大規(guī)模VRP，且運(yùn)算速度較快。

基于上述分析，本文主要研究VRPSD-STW，針對求解時間較長、客戶需求隨機(jī)且車輛行駛路徑修正成本較大的問題，提出一種二階段算法。第一階段將客戶的隨機(jī)需求作確定化處理，使其等于期望值，再運(yùn)用改進(jìn)的禁忌搜索(Tabu Search, TS)算法進(jìn)行求解；第二階段用選擇回配送中心(Select Return to Depot，SRTD)算法對第一階段所得解進(jìn)行修正，修正成本較小。

本文算法的主要創(chuàng)新點(diǎn)如下：①對第一階段使用的TS算法[17-19]中的禁忌長度、鄰域結(jié)構(gòu)進(jìn)行自適應(yīng)調(diào)整，并引入自適應(yīng)懲罰系數(shù)，不但有利于算法減少搜索最優(yōu)解的時間，而且可以避免陷入局部最優(yōu)。②第二階段采用SRTD算法對第一階段所得解修正。首先判斷車輛剩余容量是否小于客戶實(shí)際最大需求，是則計(jì)算車輛不考慮后續(xù)客戶(i+2,i+3,…)，對客戶i服務(wù)后繼續(xù)對客戶i+1服務(wù)所產(chǎn)生的成本及對客戶i服務(wù)后直接回配送中心重新裝載貨物所產(chǎn)生的成本，然后將所得成本進(jìn)行比較并確定閾值，最終決定車輛服務(wù)完當(dāng)前客戶后繼續(xù)服務(wù)下一客戶還是回配送中心重新裝載貨物。該方法提高了車輛的靈活性，極大地降低了修正成本。

1 相關(guān)工作

1.1 禁忌搜索算法

TS算法是一種現(xiàn)代啟發(fā)式算法，由Fred Glover教授[20]于1986年提出，是一種改進(jìn)的局部搜索算法。該算法在每次迭代時從當(dāng)前解s∈S移動到其鄰域N(s)的最優(yōu)解來探索解空間，S表示滿足約束條件的一組可行解。為了避免陷入局部最優(yōu)，通過設(shè)置禁忌表來禁忌一些已經(jīng)歷的搜索過程。TS算法一般由禁忌長度、鄰域結(jié)構(gòu)、選擇策略和特赦準(zhǔn)則組成。

在TS算法中，鄰域結(jié)構(gòu)是算法有效與否的關(guān)鍵，目前主要的鄰域結(jié)構(gòu)有2-opt鄰域、Relocate鄰域和Swap鄰域[17]。

(1)2-opt鄰域 隨機(jī)選取一條路徑，在路徑上隨機(jī)選取兩點(diǎn)Si-1和Sm-1，將Si-1到Sm-1之間的路徑翻轉(zhuǎn)。

(2)Relocate鄰域 表示選取一條路徑，在路徑上隨機(jī)選取一個客戶，將其從目前所屬的位置上移除，插入到其他任意位置。例如，將Si-1從路徑上移除，插入到Si+1處；將Si從路徑上移除，插入到Sm處；將Sm-1從路徑上移除，插入到Si處。

(3)Swap鄰域 隨機(jī)選取兩條路徑，在每條路徑上隨機(jī)選取一個客戶，交換其位置。例如，在路徑s上選取si-1,在路徑t上選取ti,交換其位置；在路徑t上選取ti-1,在路徑s上選取si,交換其位置；在路徑s上選取si,在路徑t上選取ti+1,交換其位置；在路徑t上選取ti,在路徑s上選取si+1,交換其位置。

圖1所示為3種鄰域結(jié)構(gòu)的具體變換示意圖。

在禁忌搜索算法中，只有當(dāng)?shù)螖?shù)超過最大預(yù)設(shè)值maxT或最優(yōu)解連續(xù)T次不更新時，算法才停止迭代并返回最優(yōu)解，具體流程如算法1所示。

算法1基本禁忌搜索算法框架。

1.隨機(jī)產(chǎn)生初始解s，清空禁忌表

2.If s滿足收斂條件

3. 將s作為當(dāng)前解

4. Repeat

6. If s′在禁忌表中

7. If s′滿足藐視準(zhǔn)則

8. 將s′作為當(dāng)前解

9. end

10. else

12. end if

13. 達(dá)到迭代終止條件

14. end

1.2 修正算法

修正算法(modified algorithm)主要用來解決帶不確定信息的VRP，一般常用于隨機(jī)VRP和動態(tài)VRP。如果配送中心對車輛行駛路徑進(jìn)行規(guī)劃時未充分考慮不確定信息，則會導(dǎo)致車輛無法為規(guī)劃路徑上的所有客戶提供服務(wù)，造成路線失敗，使整個車輛配送系統(tǒng)癱瘓。修正算法能有效解決路線失敗問題，使車輛配送系統(tǒng)重新運(yùn)轉(zhuǎn)，重新安排車輛為客戶提供服務(wù)。目前，主要的修正算法如下：

(1)車輛為某客戶提供服務(wù)后，其剩余容量為零，配送中心安排附近其他車輛為該路徑的剩余客戶提供服務(wù)。

(2)車輛為某客戶提供服務(wù)后，其剩余容量為零，安排該車輛回配送中心重新裝載貨物，然后繼續(xù)服務(wù)下一客戶。

(3)車輛為某客戶提供服務(wù)后，其剩余容量為零，配送中心按區(qū)域統(tǒng)計(jì)剩余客戶，重新安排車輛分別服務(wù)不同區(qū)域的客戶。

2 問題描述及數(shù)學(xué)模型

2.1 問題描述

在VRPSD-STW中，客戶需求未知和每個客戶都有其時間窗口的限制是兩個重要的部分。

(1)需求未知 在制定行駛路線時，客戶需求通常為隨機(jī)變量，只知其滿足某種概率分布，如正態(tài)分布、對數(shù)正態(tài)分布、離散均勻分布。因?yàn)榭蛻舻膶?shí)際需求間斷且不連續(xù)，所以本文采用離散均勻分布來顯示客戶需求。

(2)時間窗口 車輛未按設(shè)定的時間窗要求到達(dá)客戶點(diǎn)時，雖然可以對客戶進(jìn)行服務(wù)，但是必須給予相應(yīng)的懲罰，而且每個客戶只可由一輛車服務(wù)。

如果該客戶需求超過車輛剩余容量，則路線失敗，車輛停止服務(wù)。此時需要采取措施進(jìn)行彌補(bǔ)，例如在恢復(fù)送貨服務(wù)前，車輛可以返回配送中心重新裝載，從而增加了額外行駛時間，脫離了剩余客戶原先設(shè)置的時間窗。因此，客戶隨機(jī)需求、時間窗的設(shè)定是影響車輛能否按時送貨的一個關(guān)鍵問題。

2.2 建立VRPSD-STW數(shù)學(xué)模型

求解VRP首先需要綜合道路網(wǎng)絡(luò)信息。方便起見，道路網(wǎng)絡(luò)用無向完全圖G=(V0,A)表示，其中V0={0,V}為配送點(diǎn)與客戶點(diǎn)之間的集合(0表示配送中心,V={1,2,…,n}表示客戶點(diǎn)集)，A={(i,j):i,j∈V0,i≠j}為車輛在行駛過程中所經(jīng)過路段的集合，該集合有3種情況：①當(dāng)i=0,j∈V時，A表示車輛在配送點(diǎn)與客戶點(diǎn)之間行駛所經(jīng)過路段的集合；②當(dāng)i,j∈V且i≠j時，A表示車輛在客戶點(diǎn)之間行駛所經(jīng)過路段的集合；③當(dāng)i∈V,j=0時，A表示車輛在客戶點(diǎn)與配送點(diǎn)之間行駛所經(jīng)過路段的集合。C={c(i,j):i,j∈V0,i≠j}表示客戶i與客戶j之間的距離。假設(shè)車輛以單位速度行駛，則車輛從客戶i行駛到客戶j所需的時間tij等于客戶i與客戶j之間的距離c(i,j)，c(i,j)一般用最短路徑算法[21]求解。

(1)目標(biāo)函數(shù)

VRPSD-STW屬于運(yùn)籌學(xué)中的組合優(yōu)化問題。假設(shè)有K輛車為分布在不同位置的n個客戶提供服務(wù)，要求車輛在勻速行駛的情況下花費(fèi)時間最少、違背約束懲罰成本和修正成本最小。因此，構(gòu)建目標(biāo)函數(shù)

(1)

式中：tij為車輛從客戶i行駛到客戶j所需的時間；xijk為決策變量，若車輛k從客戶i行駛到客戶j，則為1，否則為0；nk為車輛k服務(wù)的客戶總數(shù)；λ1j為車輛提前到達(dá)客戶j的懲罰系數(shù)；E(Wjk)表示車輛k到達(dá)客戶j的期望提前時間；λ2j為車輛延遲到達(dá)客戶j的懲罰系數(shù)；E(Pjk)為車輛k到達(dá)客戶j的期望延遲時間；E(Lk)為配送中心對路徑L進(jìn)行修正所產(chǎn)生的期望成本。Wjk,Pjk,xijk的表達(dá)式分別為：

Wjk=max{aj-Ajk,0},j∈Rk,

1≤j≤nk,k∈K；

(2)

Pjk=max{Ajk-bj,0},j∈Rk,

1≤j≤nk,k∈K；

(3)

xijk={0,1},?i,j∈V0,k∈K。

(4)

式中：Ajk表示車輛k到達(dá)客戶j的時間；aj,bj表示客戶j時間窗的下界與上界；Rk表示車輛k行駛的路徑。

(2)約束函數(shù)

為了使所求解的VRP更加符合實(shí)際，構(gòu)建約束函數(shù)如下：

1)需求不可拆分約束 該約束表示客戶只能由一輛車服務(wù)。如果車輛已為某客戶提供服務(wù)，則其他車輛不再考慮該客戶；如果車輛剩余容量不滿足該客戶需求，則回配送中心重新裝載貨物。

(5)

2)車輛容量約束 該約束表示車輛行駛路徑上的客戶總平均需求量不能超過車輛的最大容量，如果達(dá)到車輛容量約束，則完成該路徑規(guī)劃。

(6)

式中：E(εi)為客戶i的平均需求量；Q為車輛最大容量。

3)其他約束

(7)

(8)

(9)

其中：式(7)表示車輛k從配送中心出發(fā)服務(wù)完所有客戶后必須回到配送中心。xi0k為決策變量，如果車輛k服務(wù)客戶i后回到配送中心0則為1，否則為0；x0jk為決策變量，如果車輛k從配送中心0出發(fā)，行駛到客戶j所在地并對其服務(wù)，則為1，否則為0。式(8)表示每輛車對客戶服務(wù)后必須離開該客戶所在地。式(9)表示避免車輛行駛路徑中出現(xiàn)子回路，|Sk|為車輛k行駛路徑上的客戶總數(shù)。

3 VRPSD-STW所用算法

因?yàn)榭蛻粜枨鬄殡S機(jī)變量，滿足離散均勻分布，所以傳統(tǒng)啟發(fā)式算法不再適用。本文提出一種二階段算法，在第一階段將客戶需求進(jìn)行確定化處理，使其等于期望值，再采用改進(jìn)的自適應(yīng)禁忌搜索算法(Improved Adaptive Tabu Search algorithm, IATS)進(jìn)行求解，然而客戶需求為隨機(jī)變量，確定化處理的誤差較大；第二階段采用改進(jìn)修正方法修正第一階段的所得解，最終目的是使總成本最小。

3.1 IATS算法設(shè)計(jì)

本文采用IATS對禁忌長度、鄰域結(jié)構(gòu)進(jìn)行自適應(yīng)調(diào)整，并在算法中引入自適應(yīng)懲罰系數(shù)。

3.1.1 自適應(yīng)禁忌長度

算法采用自適應(yīng)禁忌長度與靜態(tài)禁忌長度的對比結(jié)果如圖2所示，可見算法采用自適應(yīng)禁忌長度比靜態(tài)禁忌長度更有優(yōu)勢。

3.1.2 自適應(yīng)懲罰系數(shù)

為了避免陷入局部最優(yōu)，本文加入一定非可行解以擴(kuò)大搜索空間。針對帶時間窗的VRP，候選路徑是否可行與能否滿足約束條件有關(guān)。

(1)初始狀態(tài)下 對于初始解s∈S,c(s)表示車輛總行駛時間，q(s)表示違反容量約束的總?cè)萘?，t(s)表示違反時間窗約束的總時間量，α,β分別表示對應(yīng)的懲罰系數(shù)，定義函數(shù)f(s)=c(s)+αq(s)+βt(s)來評價解s的優(yōu)劣。

(10)

(11)

(12)

3.1.3 鄰域結(jié)構(gòu)

為了使算法在更具靈活性同時避免陷入局部最優(yōu)，本文吸取變鄰域搜索算法的優(yōu)點(diǎn)，使鄰域結(jié)構(gòu)動態(tài)變化。經(jīng)過實(shí)驗(yàn)對比分析，采用改進(jìn)Relocate鄰域、“尾巴”交換和1-1交換組合的鄰域結(jié)構(gòu)，如果算法在當(dāng)前鄰域內(nèi)搜索停滯不前，則跳到另一鄰域內(nèi)繼續(xù)搜索。

(1)改進(jìn)Relocate鄰域 任意選取一個客戶i，將其從原路徑上移除，插入任意路徑L上。若其插入后違反容量約束，則針對客戶i將不再選取路徑L；若客戶i插入路徑L上，路徑L上存在兩個客戶p1,p2滿足ap1≤ai≤ap2,bp1≤bi≤bp2，則將客戶i插入這兩個客戶之間，否則將客戶i插入路徑L的末尾。

(2)“尾巴”交換 隨機(jī)選擇兩條路徑L0和L1，在路徑L0上隨機(jī)選取一點(diǎn)s0，在路徑L1上隨機(jī)選取一點(diǎn)s1，將s0和s1后面的“尾巴”(從被選頂點(diǎn)至線路終點(diǎn))互換(配送中心除外)。

(3)1-1交換 隨機(jī)選擇兩條路徑L0和L1，在路徑L0上隨機(jī)選取一點(diǎn)s0，在路徑L1上隨機(jī)選取一點(diǎn)s1，將節(jié)點(diǎn)s1插入路徑L0，將節(jié)點(diǎn)s0插入路徑L1。

3.1.4 改進(jìn)后的禁忌搜索算法步驟

在TS算法中，只有當(dāng)?shù)螖?shù)超過最大預(yù)設(shè)值maxT或最優(yōu)解連續(xù)T次不更新時，才停止迭代并返回最優(yōu)解。綜上所述，IATS具體流程如算法2所示。

算法2自適應(yīng)禁忌搜索算法。

輸入：客戶數(shù)量n，車輛最大容量Q，懲罰系數(shù)α，β，最大迭代次數(shù)Nmax，自適應(yīng)因子δ，禁忌長度θ，鄰域結(jié)構(gòu)Nh(h=1,2,3)。

輸出：全局最優(yōu)解sbest。

1.初始化

2.隨機(jī)生成初始可行解s

3.If s滿足約束條件

4. sbest=s,f(sbest)=f(s)

5.else

6. f(sbest)=∞

7.WhileT

8. For h=1 To hmaxdo

11. Select s′

12. If f(s′)

13. f(sbest)=f(s′)

14. s=s′

15. θ=θ-1

16. Continue to search with N1(s)(h=1)

17. Otherwiseh=h+1

18. θ=θ+1

19. End for

20.更新禁忌表和懲罰系數(shù)

21.Endwhile

22.輸出找到的最優(yōu)解

3.2 修正算法

因?yàn)樵O(shè)定客戶需求為滿足離散均勻分布的隨機(jī)變量，將其進(jìn)行確定化處理存在很大誤差，所以在第二階段采用修正算法修正第一階段的所得解。本文提出一種新的修正算法—SRTD算法。

3.2.1 修正算法設(shè)計(jì)

為了使總成本最小，第二階段提出的修正算法尤其重要，構(gòu)建目標(biāo)函數(shù)

(13)

式中：E(Lk)為配送中心對路徑L進(jìn)行修正產(chǎn)生的期望成本；nk為車輛k行駛路徑上的總客戶數(shù)；Fki為車輛k服務(wù)客戶i后的修正成本。借鑒文獻(xiàn)[22],Fki表達(dá)式為

(14)

(15)

(16)

wi+1=max{ai+1-(di+ci,i+1+2c1,i+1),0}；

(17)

li+1=max{(di+ci,i+1+2c1,i+1)-bi+1,0}；

(18)

(19)

(20)

其中：ai+1,bi+1為客戶i+1時間窗口的左右邊界；di為車輛離開客戶i的時間；ci,i+1為車輛從客戶i行駛到客戶i+1所需的時間；c1,i+1為車輛從客戶i+1所在地回到配送中心所需的時間；ci,1為車輛從客戶i所在地回到配送中心所需的時間；c1,i+1為車輛從配送中心行駛到客戶i+1處所需的時間。

車輛k服務(wù)客戶i后,可采用DTD算法或PR(preventive restocking)算法進(jìn)行修正，具體修正方案如圖3所示。

圖3a所示為第一階段得出的一條規(guī)劃路徑，[0 300]為配送中心的時間窗口；[0 155]為26號客戶的時間窗口；q=21為車輛服務(wù)完26號客戶后的剩余容量；40為26號客戶與34號客戶之間的距離；[0 225]為34號客戶的時間窗口；q={1,2,3,…,39}為34號客戶的需求分布；50為34號客戶與配送中心之間的距離。

圖3b所示為用DTD算法和PR算法對路徑進(jìn)行修正的結(jié)果，可見兩種算法的結(jié)果是一致的。點(diǎn)線線路表示車輛行駛至34號客戶時，發(fā)現(xiàn)車輛剩余容量并不滿足該客戶的需求，車輛需要返回配送中心重新裝載，因此產(chǎn)生額外成本；虛線線路表示車輛行駛至34號客戶時，其剩余容量滿足該客戶需求，不會產(chǎn)生額外成本。

用DTD算法對路徑進(jìn)行修正，當(dāng)車輛剩余容量為零時，車輛會回配送中心重新裝載貨物；用PR算法對路徑進(jìn)行修正，當(dāng)車輛剩余容量小于下一客戶的期望需求時，車輛會回配送中心重新裝載貨物。由于車輛服務(wù)完26號客戶后的剩余容量大于零且大于34號客戶的期望需求，用DTD算法和PR算法對該路徑進(jìn)行修正時的修正成本均為122.307。

用DTD算法和PR算法修正該路徑，當(dāng)車輛到達(dá)34號客戶時，剩余容量大概率不滿足該客戶需求，必須回配送中心重新裝載貨物。車輛被動回配送中心不僅會產(chǎn)生額外的行駛成本，還會因車輛無法準(zhǔn)時對客戶進(jìn)行服務(wù)而產(chǎn)生極大的懲罰成本。為了降低車輛被動回配送中心的概率，本文提出一種新方法，在車輛服務(wù)下一客戶前進(jìn)行判斷，若直接回配送中心的成本小，則先回配送中心重新裝載貨物，再繼續(xù)服務(wù)下一客戶。該方法有效降低了車輛因剩余容量不足而回配送中心重新裝載貨物的概率，具體的修正方案如圖4所示?？梢姡囕v服務(wù)26號客戶后沒有直接服務(wù)34號客戶，而是先回配送中心重新裝載貨物，再服務(wù)34號客戶，其中虛線線路為車輛將行駛的路徑。因此本文方法能夠避免車輛被動回配送中心裝載貨物，其修正成本為50，明顯優(yōu)于DTD算法和PR算法。

λ2,i+1li+1]pi+1；

(21)

(22)

3.2.2 修正算法步驟

本文所提算法要使每個客戶修正成本均最小，從而使車輛行駛路徑的修正成本最小。在車輛服務(wù)客戶前進(jìn)行選擇，如果車輛繼續(xù)服務(wù)產(chǎn)生的成本小，則繼續(xù)服務(wù)下一個客戶，否則回配送中心重新裝載貨物。因?yàn)榭蛻粜枨鬂M足離散均勻分布，所以確定客戶i+1的最大需求值maxεi+1。若qi≥maxεi+1，則車輛繼續(xù)服務(wù)客戶i+1；否則，根據(jù)式(21)和式(22)計(jì)算其所產(chǎn)生的成本，選擇車輛繼續(xù)服務(wù)或回配送中心重新裝載貨物。

如果qi

因?yàn)楸疚淖罱K目的是使修正成本最小，所以當(dāng)qi

綜上所述，修正算法的具體流程如算法3所示。

算法3SRTD修正算法。

輸入：客戶i+1需求εi+1，車輛服務(wù)客戶i后的剩余容量qi，路線失敗成本b，車輛違反時間窗的約束λ1,λ2。

輸出：修正成本E(Lk)。

1.初始化

2.輸入算法1所得最優(yōu)解

3.For k=1 To K do

4. For n=i To ienddo

5. If qi≥max εi+1

6.車輛k服務(wù)當(dāng)前客戶后繼續(xù)服務(wù)客戶i+1

8. 車輛k服務(wù)當(dāng)前客戶后直接回配送中心

11. If qi

12. 車輛k服務(wù)當(dāng)前客戶后直接回配送中心

13. Else

14. 車輛k服務(wù)當(dāng)前客戶后繼續(xù)服務(wù)客戶i+1

15. End for

16. End if

17. i=i+1

18. End for

19.k=k+1

20.End for

21.輸出找到的最優(yōu)解

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)環(huán)境

本文算法的相關(guān)實(shí)驗(yàn)均在同一實(shí)驗(yàn)環(huán)境中進(jìn)行，其中CPU主頻為2.80 GHz，內(nèi)存為8 GB，操作系統(tǒng)為64位Windows10，編程語言為C++和MATLAB語言。

4.2 實(shí)驗(yàn)結(jié)果與分析

4.2.1 實(shí)驗(yàn)1

采用Solomon的6種類型VRPTW算例(C1類型、C2類型、R1類型、R2類型、RC1類型和RC2類型，共56個算例)[23]測試IATS，然后將IATS與DBA[10]、自適應(yīng)文化基因算法(Adaptive Memetic Algorithm, AMA)[24]、PSO算法[25]進(jìn)行對比，結(jié)果如表1和表2所示。表中：OS為算法獨(dú)立運(yùn)行10次后獲得的最優(yōu)解；AS為算法獨(dú)立運(yùn)行10次后獲得的平均解；Time為算法運(yùn)行時間。

表1 IATS與其他算法的對比實(shí)驗(yàn)結(jié)果

由表1可見，IATS具有魯棒性較好、運(yùn)行時間較短等優(yōu)點(diǎn)，主要表現(xiàn)如下：

(1)在C1類測試算例中，IATS的最優(yōu)解略差于DBA和AMA，但優(yōu)于PSO；在平均解和時間耗費(fèi)方面，IATS略差于AMA，但優(yōu)于DBA和PSO。

(2)在C2類測試算例中，IATS的最優(yōu)解略差于其他3種算法；在平均解方面，IATS略差于AMA和PSO，但優(yōu)于DBA；在時間耗費(fèi)方面，IATS優(yōu)于其他3種算法。

(3)在R1，RC1類測試算例中，IATS的最優(yōu)解略差于DBA，但優(yōu)于AMA和PSO；在平均解方面，IATS略差于DBA，但優(yōu)于AMA和PSO；在時間耗費(fèi)方面，IATS優(yōu)于其他算法。

(4)在R2類測試算例中，IATS在最優(yōu)解、平均解和時間耗費(fèi)方面均優(yōu)于其他3種算法。

(5)在RC2類測試算例中，IATS的最優(yōu)解和平均解均優(yōu)于其他3種算法；在時間耗費(fèi)方面，IATS略差于DBA，但優(yōu)于AMA和PSO。

由表2可見，在大多數(shù)情況下，IATS得到的最優(yōu)解、平均解，以及在時間耗費(fèi)方面均優(yōu)于其他算法，具有一定的競爭性，主要表現(xiàn)如下：

(1)在R201，C101，RC201測試算例中，IATS在最優(yōu)解、平均解和時間耗費(fèi)方面均優(yōu)于其他3種算法。

(2)在R204測試算例中，IATS的最優(yōu)解和平均解均優(yōu)于其他3種算法；在時間耗費(fèi)方面，IATS略差于DBA，但優(yōu)于AMA和PSO。

(3)在C201測試算例中，IATS的最優(yōu)解略差于其他3種算法；在平均解方面，IATS略差于AMA和PSO，但優(yōu)于DBA；在時間耗費(fèi)方面，IATS優(yōu)于其他3種算法。

(4)在C204測試算例中，IATS的最優(yōu)解略差于其他3種算法；在平均解方面，IATS略差于DBA和AMA，但優(yōu)于PSO；在時間耗費(fèi)方面，IATS優(yōu)于其他3種算法。

(5)在RC101測試算例中，IATS的最優(yōu)解略差于DBA和PSO，但優(yōu)于AMA；在平均解方面，IATS略差于DBA，但優(yōu)于AMA和PSO；在時間耗費(fèi)方面，IATS優(yōu)于其他3種算法。

(6)在RC208測試算例中，IATS的最優(yōu)解優(yōu)于其他3種算法；在平均解方面，IATS略差于AMA，但優(yōu)于DBA和PSO；在時間耗費(fèi)方面，IATS略差于DBA，但優(yōu)于AMA和PSO。

4.2.2 實(shí)驗(yàn)2

首先在第一階段用IATS求解R101-R110，C101-C105，RC101-RC105算例，然后將得到的解用SRTD算法、DTD算法[13]和PR算法[15]進(jìn)行修正，結(jié)果如表3所示。將第一階段用IATS對R101-R110，C101-C105，RC101-RC105算例進(jìn)行求解所得的成本分別加上第二階段SRTD算法、DTD算法、PR算法的修正成本，結(jié)果如表4所示。

表3 SRTD修正算法與其他修正算法的對比實(shí)驗(yàn)結(jié)果

續(xù)表3

表4 本文算法與其他算法的對比實(shí)驗(yàn)結(jié)果

由表3可見，在大多數(shù)算例中，SRTD算法的修正成本均明顯低于其他算法，因此在第二階段采用SRTD修正算法是有效且可行的。由表4可見，本文算法(IATS+SRTD)在大多數(shù)案例下均優(yōu)于其他算法。因此，本文所提兩階段算法是有效且可行的。

5 結(jié)束語

本文對VRPSD-STW進(jìn)行研究，提出一種兩階段算法。算法在第一階段采用IATS，第二階段采用SRTD算法。以Solomon的6種類型VRPTW算例為基礎(chǔ)構(gòu)造算例對算法進(jìn)行測試,并將求解結(jié)果與相關(guān)文獻(xiàn)的結(jié)果進(jìn)行比較,結(jié)果表明IATS具有較強(qiáng)的尋優(yōu)能力和較高的魯棒性，SRTD算法較DTD算法、PR算法的效果更優(yōu)；在測試C1，C2類算例時，因?yàn)榭蛻艏悍植?，隨機(jī)性較弱，所以IATS的尋優(yōu)能力具有一定的局限性。由此可知，本文所提算法能夠有效解決VRPSD-STW。

目前，針對VRPSD-STW的研究仍有進(jìn)一步改進(jìn)的空間，例如在模型中添加多配送中心約束或多時間窗約束。另外，為了更加符合實(shí)際情況，還可引入隨機(jī)行駛時間和隨機(jī)服務(wù)時間進(jìn)行進(jìn)一步研究。