混合粒子群算法求解帶軟時間窗的VRPSPD問題

范厚明，劉文琪，徐振林，耿 靜

1.大連海事大學 交通運輸工程學院，遼寧 大連 116026

2.大連海事大學 戰略與系統規劃研究所，遼寧 大連 116026

1 引言

同時集配貨車輛路徑問題（Vehicle Routing Problem with Simultaneous Pickup and Delivery，VRPSPD）是VRP中應用廣泛的的變體之一，其擴展為每個客戶處擁有集貨和配貨需求且要求車輛服務一次同時滿足這兩種需求。這種情況在實際生活中也廣泛的存在，如：飲料行業空瓶的回收、包裝物以及裝載設備的循環再利用，工業有毒物品的回收凈化再處理等[1]，在減少資源浪費的同時，又能夠產生經濟效益?，F有研究表明，這種配送模式與單向配送相比能夠有效地降低成本，提高效益[1-2]。因此隨著環保意識的提高和逆向物流的發展，該類問題日益受到研究者的關注。為了更加貼近現實，考慮客戶對于車輛到達時間有要求的實際情況，本文求解了更一般化的帶軟時間窗VRPSPD問題，即允許車輛到達時間違背時間窗約束，并產生相應等待或耽擱成本，這樣處理不僅可以更好地從配送企業角度衡量工作效率，同時也能更好地保證一定的服務水平。

VRPSPD最早由Min[3]提出，解決了中心圖書館與地方圖書館之間圖書分發與回庫的問題。Dethloff[4]首次從逆向物流的角度對問題進行了定義，并采用一種考慮車輛剩余裝載能力的插入啟發式算法進行求解。由于VRPSPD是NP-hard問題[5]，因此更多的此類問題的求解方法主要集中于能夠在較短時間內獲得滿意解的啟發式算法、模擬退火算法[2]、遺傳算法[6-7]、蟻群算法[8-9]、禁忌搜索[10]、量子進化算法[11]，以及混合算法[12]等，獲得了一定的研究成果。然而，由于VRPSPDTW（VRPSPD with Time Window）的決策目標、約束條件更為復雜，使求解難度進一步加深，因此相關研究相對較少，仍有進一步研究的需要。曹二保等[5]首次采用差分進化算法進行求解，并提出一種根據解滿足約束的情況，進行不斷調節得出最小所需車輛數的方法，解決了客戶數為8和40的帶時間窗的同時集配貨車輛路徑問題（VRPSPDTW）；Wang和Chen等[13]擴展了Solomon[14]關于VRPTW（Vehicle Routing Problem with Time Window）的測試算例，通過CIM（Cheapest Insertion Method）的多種變形產生初始解，并提出一種共同演化遺傳算法對VRPSPDTW進行了求解。王超等[15]采用模擬退火算法求解該問題，其中通過RCRS（Residual Capacity and Radial Surcharge）插入準則獲得初始解，在此基礎上Wang等[16]又進一步提出并行模擬退火算法對其求解，均與Wang和Chen等[13]的遺傳算法進行比較。黃務蘭等[17]通過改進的全局人工魚群算法與平行模擬退火[16]在VRPSPDTW求解結果上的比較，驗證了其改進算法的有效性。王超等[18]采用離散布谷鳥算法對VRPSPDTW問題進行了求解，通過Rank值的非參數假設檢驗對算法進行了驗證。Belgin等[19]對二級同時取送貨車輛路徑問題進行了研究，并采用變鄰域下降搜索結合局部搜索算法對該問題進行了求解。

雖然現有研究對于求解VRPSPDTW已獲得一定的成果，但是對更貼近現實配送業務要求的帶軟時間窗VRPSPD研究卻寥寥無幾。鄧愛民等[20]建立了帶軟時間窗VPRSPD的數學模型，采用增加了記憶功能的改進模擬退火算法對其進行了求解，并通過算例求解驗證了算法的可行性，但在求解結果上仍有改進空間。通過上述軟硬時間窗模型在整體成本的比較來看，即使車輛在某客戶處違背時間窗約束，存在總配送成本相對較低的情況，即求解軟時間窗約束的問題有可能產生在硬時間窗約束下難以獲得的可行解，并且該類問題的通用性很強，可以經過一些參數或條件的改變轉化為其他VRP擴展問題，因此與硬時間窗約束相比，軟時間窗約束具有不可替代的優勢。從查閱的文獻中可知，目前將粒子群算法應用求解于帶軟時間窗的VRPSPD問題的研究還較少，并且結合不同的啟發式算法進行優勢互補，已然成為學者研究的重要方向之一。周蓉等[21]提出混合的離散粒子算法對VRPSPDTW進行了求解，結合了變鄰域下降（Variable Neigborhood Descent，VND）和模擬退火算法的選擇機制，其中是對每個粒子進行一定概率地選擇VND。然而在后續的實驗結果中得出，不同結合方式在一定程度上影響算法的性能。為了更好地探索和提供不同算法結合的思路，本文提出結合以VND為適應性擾動機制主體的混合粒子群優化算法（Particle Swarm Optimization，PSO），對帶軟時間窗的VRPSPD進行求解。

PSO是一種基于群體智能搜索算法，模擬鳥類飛行的仿生算法，有著概念簡單清晰，參數較少，魯棒性好等優點，且在各類多維連續空間優化問題上表現出良好的特性[22]，在VRP及相關領域也有廣泛應用，并取得較好的結果[22-27]。在PSO的參數中，慣性權重具有平衡全局和局部搜索的作用，因此本文所提算法在PSO中加入了適應性權重。但是由于其進化只是根據粒子個體自身經驗信息和種群中的信息共享，所以容易陷入局部最優，出現早熟的現象，且爬山能力弱，不易跳出。本文提出結合以VND為主體的適應性擾動機制（Adaptive Perturbation Mechanism，APM）的混合粒子群搜索算法，能夠更好地根據種群陷入局部極值的情況進行適應性擾動，其與以往采用擾動機制的文獻[28-30]的不同之處：

（1）算法在種群迭代過程中，很有可能不只一次陷入局優，且每次陷入局優的情況不同，本文提出線性變化的調取APM準則，這樣可以在充分發揮PSO全局搜索性能的前提下，提高搜索效率。

（2）在Shaking階段中，不是所有的鄰域結構都被采用，也不是隨機或依已有概率來進行鄰域結構的選取[5，16，28，30]，而是根據適應權重采取輪盤賭的方式進行選取。

（3）對于擾動后產生的劣解不是一味地舍去，而是根據一定準則接受（詳見3.4.3小節），以便跳出局優。

本文主要研究帶軟時間窗的VRPSPD問題，設計了結合以VND為主體的適應性擾動機制的混合PSO算法進行求解，以車輛派遣成本、行駛成本和時間窗懲罰成本之和為總優化目標。實驗結果分析表明，算法具有良好的尋優性能。

2 問題描述及數學模型

2.1 問題描述

VRPSPDSTW問題可以描述如下：多臺同質車輛從物流中心出發，為一系列客戶點進行服務，且每個客戶處均設有獨立的服務時間窗。軟時間窗約束允許車輛到達時間早于或晚于所設時間窗，并根據偏離時間窗的長短進行懲罰。每輛車在訪問客戶點時，先卸貨后取貨，一次性滿足客戶的集配貨需求，并且在任何服務節點均不得超過車輛容量限制，在服務完所分配的客戶后，返回物流中心。要求在滿足所有客戶需求的前提下，使得車輛派遣成本、行駛成本和時間懲罰成本之和最小?？勺鋈缦录僭O：

（1）已知各客戶和物流中心的位置，且客戶處的送取貨量已知。

（2）每個客戶只能一輛車訪問一次，并且要求車輛同時滿足集配貨兩種需求。

（3）物流中心擁有多臺同質車輛，即容量一致，且能夠滿足所有客戶的需求。

（4）車輛平均行駛速度已知且不變。

（5）客戶的服務時間窗已知。

2.2 問題描述模型建立

為了方便建模描述VRPSPDSTW問題，本文采用如下的符號體系。

Q：車輛最大容量；

Di：客戶i處的配貨量，非負值且小于Q；

Pi：客戶i處的集貨量，非負值且小于Q；

ETi：客戶i的時間窗下限；

ELi：客戶i的時間窗上限；

Tik：車輛k在客戶i的到達時間；

WTi：客戶i的等待時間，即WTi=max{ETi-Tik,0}；

si：客戶i的服務時間；

dij：車輛從客戶i到客戶 j的距離（采用歐幾里得距離得到）；

tij：車輛從客戶i到客戶 j的行駛時間；

n：總的客戶數，其中采用i、j表示客戶編號；

m：總的車輛數，其中采用k表示車輛編號；

cv：每輛車的派送成本；

cd：單位距離運輸成本；

CTi：車輛早于時間窗到達時，單位時間機會損失成本；

CLi：車輛晚于時間窗到達時，單位時間懲罰成本；

yijk：表示經由客戶i到客戶 j的車輛k，離開客戶i的車輛載重量；

xijk：為決策變量。若車輛k從客戶i直接到達客戶 j，xijk=1，否則為0。

建立相應的數學模型如下：

式（1）為目標函數，其中第一部分表示車輛派遣費用；第二部分表示運輸費用；最后一部分是由早到或晚到時間懲罰成本構成；式（2）確保派出的車輛數不超過最大車輛數；式（3）各節點車輛進出平衡，當i為0時，表示車輛從中心出發后又返回中心；式（4）確保每個客戶只被一輛車訪問，且只能訪問一次；式（5）為消除子回路約束；式（6）表示路徑上任意節點處的車輛載重均不超過最大載重量；式（7）表示車輛從中心出發時的載重量與所要配送的客戶的配貨量相等，且不超過Q；式（8）表示車輛返回物流中心，載重量為所服務客戶總的取貨量，且不超過Q；式（9）車輛在經由前后客戶節點后的載重平衡，即車輛離開節點j的載重量等于車輛到達時的載重量去掉 j的配貨量，增加 j的取貨量；式（10）表示時間約束，其中M 為一個任意大的數；式（11）、（12）為變量屬性約束。

3 混合PSO算法設計

3.1 PSO基本原理

PSO算法最初是由Kennedy和Eberhart于1995年提出一種新的仿生進化算法[31]，模擬鳥群覓食行為，通過鳥之間的協作和個體經驗來引導鳥群的整體運動。在PSO算法中，每個備選解抽象成一個無質量的粒子，若干個粒子形成一個種群，搜索過程為每個粒子追隨兩個極值，一個是粒子本身歷史搜索的個體極值 pbest，另一個是全種群到目前為止搜索到的群體極值gbest。所有粒子都有一個根據目標函數所確定的適應值進行評價，有相同維度的位置和速度向量，速度來決定各個粒子飛行的方向和距離，其數學描述如下：

設種群中每個粒子代表D維空間中的一個解，在第t代第i個粒子位置表示為，速度表示，該粒子第t代的個體最優位置為 pbestt，種群第t代的種群最優位置為gbestt，在第(t+1)代狀態粒子速度和位置更新公式如下：

其中，c1、c2表示加速因子，r表示[0，1]之間的隨機數，w表示慣性因子，其大小的設置影響著算法的收斂速度和結果，較大的w有利于跳出局部最優解，有利于提高算法的全局搜索能力，較小的w有利于算法收斂，會增強算法的局部搜索能力。

3.2 粒子編碼

為了充分發揮PSO在連續空間優化問題良好的搜索性能，本文采用實數編碼方式[25]，即對于擁有n個客戶、m輛車的問題來說，粒子的速度和位置均為n維實數向量，速度每一維的整數部分表示所用車輛編號，在同一車輛編號（即整數部分相同）的小數部分，大小順序對應該客戶在此路徑中的訪問順序。故每個粒子的位置取值范圍為1～m.99，速度取值范圍為-(m.99-1)～(m.99-1)。為了保證粒子在可行范圍內搜索，限定位置變化范圍為[xmin,xmax]，速度變化范圍為[vmin,vmax]。

3.3 初始化種群

首先根據3.2節編碼方式和設定范圍隨機生成粒子的速度和位置，然后其中的一半粒子根據最鄰近方法并轉換成實數編碼，產生新的位置，由于粒子的速度和位置是一一對應關系，所以這一半粒子的速度是根據式（14）將前后兩個位置相減得到。

由于算法采用的是實數編碼，所以本文提出如下映射方法，將最鄰近方法產生的解映射為實數形式，即：在同一車輛訪問的節點集合中，假設共有n個節點，車輛編號為k，則對于該路徑上的第i個節點來說，其位置大小為i×0.99/(n+1)+k。

3.4 適應性擾動機制APM（Adptive Perturbation Mechanism）

在PSO算法中，gbest記錄著當前種群經歷的最優狀態，影響所有個體位置狀態的變化過程。若一味地接受更優解，很有可能導致算法的搜索逐漸聚集在局優附近，探索能力減弱。因此，為了改善上述問題，本文通過以VND為主體根據算法搜索進程情況進行適應性擾動，不僅可以擴展搜索的空間，而且可以根據設定的閾值接受劣解，以便跳出局優。同時為了防止因擾動而丟失搜索過的最好解，將Gbest作為歷史搜索到的最優解，gbest作為種群極值。

對于擾動機制來講，一個是擾動的時機，它可以有效地平衡PSO和VND兩者之間搜索優勢的發揮，另一個是構成擾動部分采用變鄰域結構，這兩者都對擾動部分產生的效果起著關鍵性的作用。

3.4.1 線性啟動準則

為了更好地發揮PSO的全局搜索能力，同時也為APM過程提供一個較好質量的擾動解，故本文提出如下線性啟動準則：

其中iter表示PSO中的迭代次數，noimp_max和noimp_min分別表示最大、最小允許歷史最優解Gbest未改進次數，若Gbest在連續多代未得到改進則認為算法陷入局部極值，所以只有當Gbest的未改進次數noimp_times大于viacriterion時，啟動APM。

3.4.2鄰域結構

在進行VND搜索之前，需要先定義一組鄰域結構，本文采用了路徑間、路徑內等常見的鄰域結構來進行擾動。

為了提高執行操作的有效性，在路徑間鄰域變換中，首先隨機選擇一條路徑，通過計算此路徑與解中其他路徑重心之間的距離，并將各個距離與所有距離之和的比值作為選擇概率，根據輪盤賭規則選擇另一條路徑r2。

（1）Cross1：由于所選兩個路徑所含客戶數不同，所以分別隨機選擇交叉點。交叉點將路徑劃分為兩部分，路徑r1的第一部分與r2的第二部分結合形成新的路徑，同理r1、r2的剩余兩個部分結合成另一條新路徑（見圖1）。

圖1 Cross1鄰域結構示意圖

（2）Cross2：此交叉操作與Cross1類似，不同之處在于路徑r1的第一部分與r2的第一部分結合形成新的路徑，同理r1、r2的剩余兩個部分結合成另一條新路徑，其中r1節點的順序不變，r2節點的順序要進行逆轉（見圖2）。

圖2 Cross2鄰域結構示意

（3）Shift（0，n）：在r1中任選一點或兩點插入到r2中，即n取1或2。

（4）Exchange(m,n)：在r1、r2中分別選取連續的m、n個節點，將r1中的m個節點和r2的n個節點進行交換，在本文中，m取1或2，n取1。

（5）采用的路徑內鄰域結構如下，設解s中任選一條路徑r。

（6）Swap：在r中交換任意兩點的位置。

（7）插入：在r中任選一點或兩點插入到路徑中另外位置。

（8）2-opt：在r中任選兩點，將兩點間的節點順序逆轉。

3.4.3 適應性選擇鄰域策略

本文采用適應性選擇策略[32]來選擇路徑間某一鄰域結構進行搜索。與隨機選擇某一鄰域進行變化相比，可以使搜索過較好解的鄰域結構有更大機會被選中，減少搜索的盲目性，其內容如下。

起初，每個路徑間鄰域結構的權重賦予為1，擾動次數每隔50代進行更新權重，并重置使用次數和所得分數。根據如下公式進行更新[32]：

σj,t計算準則：在同一周期中，經過路徑間鄰域結構變化后，若其適應度值優于歷史搜索到的最優解Gbest，則此鄰域結構加30分，并設noimp_times為0，同時更新Gbest和gbest；若其所得解未進一步改善Gbest，但卻優于Gbest+Gbest×δ，δ為偏差系數，δ∈(0,1)，則加10分，并累加noimp_times，Gbest不變，但更新gbest，起到擾動PSO的作用；如果均不滿足上述兩種情況，而是獲得了滿足約束解，則加6分，并替換種群中最差的粒子；否則分數不變。在本文所提算法中，δ取0.1。

3.4.4擾動搜索過程

本文設計的算法主要由路徑間VND和路徑內VND組成，為了方便描述分別表示為inter-VND、intra-VND。擾動部分其過程如下。

擾動搜索步驟如下：

步驟1輸入初始解s，定義一組路徑間鄰域結構Nm，其中m=1,2,…,mmax，路徑內鄰域結構Nn，其中n=1,2,…,nmax。

步驟2 Shaking：根據3.4.3小節中的策略選擇鄰域為N，在該鄰域多次循環，獲得其中的最小解即s1←N(s)，與 f()s進行比較，若優則進行替換s。

步驟3 inter-VND其過程的偽代碼如下[9]：

1.m←1；

2.whilem＜mmax

3.inter←1；

4.whileinter＜mmax

5.s2←Nm(s)；/找到在鄰域Nm中的最好解/

6.if f(s2)＜f(s1)

7.s1←s2；

8.m←1；

9.else

10.m←m+1；

11.end

12.inter←inter+1；

13.end

14.end

步驟4 intra-VND。路徑內的鄰域變化與上述步驟相同，其中不同的是輸入的初始解為s1，采用的是路徑內鄰域變化結構，以及所包含鄰域的個數為nmax。

步驟5根據3.4.3小節進行選擇鄰域，結束擾動。

值得注意的是，搜尋解s在某種鄰域結構的局優時，較易忽略循環的設定次數[9]。所以為了更好地提高搜索效率，本文在此過程（即在上述步驟5）中加入自適應性循環次數變化，可以根據在該種鄰域結構搜索到解的質量來調整循環次數。

假設當前鄰域結構為N，輸入的初始解為s，初設循環次數 pmax，首先在該鄰域隨機獲得一個擾動解s′，由于鄰域變化本身帶有隨機性，所以在搜索過程中，獲得的鄰域解的質量有所不同，其質量的優劣決定了在當前鄰域搜索的次數多少。如果搜索到解s″優于當前s′，則代替當前解，在此基礎上若滿足設定的條件，則增加循環次數 pmax+1。如果不優于解s′，則累計循環計數器 p，若在此基礎上不滿足設定的條件，則減少循環次數 pmax-1，其中設定的條件為滿足約束。同時，為了進一步控制循環的進程，計算在同一鄰域中搜索到可行或不可行解連續出現的次數，若不小于ε，則變化循環次數。根據先前的實驗，ε設為3。主要步驟如下：

1.s'←N(s);p←1;mm=0；

2.while p＜pmax

3.s''←N(s)；

4.iff(s'')＜f(s')

5.s'←s''；

6.ifs'滿足條件 /可以設定為滿足可行約束/

7.pmax←pmax+1；

8.mm←0；

9.end

10.else

11.p←p+1

12.ifs'不滿足設定的條件

13.mm=mm+1；

14.ifmm＞=ε]

15.pmax←pmax-1；

16.end

17.end

18.end

19.end

3.5 適應性權重

在PSO部分，本文采用如下適應權重，其更新公式如下，設權重最小值wmin，最大值為wmax，第i個粒子的適應值為 fi，種群最小值為 fmin，平均值為 favg，對于粒子i的權重值計算如下：

3.6 算法求解過程

算法求解過程如下，其流程圖見圖3。

圖3 混合粒子群算法流程圖

步驟1采用上述3.3節方法產生初始粒子的位置和速度，計算適應度值并初始化種群的個體 pbest和種群的gbest、Gbest，以及最大迭代次數、加速因子等相關參數。

步驟2計算粒子的適應性權重（公式（17）），并根據公式（13）和（14）更新粒子位置和速度，計算適應值。

步驟3若優于粒子個體最優適應值 pbest或種群最優適應值gbest，則相應地更新 pbest或gbest。

步驟4種群所有粒子全部更新完以后，若gbest優于歷史最優Gbest，則更新Gbest，設noimp_times為0，否則累加未改進的次數。

步驟5判斷是否滿足擾動準則，是則依3.4.4小節方法進行擾動搜索，進行下一步，否則轉至步驟8。

步驟6對擾動后的解依3.4.3小節進行評分并記錄鄰域使用次數，以及相應地進行更新。

步驟7判斷是否達到下一評分周期，若達到則更新權重，并重置分數和使用次數。

步驟8若迭代次數達到最大允許迭代次數且未改進次數達到終止的最大次數，則終止算法，否則返回步驟2。

4 算例驗證與結果分析

為了驗證所提算法的可行性和有效性，本文進行了3組實驗。第1、2組實驗分別選取了文獻[13]和文獻[21]中的算例進行硬時間窗問題的測試，第3組實驗選取文獻[20]中求解帶軟時間窗VRPSPD問題的算例測試。本文所設計算法在Matlab 2015a平臺上編譯，并在PC機上運行實驗（測試環境CPU：雙核奔騰2.80 GHz；內存：2 GB；操作系統：Windows 7）。

實驗1實驗選取由Wang和Chen[13]生成求解VRPSPDTW的算例，分別與遺傳算法[13]、模擬退火[15]、平行模擬退火[16]以及全局人工魚群算法[17]進行比較。

在這組實驗中不同規模算例所取參數如下：W_min和W_max分別表示慣性權重的最大、最小值，Popsize表示種群規模，Itermax表示最大迭代次數（見表1）。加速因子c1=c2=1.496 18，在擾動部分中，Shaking階段在同一鄰域循環次數為3倍的Popsize，pmax在路徑間、路徑內分別設為2倍的Popsize、Popsize。值得注意的是，50個客戶規模的算例中，為了充分地進行擾動，shaking階段采用的鄰域有所不同，采用的是doublereplace（1，1），triple shift（1，0），triple swap（1，1），double cross[30]以及exchange（m，n）（其中 m 和 n 的組合為（3，2）、（3，1）和（2，2））。

表1 不同規模算例所用參數

表2列出了本文所提算法運行10次獲得的最好解，并與其他算法在總運輸距離的比較。其中將Wang和Chen[13]采用GA計算的結果作為標準1，其他算法的結果進行“標準化”，即第二至五列均為與GA的比值，最后一列給出了所提算法計算得到的結果，最后一行列出了各算例的比值平均值。由表2可知，除算例Rcdp5004外，其他算例均能找到當前已知最好解或更優解，從比值的平均值來看，本文所提算法為0.937 5，分別與SAA[15]、p-SA[16]、IGAFSA[17]相比都較小，其中 Rcdp1007改進最大。在9個算例中，更新了6個算例的最好解。在求解50個客戶規模的算例運行時間均在820 s以內獲得，雖然運行時間較長（采用了多鄰域循環所致），但是仍在可以接受的范圍之內。綜上，可以驗證所提算法的可行性和有效性。

表2 各算法運行結果比較

Rcdp1001軌跡圖如圖4；Rcdp2504軌跡圖如圖5。

圖4 Rcdp1001軌跡圖

圖5 Rcdp2504軌跡圖

實驗2根據文獻[21]擴展的Solomon[14]算例的方法，生成配送和取貨需求，在RC類算例中形成客戶規模分別為10、25和50共9個算例。該組實驗采用的相關參數與實驗1相同。表3為本文算法與文獻[21]運行結果的比較，從表中的結果可以得到，本文算法的節省車輛數（NV）和總行駛距離（TD）結果都優于離散粒子群算法DPSO[21]（Discrete Particle Swarm Optimization），在算例RCdp25107的比較結果可知，雖然所用車輛數比DPSO多1輛，但是總行駛距離改進了29.83%。在各算例運行時間均在475 s之內，雖然相比較而言，耗時較長，但仍在可接受范圍內。綜上表明，本文算法優勢明顯，同時也說明不同結合方式很大程度上影響著算法的性能。

表3 與離散粒子群算法結果比較

實驗3本文根據文獻[20]中，包含1個物流中心和20個客戶點的算例，用來求解帶有軟時間窗的VRPSPD問題，通過計算總需求量與車輛載重的比值可知，最少需要車輛數為3，為了保證產生的粒子的多樣性且有效地減少搜索的盲目性，本文設定車輛數為4。該實驗所選用的參數與實驗1中25個客戶規模的算例相同，在模型中的參數與文獻[20]中相同。

表4列出的是加入適應性權重的基本PSO（用BPSO表示）、SA[20]和本文所提算法運行10次的結果，從中可以看出本文算法在10次運行中均能找到較高質量的解。從表中得知，與BPSO相比，在平均值、最好值和最差值上分別改進了12.84% 、17.91%、14.69%，說明在PSO的基礎上，所提算法可以有效地跳出局部最優；與文獻[20]的SA比較，分別改進了5.08%、12.95%、4.05%。本文算法所獲的最好解其總配送成本為175.2元，總運輸距離為113.1 km，所用總的車輛數為3，與前兩個算法所用車輛數均少1。具體的配送路線為：第1輛車：0-14-13-5-4-19-6-12-0；第2輛車：0-8-9-18-10-11-3-15-0；第3輛車：0-7-20-1-17-16-2-0。算法在10次運行的平均耗時為160.9 s，雖然算法耗時較多，但仍在可接受的范圍內。

表4 各算法運行結果比較

如圖6為本文算法運行最好結果（即第10次實驗）總配送成本和運輸成本的迭代變化圖；如圖7是其中擾動種群全局極值的變化圖。從兩者比較來看，在1 000代左右以及1 600代到1 900代這兩個階段的擾動，均能有效地引導算法跳出局優；在2 000代以后算法最終收斂。

圖6 迭代變化圖

圖7 擾動圖

綜上，擾動部分可以更進一步優化PSO的搜索進程，起到改進的作用，同時也驗證了算法的可行性和有效性。

5 結論語

本文針對更貼近現實物流配送網絡的帶軟時間窗VRPSPD問題，建立了以車輛派遣成本、行駛成本和時間窗懲罰成本之和最小為目標的車輛路徑優化模型，設計了混合PSO算法進行求解。為了克服PSO容易陷入局部最優，爬山能力弱等問題，在Gbest未改進次數達到線性擾動啟動準則計算的值時，啟動適應性擾動機制，即進行VND擾動，其中在Shaking階段采取了適應性選擇鄰域策略，并在每個鄰域搜索中應用可變的循環次數，以便提高對解空間的探測能力和搜索效率。

通過與現有算法求解結果比較，本文所設計的混合PSO能夠有效地求解該問題，同時也表明了擾動機制可以很好地跳出局部最優，并在可接受的時間范圍內獲得滿意解，驗證了算法的有效性。今后，將針對不同算法之間的結合方式，以及求解更一般化的車輛路徑問題進行進一步研究。