行駛時間隨機的分批配送車輛路徑問題模型與算法

石建力，張　錦

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

0　引言

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

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

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

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

多數求解VRPSTT的問題都要考慮時間窗，但很少在軟時間窗下考慮等待時間問題。在現實配送過程中，很多時候即使客戶時間窗為軟時間窗，由于配送時間問題、文書問題等都將導致等待的情況發生，因此本文考慮軟時間窗下等待的情況，此時比硬時間窗下更為復雜，因為等待隨時都可能發生，而硬時間窗下只需考慮時間窗之前的等待時間。

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

1　問題描述及模型建立

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

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

本文將等待時間引入軟時間窗VRP中，第k輛車在需求點i的等待時間記為wik，也是隨機變量，為簡化問題，假設等待時間也服從正態分布，即wik～N(μik2,σik2)。在實際生活中，時間窗內外都有可能產生等待，有時甚至會發生長時間等待的情況，如在給大超市進行配送時，零售商處于主導地位，配送企業可能需要等待較長時間，即使提前預約，有時也會需要等待1～2個小時。為簡化問題，本文暫不對此種情況作考慮。等待將對配送過程及司機勞動強度產生影響，將此類影響統稱為等待費用，其大小簡化為與等待時間線性相關。

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

車輛集合為K={1,2,…,m}，所有車容量均相同，為Q。假設車輛數量無限，根據實際調研，即使某些時候配送企業車輛數不夠用，但均有相應的應急處理方式，比如與其他配送企業簽訂戰略協議，可隨時借調車輛。某些需求點可能由多輛車服務。

符號說明見表1。

表1　變量符號說明Tab. 1　Variable symbol description

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

yik則為需求點i由車輛k進行配送的量。

目標函數為最小化綜合費用。

隨機規劃模型如下：

(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)

目標函數中期望延遲時間、期望提前時間和期望等待時間都是隨機的，本文通過將這三個期望量通過推導表示為行駛時間、服務時間和等待時間期望與方差的解析表達式，以提高計算過程中目標函數計算效率。

1.1　服務時間性質

1.2　到達時刻和開始服務時刻性質

令Tij表示車輛經過弧(i,j)從需求點i到需求點j所需時間，則車輛k到達需求點j的時間ajk為直到需求點j所有邊的行駛時間、需求點j之前的所有需求點的等待時間和服務時間之和，即：

其中：Ajk表示車輛k經過的直到需求點的j所有邊；Cjk表示車輛k上需求點j之前的所有需求點；yik為車輛k對Cjk中需求點的配送比例。

根據正態分布的可加性，到達時間ajk也服從正態分布，其均值和方差分別為：

由于本文中假定車輛到達需求點不一定直接開始服務，因此，車輛開始服務的時間為ssjk=ajk+wjk，由正態分布的性質得，開始服務時間也服從正態分布，其均值與方差分別為：

1.3　目標函數計算

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

其中：t≥0，δ≥0。

期望延遲時間可以根據以下過程計算得到：

所以：

同樣的道理，期望提前時間也可計算出來：

2　改進的粒子群優化算法

2.1　問題描述

本文結合問題特點，將自適應選擇和路徑重連融入PSO算法進行求解：路徑重連用于粒子位置更新，自適應選擇用于速度更新。

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

經典PSO中粒子移動取決于速度向量，粒子位置向量需要在連續空間和離散空間之間進行轉換，會丟失信息，降低隨機路徑問題的求解效率，影響解質量。本文使用路徑重連策略進行位置更新以避免PSO算法中位置向量在離散空間與連續空間之間轉換，提高求解效率。速度更新方程的角色有所轉變，用于衡量粒子在路徑重連過程中向自身最優、局部最優、全局最優進化的重要參數。粒子速度不再是粒子位置更新的主導，也減弱分批配送車輛路徑問題中統一粒子位置向量、速度向量、局部最優、鄰域最優和全局最優位置向量等向量非零元素個數而導致信息丟失或者增加無用信息帶來的影響。

最后，本文使用基于變鄰域搜索(Variable Neighborhood Search， VNS)算法的局部搜索策略對每個粒子進行優化以提高解的質量。在每次迭代中，粒子群中最優粒子和粒子自身最優被保存。本文求解最小化問題，目標函數值較大的解將被標記為劣解。算法在達到最大迭代次數時結束。

2.2　初始解生成

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

1)節約算法。

此算法為經典的VRP算法，將每個需求點看作一條路徑，然后通過連續的方式將距離最近的兩個路徑合并，從而得到VRP解。本文以此方式生成1個初始解，解中無需求點被分割，意在初始種群中放置較優的不產生分割的初始解。

2)改進的掃描算法。

掃描算法也是VRP經典算法，當一條路徑的容量未被耗盡且無法容下下一個需要加入的需求點時，分割此需求點，一部分放入當前路徑，剩余一部分放入下一條新路徑。本文以此方式產生一個初始解，部分需求點被分割。

3)隨機生成。

此算法隨機生成一個需求點的序列，并依次將需求點添加到路徑中，當前路徑容量未被耗盡且無法容下下一個需求點的需求量時，將此需求點需求量分割，部分放在當前路徑中，剩余部分放入下一條新路徑中。本文以此方式產生np-2個初始解，這些解中有可能無需求點被分割，部分解中部分需求點被分割。

2.3　編碼

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

2.4　速度更新

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

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

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

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

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

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

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

向量o在第N階段的得分按下式計算，其中得到的解為在組合鄰域拓撲階段得到的解：

2.5　粒子位置更新

文中每個粒子位置通過路徑重連進行更新，位置更新方程被路徑重連過程替代，能這樣做的原因為路徑重連思想與PSO算法中粒子位置更新思想是相似的，也是決定粒子向自身最優、向全局最優和向局部最優等移動。

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

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

2.6　粒子鄰域最優更新

本文使用擴展鄰域拓撲進行粒子局部鄰域最優的更新。借鑒Marinakis等[32]將VNS鄰域擴展的思想融入到擴展鄰域的做法，根據解的質量調整粒子鄰域，每個粒子的鄰域根據自身解優化程度的不同而不同。開始階段所有粒子鄰域是相同的,當某個粒子對應的解在連續一定數量itnum的迭代過程中都沒有被優化，只有它的鄰域進行擴展。在此策略下，每個粒子鄰域范圍不同。當鄰域范圍擴展到整個空間時，局部最優鄰域將從最小規模鄰域重新初始化。

2.7　局部搜索算法

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

2.8　出發時間調整

從PSO算法得到的解都是時刻0從車場出發，本文的后驗優化算法將每輛車從車場出發的時間以M分鐘循環調整，直到路徑綜合費用無法進一步降低為止。

3　算例分析

本文程序使用Matlab (2012b)編寫，運行平臺內存12 GB，顯卡2.9 GHz，64位操作系統。

算例采用Solomon[33]提出的經典算例進行測試，該算例構造時考慮了需求點空間分布和時間窗的合理性等，被很多學者選為測試算例。考慮Solomon的四類算例：R1、R2、RC1和RC2，且算例規模為100。R1和RC1類算例時間窗較短，車輛只能服務較少的需求點；R2及RC2類算例具有長時間窗，允許車輛對更多的需求點進行配送。在所有的測試中，期望行駛時間等于相應的歐幾里得距離。

3.1　算例調整

本文采用Ho等[6]提出的調整方式對實驗算例進行調整。其中：節點(包括車場和需求點)的位置、車容量、時間窗和服務時間與Solomon[33]的例子相同。在此基礎上，考慮對各個需求點的平均需求進行調整，將平均需求調整到區間[vQ,uQ]，其中，v和u均為(0，1]區間的數，且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]，并證實平均需求量較大的算例分割現象較明顯。綜合現有結果，本文考慮[v,u]取值為[0.1，0.9]和[0.3，0.7]的情況，所有調整的需求均取整。

3.2　算法參數

本文算法在Marinakis[31]算法的基礎上進行設計，故算法參數參考Marinakis[31]中的參數取值如表2所示。

3.3　結果分析

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

表2　實驗中算法的參數選取Tab. 2　Experimental parameters selection of the algorithm

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

不允許等待的情況同一般情況下的軟時間窗問題相同，不考慮等待時間，只考慮提前服務和延遲服務的懲罰費用。

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

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

從圖1可以看出，四類算例中絕大部分算例允許等待時總費用高于不允許等待時的總費用，平均高出3%左右。從計算結果看，產生此類現象的原因主要是由于考慮等待時間造成車輛服務時間延長，從而導致平均使用車輛數增加,具體如圖2所示。從圖2可以看出，超過70%以上的算例使用車輛數在考慮等待的情況下高于不考慮等待的情況，由于考慮等待而導致的車輛數平均增加0.62。但是，等待在實際配送過程中是普遍存在的，因此在實際配送運營中應盡量減少等待時間，以提升配送人員效率，提升服務效率。

2)行駛費用和懲罰費用。行駛費用是指不與時間相關的費用，包括車輛使用費用和車輛行駛距離產生的費用；懲罰費用是指與時間相關的費用，包括提前服務和延遲服務產生的懲罰費用。

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

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

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

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

3)考慮等待時間時更傾向于分批配送。如圖5所示，從最優解中最終配送點數量來看，80%以上的算例考慮等待時間時多于不考慮等待時間的情況，平均多約2.8個；考慮等待時間更傾向于分批配送。

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

1)總費用對比。如圖6所示，總體來看，允許分批配送時比不允許分批配送時總費用有所降低。所有測試算例中，約61.5%的算例總費用低于不允許分批配送，所有算例總費用平均降低約2%。

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

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

2)車輛數對比。如圖7所示，總體來看，是否允許分批配送對最優解中車輛數的影響不具有一般規律，特別在R1、R2類算例中。在RC1類算例中，不允許分批配送時車輛數總體少于允許分批配送；而在RC2類算例中，不允許分批配送時車輛數則多于允許分批配送，此時分批配送將為最優解帶來更顯著的節約。將所有算例數據匯總來看，允許分批配送時使用的車輛數比不允許分批配送時使用的車輛數平均少約0.6。

3)配送點數。如表3所示，四類算例平均配送點數達105.9，分割點比例達到5.9%，測算過程中，80%以上的算例最優解中均產生分批配送的需求點，允許分批在較大規模算例中能起到較好作用。

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

圖7　車輛數在是否允許分批配送情況下的對比Fig. 7　Comparison of number of vehicles for allowing split or not

表3　四類算例平均配送點數Tab. 3　Average number of delivery customers for four types of instances

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

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

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

4　結語

本文在軟時間窗下考慮等待時間，建立帶修正的隨機規劃模型，并設計改進的PSO算法進行求解。算法結合三類不同的拓撲，使用路徑重連算法有效解決了粒子位置向量在連續空間和離散空間轉換造成的信息丟失問題，并采用自適應選擇解決了分批配送引起的向量長度不一致問題。

通過對調整的Solomon算例進行測試，算法能有效求解本文提出的問題。考慮等待時間將造成總費用平均增加約3%，使用的車輛數平均增加0.62。懲罰費用占總費用的比例平均降低約9.65%，考慮等待時間對懲罰費用影響較大，等待時間產生的費用部分由懲罰費用轉化而來。同時考慮等待時間的情況也更傾向于分批配送，最終配送點數平均多約2.8。

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

進一步的研究集中在兩個方面:1)設計更高效的基于種群的進化算法求解隨機分批配送問題，比如螢火蟲群算法等；設計動態求解或精確求解算法解決行駛時間隨機車輛路徑問題等。2)尋求合理的方法對等待時間分布進行研究，更深入、精確地分析等待時間在配送中的影響；將城市交通流量、交通信號控制等與車輛路徑問題相結合，考慮更接近現實情況、更復雜的動態車輛路徑問題。

參考文獻:

[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].交通運輸系統工程與信息,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]李鋒,魏瑩.求解隨機旅行時間的C-VRP問題的混合遺傳算法[J].系統管理學報,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]王征,胡祥培,王旭坪.行駛時間延遲下配送車輛調度的干擾管理模型與算法[J].系統工程理論與實踐,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]李妍峰,高自友,李軍.基于實時交通信息的城市動態網絡車輛路徑優化問題[J].系統工程理論與實踐,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]李相勇,田澎.帶時間窗和隨機時間車輛路徑問題:模型和算法[J].系統工程理論與實踐,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.