行駛時(shí)間隨機(jī)的分批配送車(chē)輛路徑問(wèn)題模型與算法

石建力，張　錦

(1.西南交通大學(xué) 交通運(yùn)輸與物流學(xué)院，成都 610031；　2.西南交通大學(xué) 綜合交通運(yùn)輸智能化國(guó)家地方聯(lián)合工程實(shí)驗(yàn)室，成都 610031)(*通信作者電子郵箱shjl20043528@163.com)

0　引言

隨著顧客期望值增高以及眾多以顧客為導(dǎo)向的商業(yè)模式的出現(xiàn)[1]，在城市配送中考慮配送時(shí)間、配送效率越來(lái)越引起研究者關(guān)注。帶時(shí)間窗的車(chē)輛路徑問(wèn)題(Vehicle Routing Problem， VRP)、以配送時(shí)間為目標(biāo)的VRP以及以綜合費(fèi)用(包括時(shí)間費(fèi)用等)為目標(biāo)的VRP等研究越來(lái)越得到重視。在實(shí)際的配送過(guò)程中，紅綠燈的變換、城市道路限行等常規(guī)因素，以及道路擁堵、道路維修、車(chē)輛損壞等意外因素都會(huì)引起行駛時(shí)間的不確定[2]。此時(shí)的情形與確定情形不同，需要對(duì)配送路徑進(jìn)行合理規(guī)劃和優(yōu)化，以提高配送效率，降低配送費(fèi)用。本文將行駛時(shí)間隨機(jī)引入分批配送車(chē)輛路徑問(wèn)題(Split Delivery Vehicle Routing Problem， SDVRP)進(jìn)行研究，建立行駛時(shí)間隨機(jī)的帶軟時(shí)間窗的分批配送車(chē)輛路徑問(wèn)題(Split Delivery Vehicle Routing Problem with Time Window and Stochastic Travel Time，SDVRPTWSTT)帶修正的隨機(jī)規(guī)劃模型，并根據(jù)問(wèn)題特點(diǎn)設(shè)計(jì)改進(jìn)的粒子群優(yōu)化(Particle Swarm Optimization， PSO)算法進(jìn)行求解。

SDVRP由Dror等[3]于1989年正式提出，是經(jīng)典車(chē)輛路徑問(wèn)題的一類變型，在報(bào)紙配送、食品配送、零售物品配送、應(yīng)急物資車(chē)輛路徑問(wèn)題等實(shí)際運(yùn)作中廣泛應(yīng)用[4]。特別地，F(xiàn)rizzell等[5]首次對(duì)帶時(shí)間窗的分配配送車(chē)輛路徑問(wèn)題(Split Delivery Vehicle Routing Problem with Time Windows，SDVRPTW)進(jìn)行研究，提出使用局部搜索算法求解，并使用重定位和交換兩個(gè)局部搜索算法優(yōu)化構(gòu)造的解；Ho等[6]提出使用禁忌搜索算法求解SDVRPTW，并且不對(duì)需求點(diǎn)分割加任何限制；Belfiore等[7]將巴西一個(gè)零售組織配送問(wèn)題抽象為混合車(chē)輛的SDVRPTW，并使用分散搜索算法求解；McNabb等[8]將局部搜索算子使用到最小-最大蟻群系統(tǒng)中，對(duì)各個(gè)局部搜索算子的效率進(jìn)行測(cè)試和對(duì)比研究。精確求解算法上，Salani等[9]分別使用分支定價(jià)法求解SDVRPTW；Desaulniers[10]使用一類新的分支定價(jià)切割法(branch-and-price-and cut)求解SDVRPTW，并得到較好結(jié)果；Archetti等[11]將禁忌搜索算法嵌入到分支定價(jià)切割法求解SDVRPTW。

以往的SDVRPTW基本都是研究確定性問(wèn)題，行駛時(shí)間是確定的，隨機(jī)分批配送車(chē)輛路徑問(wèn)題的研究成果較少。Bouzaiene-Ayari等[12]、Lei等[13]分別對(duì)需求隨機(jī)的SDVRP進(jìn)行研究，但目前尚無(wú)對(duì)SDVRPTWSTT的研究成果。

對(duì)行駛時(shí)間隨機(jī)的車(chē)輛路徑問(wèn)題(Vehicle Routing Problem with Stochastic Travel Time，VRPSTT)有較多研究[14]。楊信豐等[15]研究帶時(shí)間窗的VRPSTT，建立機(jī)會(huì)約束規(guī)劃模型，并設(shè)計(jì)遺傳算法進(jìn)行求解。李鋒等[16]建立VRPSTT的多目標(biāo)模型，并設(shè)計(jì)混合遺傳算法進(jìn)行求解。王征等[17]建立帶時(shí)間窗的VRPSTT多目標(biāo)模型，并設(shè)計(jì)高效的啟發(fā)式算法進(jìn)行求解。李妍峰等[18]結(jié)合交通流量特征研究行駛時(shí)間隨機(jī)的VRP，并設(shè)計(jì)新的路徑更新策略進(jìn)行求解。Ando等[19]對(duì)帶軟時(shí)間窗的VRPSTT進(jìn)行研究，文中行駛時(shí)間分布函數(shù)由實(shí)際交通數(shù)據(jù)估計(jì)而來(lái)。Russell等[20]構(gòu)建了帶時(shí)間窗的VRPSTT多目標(biāo)模型，分別以車(chē)輛數(shù)、總行駛距離和懲罰費(fèi)用為約束設(shè)計(jì)禁忌搜索算法進(jìn)行求解，并使用愛(ài)爾朗分布作為行駛時(shí)間的分布。Li等[2,21]研究軟時(shí)間窗和硬時(shí)間窗的VRPSTT，并考慮了服務(wù)時(shí)間不確定的因素。對(duì)軟時(shí)間窗情形，作者建立兩階段帶修正的隨機(jī)規(guī)劃模型，目標(biāo)為在第一階段構(gòu)建路徑集、在第二階段最小化期望費(fèi)用對(duì)路徑進(jìn)行調(diào)整。為此，該文中設(shè)計(jì)禁忌搜索算法進(jìn)行求解，假設(shè)行駛時(shí)間和服務(wù)時(shí)間都服從正態(tài)分布，并利用隨機(jī)模擬求得期望。對(duì)硬時(shí)間窗情形，作者建立機(jī)會(huì)約束模型進(jìn)行求解以保證車(chē)輛到達(dá)需求點(diǎn)時(shí)間窗的概率不小于某預(yù)設(shè)值，期望最早和最晚懲罰費(fèi)用不包括在目標(biāo)函數(shù)中。Zhang等[14]對(duì)帶時(shí)間窗的VRPSTT進(jìn)行研究，建立了以費(fèi)用最小和按時(shí)到達(dá)概率最大的多目標(biāo)模型。通過(guò)模型中顧客服務(wù)水平的約束可顯式計(jì)算出每個(gè)顧客點(diǎn)準(zhǔn)時(shí)送達(dá)的概率，而通過(guò)調(diào)整顧客服務(wù)水平約束值可方便研究費(fèi)用與服務(wù)水平的對(duì)比。該文中設(shè)計(jì)了迭代禁忌搜索算法進(jìn)行求解。Ta等[22-23]研究了軟時(shí)間窗的VRPSTT，建立帶修正的隨機(jī)規(guī)劃模型，同時(shí)考慮配送總費(fèi)用(總行駛路徑、車(chē)輛數(shù)以及期望超時(shí)費(fèi)用)和服務(wù)費(fèi)用(提前到達(dá)或遲到)，其中配送費(fèi)用為實(shí)際費(fèi)用，而服務(wù)費(fèi)用為服務(wù)水平的代表。該文作者分別構(gòu)建禁忌搜索算法和列生成、分支定價(jià)法進(jìn)行求解。Ehmke等[24]針對(duì)帶時(shí)間窗的VRPSTT建立以違背每個(gè)時(shí)間窗約束的概率為約束的機(jī)會(huì)約束模型，并以配送費(fèi)用為目標(biāo)函數(shù)。該文中提供了一種為所有需求點(diǎn)計(jì)算服務(wù)水平的方法，并計(jì)算每個(gè)需求點(diǎn)的開(kāi)始服務(wù)時(shí)間及到達(dá)時(shí)間的分布。

多數(shù)求解VRPSTT的問(wèn)題都要考慮時(shí)間窗，但很少在軟時(shí)間窗下考慮等待時(shí)間問(wèn)題。在現(xiàn)實(shí)配送過(guò)程中，很多時(shí)候即使客戶時(shí)間窗為軟時(shí)間窗，由于配送時(shí)間問(wèn)題、文書(shū)問(wèn)題等都將導(dǎo)致等待的情況發(fā)生，因此本文考慮軟時(shí)間窗下等待的情況，此時(shí)比硬時(shí)間窗下更為復(fù)雜，因?yàn)榈却S時(shí)都可能發(fā)生，而硬時(shí)間窗下只需考慮時(shí)間窗之前的等待時(shí)間。

求解VRPSTT使用最多的方法為現(xiàn)代進(jìn)化算法，最常用的為禁忌搜索算法，目前尚無(wú)使用PSO算法求解SDVRPTWSTT的成果。PSO算法被應(yīng)用于解決多類離散優(yōu)化問(wèn)題(包括帶時(shí)間窗的VRPSTT)并取得了比較好的結(jié)果，與其他啟發(fā)式算法相比，它具有信息交換充分、收斂快等優(yōu)點(diǎn)[25-26]。在不允許分批配送的車(chē)輛路徑問(wèn)題[27-29]中，一般使用整數(shù)編碼，即所有需求點(diǎn)序號(hào)的一個(gè)排列，所有粒子位置向量、速度向量長(zhǎng)度均一致。本文考慮使用改進(jìn)的PSO算法求解SDVRPTWSTT，與求解不允許分批配送的車(chē)輛路徑問(wèn)題的不同之處有兩點(diǎn)：1)由于允許分批配送的原因，粒子編碼中存在重復(fù)的需求點(diǎn)，其編碼和解碼過(guò)程均與不允許分批配送時(shí)不同。2)粒子位置向量更新過(guò)程中涉及到的位置向量、速度向量等長(zhǎng)度有可能不統(tǒng)一，計(jì)算過(guò)程中將導(dǎo)致信息丟失或增加隨機(jī)信息，影響算法效率和效果；其次，使用PSO算法求解車(chē)輛路徑問(wèn)題過(guò)程中，粒子位置向量需要在連續(xù)空間及離散空間之間進(jìn)行轉(zhuǎn)換，容易丟失信息，降低算法效率。這些均是本文需要解決的問(wèn)題。

1　問(wèn)題描述及模型建立

問(wèn)題定義在無(wú)向圖G=(V,A)上，其中：V={0,1,…,n}為節(jié)點(diǎn)集合，0代表車(chē)場(chǎng)；C={1,2,…,n}表示n個(gè)不同的需求點(diǎn)；A={(i,j):i,j∈V,i≠j}為邊集合。

需求點(diǎn)i的需求量為di(di>0)為整數(shù)；第k輛車(chē)對(duì)需求點(diǎn)i的服務(wù)時(shí)間為sik(sik≥0)是隨機(jī)變量，本文假設(shè)所有需求點(diǎn)的服務(wù)時(shí)間均服從正態(tài)分布，即sik～N(μik1,σik1)。所有節(jié)點(diǎn)均帶有時(shí)間窗[ei,li]，其中：ei,li分別代表對(duì)需求點(diǎn)i開(kāi)始服務(wù)的最早時(shí)刻和結(jié)束服務(wù)的最晚時(shí)刻；[e0,l0]代表車(chē)輛離開(kāi)車(chē)場(chǎng)的最早時(shí)刻和返回車(chē)場(chǎng)的最晚時(shí)刻。時(shí)間窗為軟時(shí)間窗，允許車(chē)輛在時(shí)間窗外開(kāi)始服務(wù)，但在時(shí)間窗外開(kāi)始服務(wù)需要產(chǎn)生額外懲罰費(fèi)用。

本文將等待時(shí)間引入軟時(shí)間窗VRP中，第k輛車(chē)在需求點(diǎn)i的等待時(shí)間記為wik，也是隨機(jī)變量，為簡(jiǎn)化問(wèn)題，假設(shè)等待時(shí)間也服從正態(tài)分布，即wik～N(μik2,σik2)。在實(shí)際生活中，時(shí)間窗內(nèi)外都有可能產(chǎn)生等待，有時(shí)甚至?xí)l(fā)生長(zhǎng)時(shí)間等待的情況，如在給大超市進(jìn)行配送時(shí)，零售商處于主導(dǎo)地位，配送企業(yè)可能需要等待較長(zhǎng)時(shí)間，即使提前預(yù)約，有時(shí)也會(huì)需要等待1～2個(gè)小時(shí)。為簡(jiǎn)化問(wèn)題，本文暫不對(duì)此種情況作考慮。等待將對(duì)配送過(guò)程及司機(jī)勞動(dòng)強(qiáng)度產(chǎn)生影響，將此類影響統(tǒng)稱為等待費(fèi)用，其大小簡(jiǎn)化為與等待時(shí)間線性相關(guān)。

每條邊具有對(duì)稱的行駛距離cij和行駛時(shí)間tij，行駛距離滿足三角不等式；每條邊上的行駛時(shí)間tij為隨機(jī)變量，假設(shè)所有邊的行駛時(shí)間均服從正態(tài)分布，即tij～N(μij,σij)。

車(chē)輛集合為K={1,2,…,m}，所有車(chē)容量均相同，為Q。假設(shè)車(chē)輛數(shù)量無(wú)限，根據(jù)實(shí)際調(diào)研，即使某些時(shí)候配送企業(yè)車(chē)輛數(shù)不夠用，但均有相應(yīng)的應(yīng)急處理方式，比如與其他配送企業(yè)簽訂戰(zhàn)略協(xié)議，可隨時(shí)借調(diào)車(chē)輛。某些需求點(diǎn)可能由多輛車(chē)服務(wù)。

符號(hào)說(shuō)明見(jiàn)表1。

表1　變量符號(hào)說(shuō)明Tab. 1　Variable symbol description

決策變量包括xijk和yik,其中xijk如下所示：

yik則為需求點(diǎn)i由車(chē)輛k進(jìn)行配送的量。

目標(biāo)函數(shù)為最小化綜合費(fèi)用。

隨機(jī)規(guī)劃模型如下：

(1)

(2)

(3)

(4)

(5)

(6)

yik∈N;i=1,2,…,n,k=1,2,…,m

(7)

xijk∈{0,1};i=0,1,…,n,j=0,1,…,n,k=1,2,…,m

(8)

目標(biāo)函數(shù)中期望延遲時(shí)間、期望提前時(shí)間和期望等待時(shí)間都是隨機(jī)的，本文通過(guò)將這三個(gè)期望量通過(guò)推導(dǎo)表示為行駛時(shí)間、服務(wù)時(shí)間和等待時(shí)間期望與方差的解析表達(dá)式，以提高計(jì)算過(guò)程中目標(biāo)函數(shù)計(jì)算效率。

1.1　服務(wù)時(shí)間性質(zhì)

1.2　到達(dá)時(shí)刻和開(kāi)始服務(wù)時(shí)刻性質(zhì)

令Tij表示車(chē)輛經(jīng)過(guò)弧(i,j)從需求點(diǎn)i到需求點(diǎn)j所需時(shí)間，則車(chē)輛k到達(dá)需求點(diǎn)j的時(shí)間ajk為直到需求點(diǎn)j所有邊的行駛時(shí)間、需求點(diǎn)j之前的所有需求點(diǎn)的等待時(shí)間和服務(wù)時(shí)間之和，即：

其中：Ajk表示車(chē)輛k經(jīng)過(guò)的直到需求點(diǎn)的j所有邊；Cjk表示車(chē)輛k上需求點(diǎn)j之前的所有需求點(diǎn)；yik為車(chē)輛k對(duì)Cjk中需求點(diǎn)的配送比例。

根據(jù)正態(tài)分布的可加性，到達(dá)時(shí)間ajk也服從正態(tài)分布，其均值和方差分別為：

由于本文中假定車(chē)輛到達(dá)需求點(diǎn)不一定直接開(kāi)始服務(wù)，因此，車(chē)輛開(kāi)始服務(wù)的時(shí)間為ssjk=ajk+wjk，由正態(tài)分布的性質(zhì)得，開(kāi)始服務(wù)時(shí)間也服從正態(tài)分布，其均值與方差分別為：

1.3　目標(biāo)函數(shù)計(jì)算

本文中假定行駛時(shí)間、服務(wù)時(shí)間、等待時(shí)間均服從正態(tài)分布，它們的概率密度函數(shù)和分布函數(shù)分別由下述兩式給出：

其中：t≥0，δ≥0。

期望延遲時(shí)間可以根據(jù)以下過(guò)程計(jì)算得到：

所以：

同樣的道理，期望提前時(shí)間也可計(jì)算出來(lái)：

2　改進(jìn)的粒子群優(yōu)化算法

2.1　問(wèn)題描述

本文結(jié)合問(wèn)題特點(diǎn)，將自適應(yīng)選擇和路徑重連融入PSO算法進(jìn)行求解：路徑重連用于粒子位置更新，自適應(yīng)選擇用于速度更新。

在PSO算法初始階段，一簇粒子隨機(jī)產(chǎn)生，每個(gè)粒子對(duì)應(yīng)一個(gè)解，在解空間中有一個(gè)固定的位置。在迭代過(guò)程中，每個(gè)粒子對(duì)應(yīng)一個(gè)速度向量，并根據(jù)速度向量移動(dòng)。設(shè)計(jì)成功PSO的關(guān)鍵是在位置向量和解之間尋找合適的映射。由于分批配送車(chē)輛路徑問(wèn)題中存在被分割的需求點(diǎn)，針對(duì)VRP的路徑分割算法已不再適用，本文使用Boudia等[30]提出的改進(jìn)的基于Bellman方程的路徑分割算法分割路徑。

經(jīng)典PSO中粒子移動(dòng)取決于速度向量，粒子位置向量需要在連續(xù)空間和離散空間之間進(jìn)行轉(zhuǎn)換，會(huì)丟失信息，降低隨機(jī)路徑問(wèn)題的求解效率，影響解質(zhì)量。本文使用路徑重連策略進(jìn)行位置更新以避免PSO算法中位置向量在離散空間與連續(xù)空間之間轉(zhuǎn)換，提高求解效率。速度更新方程的角色有所轉(zhuǎn)變，用于衡量粒子在路徑重連過(guò)程中向自身最優(yōu)、局部最優(yōu)、全局最優(yōu)進(jìn)化的重要參數(shù)。粒子速度不再是粒子位置更新的主導(dǎo)，也減弱分批配送車(chē)輛路徑問(wèn)題中統(tǒng)一粒子位置向量、速度向量、局部最優(yōu)、鄰域最優(yōu)和全局最優(yōu)位置向量等向量非零元素個(gè)數(shù)而導(dǎo)致信息丟失或者增加無(wú)用信息帶來(lái)的影響。

最后，本文使用基于變鄰域搜索(Variable Neighborhood Search， VNS)算法的局部搜索策略對(duì)每個(gè)粒子進(jìn)行優(yōu)化以提高解的質(zhì)量。在每次迭代中，粒子群中最優(yōu)粒子和粒子自身最優(yōu)被保存。本文求解最小化問(wèn)題，目標(biāo)函數(shù)值較大的解將被標(biāo)記為劣解。算法在達(dá)到最大迭代次數(shù)時(shí)結(jié)束。

2.2　初始解生成

初始種群包含np個(gè)初始解，本文使用三種不同的方式生成整個(gè)初始解，其中：節(jié)約算法生成不產(chǎn)生需求點(diǎn)分割的1個(gè)初始解；改進(jìn)掃描算法產(chǎn)生需求點(diǎn)分割的1個(gè)初始解；順序插入算法生成np-2個(gè)允許分割的初始解。

1)節(jié)約算法。

此算法為經(jīng)典的VRP算法，將每個(gè)需求點(diǎn)看作一條路徑，然后通過(guò)連續(xù)的方式將距離最近的兩個(gè)路徑合并，從而得到VRP解。本文以此方式生成1個(gè)初始解，解中無(wú)需求點(diǎn)被分割，意在初始種群中放置較優(yōu)的不產(chǎn)生分割的初始解。

2)改進(jìn)的掃描算法。

掃描算法也是VRP經(jīng)典算法，當(dāng)一條路徑的容量未被耗盡且無(wú)法容下下一個(gè)需要加入的需求點(diǎn)時(shí)，分割此需求點(diǎn)，一部分放入當(dāng)前路徑，剩余一部分放入下一條新路徑。本文以此方式產(chǎn)生一個(gè)初始解，部分需求點(diǎn)被分割。

3)隨機(jī)生成。

此算法隨機(jī)生成一個(gè)需求點(diǎn)的序列，并依次將需求點(diǎn)添加到路徑中，當(dāng)前路徑容量未被耗盡且無(wú)法容下下一個(gè)需求點(diǎn)的需求量時(shí)，將此需求點(diǎn)需求量分割，部分放在當(dāng)前路徑中，剩余部分放入下一條新路徑中。本文以此方式產(chǎn)生np-2個(gè)初始解，這些解中有可能無(wú)需求點(diǎn)被分割，部分解中部分需求點(diǎn)被分割。

2.3　編碼

本文中粒子采用整數(shù)編碼，每個(gè)元素代表一個(gè)需求點(diǎn)，編碼中可存在重復(fù)數(shù)字，表示此需求點(diǎn)需求被分割；每個(gè)粒子包含2*nc個(gè)元素，nc為需求點(diǎn)數(shù)量。由于本文使用路徑重連算法對(duì)粒子位置進(jìn)行更新，只需對(duì)粒子進(jìn)行編碼，不再需要將連續(xù)型編碼轉(zhuǎn)化為整型編碼，只需在每次速度更新時(shí)將整型編碼轉(zhuǎn)換為連續(xù)型編碼即可，轉(zhuǎn)換的方式為每個(gè)元素除以需求點(diǎn)個(gè)數(shù)。

2.4　速度更新

本文使用基于全局、局部鄰域最優(yōu)的速度更新方程，方程中包括四項(xiàng)，因此粒子除了向新方向、自身最優(yōu)、全局最優(yōu)移動(dòng)外，還會(huì)向局部最優(yōu)移動(dòng)，與局部最優(yōu)粒子交換信息。通過(guò)添加第四項(xiàng)，避免解快速向初始全局最優(yōu)解收斂，增加每個(gè)粒子通過(guò)局部最優(yōu)找到全局最優(yōu)的概率。速度更新方程如下：

vij(t+1)=χ1*(vij(t)+c1*rand1*(pbestij-xij(t))+

c2*rand2*(gbestij-xij(t))+

c3*rand3*(lbestij-xij(t)))

在分批配送車(chē)輛路徑問(wèn)題中，速度更新公式中的向量vij(t)、xij(t)、pbestij、gbestij、lbestij，除了vij(t)、xij(t)非零元素個(gè)數(shù)相同，其他向量之間非零元素個(gè)數(shù)均有可能不同，因此在速度更新公式中需要選擇合適的向量長(zhǎng)度進(jìn)行計(jì)算。本文中采用自適應(yīng)方式在粒子位置向量xij(t)、自身最優(yōu)pbestij、全局最優(yōu)gbestij和局部最優(yōu)lbestij之間選取標(biāo)準(zhǔn)向量。

wo,N+1=wo,N(1-χ)+χπoN/εoN

其中:εoN、πoN分別代表向量o在第N階段被選中的次數(shù)和所得的分?jǐn)?shù)；χ∈[0,1]為常數(shù)，文中選取χ=0.1。

向量o在第N階段的得分按下式計(jì)算，其中得到的解為在組合鄰域拓?fù)潆A段得到的解：

2.5　粒子位置更新

文中每個(gè)粒子位置通過(guò)路徑重連進(jìn)行更新，位置更新方程被路徑重連過(guò)程替代，能這樣做的原因?yàn)槁窂街剡B思想與PSO算法中粒子位置更新思想是相似的，也是決定粒子向自身最優(yōu)、向全局最優(yōu)和向局部最優(yōu)等移動(dòng)。

其中:itermax為迭代最大次數(shù)。ubound和lbound分別是每個(gè)粒子速度的上界和下界,一般地，ubound和lbound分別取4和-4。如果在某些迭代中，粒子速度某元素超出上下界，則在上下界中重新產(chǎn)生一個(gè)新的值。參數(shù)w1和w2值應(yīng)比較大，以保證算法初始階段L1盡量大，并隨著迭代的進(jìn)行減??；另外，L2需要比L1大，因此w2應(yīng)大于w1。所以，本文設(shè)置w1=0.8，w2=0.9以保證不同移動(dòng)方向擁有基本相同的概率。由于路徑重連算法將導(dǎo)致解在較少次數(shù)的迭代中收斂到單個(gè)優(yōu)解附近，因此與最優(yōu)解相差10%以內(nèi)的解均不接受[31]，除非能更新最優(yōu)解。

在不允許分批配送的VRP中，一般在路徑重連過(guò)程中使用交換算子進(jìn)行局部搜索，本文中允許分批配送，因此使用Boudia等[30]提出的改進(jìn)的允許分批配送的交換算子進(jìn)行局部搜索。

2.6　粒子鄰域最優(yōu)更新

本文使用擴(kuò)展鄰域拓?fù)溥M(jìn)行粒子局部鄰域最優(yōu)的更新。借鑒Marinakis等[32]將VNS鄰域擴(kuò)展的思想融入到擴(kuò)展鄰域的做法，根據(jù)解的質(zhì)量調(diào)整粒子鄰域，每個(gè)粒子的鄰域根據(jù)自身解優(yōu)化程度的不同而不同。開(kāi)始階段所有粒子鄰域是相同的,當(dāng)某個(gè)粒子對(duì)應(yīng)的解在連續(xù)一定數(shù)量itnum的迭代過(guò)程中都沒(méi)有被優(yōu)化，只有它的鄰域進(jìn)行擴(kuò)展。在此策略下，每個(gè)粒子鄰域范圍不同。當(dāng)鄰域范圍擴(kuò)展到整個(gè)空間時(shí)，局部最優(yōu)鄰域?qū)淖钚∫?guī)模鄰域重新初始化。

2.7　局部搜索算法

為了提高PSO算法解的質(zhì)量，采用基于VNS的局部搜索策略。本文允許分批配送，在單條路徑上執(zhí)行2-opt、重定位、交換等局部搜索算子，在路徑間執(zhí)行分批1-1交換、分批2-1交換、路徑添加、k-分割等算子。首先，選擇局部搜索算法的數(shù)量，為了不增加算法復(fù)雜性，使用Marinakis在文獻(xiàn)[31]中提出的策略，在每次迭代中使用一個(gè)局部搜索組合，因此選取VNS因子CVNS控制使用的局部搜索組合，通過(guò)隨機(jī)數(shù)產(chǎn)生器randi(0,1)產(chǎn)生的隨機(jī)數(shù)與CVNS進(jìn)行比較：如果隨機(jī)數(shù)小于或等于CVNS，則執(zhí)行上述7個(gè)局部搜索算子中的第一個(gè)局部搜索算子；如果隨機(jī)數(shù)小于或等于2*CVNS，則執(zhí)行前兩個(gè)局部搜索算子；以此類推。

2.8　出發(fā)時(shí)間調(diào)整

從PSO算法得到的解都是時(shí)刻0從車(chē)場(chǎng)出發(fā)，本文的后驗(yàn)優(yōu)化算法將每輛車(chē)從車(chē)場(chǎng)出發(fā)的時(shí)間以M分鐘循環(huán)調(diào)整，直到路徑綜合費(fèi)用無(wú)法進(jìn)一步降低為止。

3　算例分析

本文程序使用Matlab (2012b)編寫(xiě)，運(yùn)行平臺(tái)內(nèi)存12 GB，顯卡2.9 GHz，64位操作系統(tǒng)。

算例采用Solomon[33]提出的經(jīng)典算例進(jìn)行測(cè)試，該算例構(gòu)造時(shí)考慮了需求點(diǎn)空間分布和時(shí)間窗的合理性等，被很多學(xué)者選為測(cè)試算例?？紤]Solomon的四類算例：R1、R2、RC1和RC2，且算例規(guī)模為100。R1和RC1類算例時(shí)間窗較短，車(chē)輛只能服務(wù)較少的需求點(diǎn)；R2及RC2類算例具有長(zhǎng)時(shí)間窗，允許車(chē)輛對(duì)更多的需求點(diǎn)進(jìn)行配送。在所有的測(cè)試中，期望行駛時(shí)間等于相應(yīng)的歐幾里得距離。

3.1　算例調(diào)整

本文采用Ho等[6]提出的調(diào)整方式對(duì)實(shí)驗(yàn)算例進(jìn)行調(diào)整。其中：節(jié)點(diǎn)(包括車(chē)場(chǎng)和需求點(diǎn))的位置、車(chē)容量、時(shí)間窗和服務(wù)時(shí)間與Solomon[33]的例子相同。在此基礎(chǔ)上，考慮對(duì)各個(gè)需求點(diǎn)的平均需求進(jìn)行調(diào)整，將平均需求調(diào)整到區(qū)間[vQ,uQ]，其中，v和u均為(0，1]區(qū)間的數(shù)，且v

(9)

Silva等[34]考慮不同的組合值：[0.01，0.1]，[0.1，0.3]，[0.1，0.5]，[0.1，0.9]，[0.3，0.7]，[0.7，0.9]，并證實(shí)平均需求量較大的算例分割現(xiàn)象較明顯。綜合現(xiàn)有結(jié)果，本文考慮[v,u]取值為[0.1，0.9]和[0.3，0.7]的情況，所有調(diào)整的需求均取整。

3.2　算法參數(shù)

本文算法在Marinakis[31]算法的基礎(chǔ)上進(jìn)行設(shè)計(jì)，故算法參數(shù)參考Marinakis[31]中的參數(shù)取值如表2所示。

3.3　結(jié)果分析

在每個(gè)算例上分別針對(duì)[0.1,0.9]和[0.3,0.7]運(yùn)行10次，選取兩種情況下的最優(yōu)解，然后使用這兩個(gè)最優(yōu)解的平均值進(jìn)行分析。由于尚未發(fā)現(xiàn)可直接與本文結(jié)果進(jìn)行比較的成果，本文考慮否允許等待和是否允許分批配送兩種角度對(duì)結(jié)果進(jìn)行分析。

表2　實(shí)驗(yàn)中算法的參數(shù)選取Tab. 2　Experimental parameters selection of the algorithm

3.3.1是否允許等待的情況比較

不允許等待的情況同一般情況下的軟時(shí)間窗問(wèn)題相同，不考慮等待時(shí)間，只考慮提前服務(wù)和延遲服務(wù)的懲罰費(fèi)用。

1)總費(fèi)用。是否允許等待兩種情況下的總費(fèi)用對(duì)比如圖1所示。

圖1　總費(fèi)用在是否允許等待情況下的比較Fig. 1　Comparison of all-in cost for allowing waiting or not

從圖1可以看出，四類算例中絕大部分算例允許等待時(shí)總費(fèi)用高于不允許等待時(shí)的總費(fèi)用，平均高出3%左右。從計(jì)算結(jié)果看，產(chǎn)生此類現(xiàn)象的原因主要是由于考慮等待時(shí)間造成車(chē)輛服務(wù)時(shí)間延長(zhǎng)，從而導(dǎo)致平均使用車(chē)輛數(shù)增加,具體如圖2所示。從圖2可以看出，超過(guò)70%以上的算例使用車(chē)輛數(shù)在考慮等待的情況下高于不考慮等待的情況，由于考慮等待而導(dǎo)致的車(chē)輛數(shù)平均增加0.62。但是，等待在實(shí)際配送過(guò)程中是普遍存在的，因此在實(shí)際配送運(yùn)營(yíng)中應(yīng)盡量減少等待時(shí)間，以提升配送人員效率，提升服務(wù)效率。

2)行駛費(fèi)用和懲罰費(fèi)用。行駛費(fèi)用是指不與時(shí)間相關(guān)的費(fèi)用，包括車(chē)輛使用費(fèi)用和車(chē)輛行駛距離產(chǎn)生的費(fèi)用；懲罰費(fèi)用是指與時(shí)間相關(guān)的費(fèi)用，包括提前服務(wù)和延遲服務(wù)產(chǎn)生的懲罰費(fèi)用。

如圖3、圖4所示，考慮等待時(shí)間造成行駛費(fèi)用占總費(fèi)用的比例比不考慮等待時(shí)間時(shí)比例略微降低，平均降低約0.6%，主要由于行駛費(fèi)用變化不大(平均增加約68.30)，其增加的幅度低于總費(fèi)用增加的幅度；同時(shí)懲罰費(fèi)用占總費(fèi)用的比例降低明顯，平均降低約9.65%，絕對(duì)值上平均約降低467。從此現(xiàn)象可以看出，等待時(shí)間對(duì)懲罰費(fèi)用影響較大，同時(shí)等待時(shí)間產(chǎn)生的費(fèi)用部分由懲罰費(fèi)用轉(zhuǎn)化而來(lái)。

圖2　車(chē)輛數(shù)在是否允許等待情況下的比較Fig. 2　Comparison of number of vehicles for allowing waiting or not

圖3　行駛費(fèi)用占總費(fèi)用的比在是否允許等待情況下的比較Fig. 3　Comparison of ratio of travel cost in all-in cost for allowing waiting or not

圖4　懲罰費(fèi)用占總費(fèi)用的比在是否允許等待情況下的比較Fig. 4　Comparison of ratio of penalty cost in all-in cost for allowing waiting or not

3)考慮等待時(shí)間時(shí)更傾向于分批配送。如圖5所示，從最優(yōu)解中最終配送點(diǎn)數(shù)量來(lái)看，80%以上的算例考慮等待時(shí)間時(shí)多于不考慮等待時(shí)間的情況，平均多約2.8個(gè)；考慮等待時(shí)間更傾向于分批配送。

3.3.2是否允許分批的情況比較

1)總費(fèi)用對(duì)比。如圖6所示，總體來(lái)看，允許分批配送時(shí)比不允許分批配送時(shí)總費(fèi)用有所降低。所有測(cè)試算例中，約61.5%的算例總費(fèi)用低于不允許分批配送，所有算例總費(fèi)用平均降低約2%。

圖5　配送點(diǎn)數(shù)量在是否允許等待情況下的比較Fig. 5　Comparison of number of delivery customers for allowing waiting or not

圖6　總費(fèi)用在是否允許分批配送情況下的對(duì)比Fig. 6　Comparison of all-in cost for allowing split or not

2)車(chē)輛數(shù)對(duì)比。如圖7所示，總體來(lái)看，是否允許分批配送對(duì)最優(yōu)解中車(chē)輛數(shù)的影響不具有一般規(guī)律，特別在R1、R2類算例中。在RC1類算例中，不允許分批配送時(shí)車(chē)輛數(shù)總體少于允許分批配送；而在RC2類算例中，不允許分批配送時(shí)車(chē)輛數(shù)則多于允許分批配送，此時(shí)分批配送將為最優(yōu)解帶來(lái)更顯著的節(jié)約。將所有算例數(shù)據(jù)匯總來(lái)看，允許分批配送時(shí)使用的車(chē)輛數(shù)比不允許分批配送時(shí)使用的車(chē)輛數(shù)平均少約0.6。

3)配送點(diǎn)數(shù)。如表3所示，四類算例平均配送點(diǎn)數(shù)達(dá)105.9，分割點(diǎn)比例達(dá)到5.9%，測(cè)算過(guò)程中，80%以上的算例最優(yōu)解中均產(chǎn)生分批配送的需求點(diǎn)，允許分批在較大規(guī)模算例中能起到較好作用。

4)計(jì)算時(shí)間對(duì)比。如圖8所示，總體來(lái)看，是否允許分批配送對(duì)計(jì)算時(shí)間的影響不具有一般規(guī)律。所有算例允許分批配送比不允許分批配送時(shí)的平均計(jì)算時(shí)間多約300 s。

圖7　車(chē)輛數(shù)在是否允許分批配送情況下的對(duì)比Fig. 7　Comparison of number of vehicles for allowing split or not

表3　四類算例平均配送點(diǎn)數(shù)Tab. 3　Average number of delivery customers for four types of instances

圖8　平均計(jì)算時(shí)間在是否允許分批配送情況下的對(duì)比Fig. 8　Comparison of average computing time for allowing split or not

5)等待費(fèi)用占總費(fèi)用的比例。如圖9所示,總體來(lái)看，是否允許分批配送對(duì)等待費(fèi)用占總費(fèi)用的比例影響較小。所有算例允許分批配送比不允許分批配送的占比約降低0.78%，允許分批配送在部分算例中能有效降低車(chē)輛等待時(shí)間，特別在R2類算例中表現(xiàn)比較明顯。

圖9　等待費(fèi)用占總費(fèi)用的比例在是否允許分批配送情況下的對(duì)比Fig. 9　Comparison of ratio of waiting cost in all-in cost for allowing split or not

4　結(jié)語(yǔ)

本文在軟時(shí)間窗下考慮等待時(shí)間，建立帶修正的隨機(jī)規(guī)劃模型，并設(shè)計(jì)改進(jìn)的PSO算法進(jìn)行求解。算法結(jié)合三類不同的拓?fù)?，使用路徑重連算法有效解決了粒子位置向量在連續(xù)空間和離散空間轉(zhuǎn)換造成的信息丟失問(wèn)題，并采用自適應(yīng)選擇解決了分批配送引起的向量長(zhǎng)度不一致問(wèn)題。

通過(guò)對(duì)調(diào)整的Solomon算例進(jìn)行測(cè)試，算法能有效求解本文提出的問(wèn)題?？紤]等待時(shí)間將造成總費(fèi)用平均增加約3%，使用的車(chē)輛數(shù)平均增加0.62。懲罰費(fèi)用占總費(fèi)用的比例平均降低約9.65%，考慮等待時(shí)間對(duì)懲罰費(fèi)用影響較大，等待時(shí)間產(chǎn)生的費(fèi)用部分由懲罰費(fèi)用轉(zhuǎn)化而來(lái)。同時(shí)考慮等待時(shí)間的情況也更傾向于分批配送，最終配送點(diǎn)數(shù)平均多約2.8。

分批配送能有效降低總費(fèi)用和使用車(chē)輛數(shù)，分別平均降低約2%和0.6輛;而且允許分批配送在部分算例中能有效降低車(chē)輛等待時(shí)間，特別是在R2類算例中表現(xiàn)比較明顯，所有等待時(shí)間平均約降低0.78%。

進(jìn)一步的研究集中在兩個(gè)方面:1)設(shè)計(jì)更高效的基于種群的進(jìn)化算法求解隨機(jī)分批配送問(wèn)題，比如螢火蟲(chóng)群算法等；設(shè)計(jì)動(dòng)態(tài)求解或精確求解算法解決行駛時(shí)間隨機(jī)車(chē)輛路徑問(wèn)題等。2)尋求合理的方法對(duì)等待時(shí)間分布進(jìn)行研究，更深入、精確地分析等待時(shí)間在配送中的影響；將城市交通流量、交通信號(hào)控制等與車(chē)輛路徑問(wèn)題相結(jié)合，考慮更接近現(xiàn)實(shí)情況、更復(fù)雜的動(dòng)態(tài)車(chē)輛路徑問(wèn)題。

參考文獻(xiàn):

[1]EHMKE J F, CAMPBELL A M, URBAN T L. Ensuring service levels in routing problems with time windows and stochastic travel times [J]. European Journal of Operational Research, 2015, 240(2): 539-550.

[2]LI X, TIAN P, LEUNG S C H. Vehicle routing problems with time windows and stochastic travel and service times: models and algorithm [J]. International Journal of Production Economics, 2010, 125(1): 137-145.

[3]DROR M, TRUDEAU P. Savings by split delivery routing [J]. Transportation Science, 1989, 23(2): 141-145.

[4]ARCHETTI C, SPERANZA M G. Vehicle routing problems with split deliveries [J]. International Transactions in Operational Research, 2012, 19(1/2): 3-22.

[5]FRIZZELL P W, GIFFIN J W. The split delivery vehicle scheduling problem with time windows and grid network distances [J]. Computers & Operations Research, 1995, 22(6): 655-667.

[6]HO S C, HAUGLAND D. A Tabu search heuristic for the vehicle routing problem with time windows and split deliveries [J]. Computers & Operations Research, 2004, 31(12): 1947-1964.

[7]BELFIORE P, YOSHIDA YOSHIZAKI H T. Scatter search for a real-life heterogeneous fleet vehicle routing problem with time windows and split deliveries in Brazil [J]. European Journal of Operational Research, 2009, 199(3): 750-758.

[8]MCNABB M E. Exploring heuristics for the vehicle routing problem with split deliveries and time windows [D]. Ohio: Air University, Department of the Air Force, Wright-Patterson Air Force Base, 2014: 29-63.

[9]SALANI M, VACCA I. Branch and price for the vehicle routing problem with discrete split deliveries and time windows [J]. European Journal of Operational Research, 2011, 213(3): 470-477.

[10]DESAULNIERS G. Branch-and-price-and-cut for the split-delivery vehicle routing problem with time windows [J]. Operations Research, 2010,58(1): 179-192.

[11]ARCHETTI C, BOUCHARD M, DESAULNIERS G. Enhanced branch and price and cut for vehicle routing with split deliveries and time windows [J]. Transportation Science, 2011, 45(3): 285-298.

[12]BOUZAIENE-AYARI B, DROR M, LAPORTE G. Vehicle routing with stochastic demand and split deliveries [J]. Discrete Applied Mathematics, 1994, 50(3): 239-254.

[13]LEI H, LAPORTE G, GUO B. The vehicle routing problem with stochastic demands and split deliveries [J]. INFOR: Information Systems & Operational Research, 2012, 50(2): 59-71.

[14]ZHANG J, LAM W H K, CHEN B Y. A stochastic vehicle routing problem with travel time uncertainty: trade-off between cost and customer service [J]. Networks and Spatial Economics, 2013, 13(4): 471-496.

[15]楊信豐,楊慶豐.隨機(jī)車(chē)輛路徑問(wèn)題的模型及其算法[J].交通運(yùn)輸系統(tǒng)工程與信息,2006,6(4):75-80. (YANG X F, YANG Q F. Model and algorithm of vehicle routing problem with stochastic travel time [J]. Journal of Transponation systems Engineering and Information Technology, 2006, 6(4): 75-80.)

[16]李鋒,魏瑩.求解隨機(jī)旅行時(shí)間的C-VRP問(wèn)題的混合遺傳算法[J].系統(tǒng)管理學(xué)報(bào),2014,23(6):819-825. (LI F, WEI Y. Hybrid genetic algorithm for capacitated vehicle routing problem with stochastic travel time [J]. Journal of Systems & Management, 2014, 23(6): 819-825.)

[17]王征,胡祥培,王旭坪.行駛時(shí)間延遲下配送車(chē)輛調(diào)度的干擾管理模型與算法[J].系統(tǒng)工程理論與實(shí)踐,2013,33(2):378-387. (WANG Z, HU X P, WANG X P. Disruption management model and algorithm for distribution vehicle scheduling problems under accidental travel time delay [J]. Systems Engineering — Theory & Practice, 2013, 33(2): 378-387.)

[18]李妍峰,高自友,李軍.基于實(shí)時(shí)交通信息的城市動(dòng)態(tài)網(wǎng)絡(luò)車(chē)輛路徑優(yōu)化問(wèn)題[J].系統(tǒng)工程理論與實(shí)踐,2013,33(7):1813-1819. (LI Y F, GAO Z Y, LI J. Vehicle routing problem in dynamic urban network with real-time traffic information[J]. Systems Engineering — Theory & Practice, 2013, 33(7): 1813-1819.)

[19]ANDO N, TANIGUCHI E. Travel time reliability in vehicle routing and scheduling with time windows [J]. Networks and Spatial Economics, 2006, 6(3/4): 293-311.

[20]RUSSELL R A, URBAN T L. Vehicle routing with soft time windows and erlang travel times [J]. The Journal of the Operational Research Society, 2008, 59(9): 1220-1228.

[21]李相勇,田澎.帶時(shí)間窗和隨機(jī)時(shí)間車(chē)輛路徑問(wèn)題:模型和算法[J].系統(tǒng)工程理論與實(shí)踐,2009,29(8):81-90. (LI X Y, TIAN P. Vehicle routing problems with time windows and stochastic times: models & algorithm [J]. Systems Engineering — Theory & Practice, 2009, 29(8): 81-90.)

[24]EHMKE J F, CAMPBELL A M, URBAN T L. Ensuring service levels in routing problems with time windows and stochastic travel times [J]. European Journal of Operational Research, 2015, 240(2): 539-550.

[25]MARINAKIS Y, MARINAKI M, DOUNIAS G. A hybrid particle swarm optimization algorithm for the vehicle routing problem [J]. Engineering Applications of Artificial Intelligence, 2010, 23(4): 463-472.

[26]KECHAGIOPOULOS P N, BELIGIANNIS G N. Solving the urban transit routing problem using a particle swarm optimization based algorithm [J]. Applied Soft Computing, 2014, 21: 654-676.

[27]AI T J, KACHITVICHYANUKUL V. Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem [J]. Computers & Industrial Engineering, 2009, 56(1): 380-387.

[28]CHEN M-C, HSIAO Y-H, HIMADEEP REDDY R, et al. The self-learning particle swarm optimization approach for routing pickup and delivery of multiple products with material handling in multiple cross-docks [J]. Transportation Research Part E: Logistics and Transportation Review, 2016, 91: 208-226.

[29]NOROUZI N, SADEGH-AMALNICK M, ALINAGHIYAN M. Evaluating of the particle swarm optimization in a periodic vehicle routing problem [J]. Measurement, 2015, 62: 162-169.

[30]BOUDIA M, PRINS C, REGHIOUI M. An effective memetic algorithm with population management for the split delivery vehicle routing problem [C]// HM’07: Proceedings of the 4th International Conference on Hybrid Metaheuristics, LNCS 4771. Berlin: Springer, 2007: 16-30.

[31]MARINAKIS Y. An improved particle swarm optimization algorithm for the capacitated location routing problem and for the location routing problem with stochastic demands [J]. Applied Soft Computing, 2015, 37: 680-701.

[32]MARINAKIS Y, MARINAKI M. Combinatorial expanding neighborhood topology particle swarm optimization for the vehicle routing problem with stochastic demands [C]// GECCO ’13: Proceedings of the 2013 Conference on Genetic and Evolutionary Computation. New York: ACM, 2013: 49-56.

[33]SOLOMON M M. Algorithms for the vehicle routing and scheduling problems with time window constraint [J]. Operations Research, 1987, 35(2): 254-265.

[34]SILVA M M, SUBRAMANIAN A, OCHI L S. An iterated local search heuristic for the split delivery vehicle routing problem [J]. Computers & Operations Research, 2015, 53: 234-249.