基于改進粒子群算法的帶模糊時間和需求量的VRP問題

朱顥（湖州職業技術學院，浙江 湖州 313000）

基于改進粒子群算法的帶模糊時間和需求量的VRP問題

朱顥
（湖州職業技術學院，浙江 湖州 313000）

針對車輛旅行時間、卸貨時間和客戶需求量均為模糊變量的VRP問題，建立了基于可信性測度的模糊機會約束規劃模型，并用改進的粒子群算法進行優化，算法以實數形式進行編碼，針對不可行解，設計了專門的修復算子。通過仿真實驗證明，該算法對于解決此類模糊VRP問題是行之有效的。

車輛調度問題；模糊旅行時間；模糊需求量；粒子群算法

1 引言

車輛路徑問題(Vehicle Routing Problems)作為一類NP難的組合優化問題，由學者Dantzig和Ramser[1]于1959年首次提出,可以描述為：配送中心根據現有的資源和信息（如車輛、客戶、距離等），在某些約束條件下（如客戶服務時間要求、車輛容積限制等），為一系列客戶安排送貨車輛并選擇合適的行車路線，以達到某些目標的最優（如總成本最低，總路線最短）。在實際應用中，由于受客觀世界不確定因素及人類認識事物的模糊性影響，車輛路徑問題中的某些信息可能是模糊的、不確定的，如車輛旅行時間、客戶需求量等均存在不確定的情況，此時需要從模糊的視角來處理該類問題。

目前，國內外有關模糊VRP問題的研究文獻中，以模糊需求量為特征的文獻有：Teodorovic等[2]引入決策者偏好，采用模糊推理算法求解了帶模糊需求的車輛路徑問題；祝崇雋等[3]等在國內較早地針對帶模糊需求的VRP問題，通過模糊模擬來估算車輛額外行程，并運用基于可能性分布和基于需求上界的2-OPT算法進行尋優；張建勇等[4-5]考慮了由于任務“失敗”而產生的額外行駛距離，設計了一種新穎的交叉算子,并運用遺傳算法進行求解；張建勇等[6]還對于同一類問題，設計了相應的weeping啟發式算法；曹二保等[7-8]運用差分進化算法對此類問題進行了求解，在該算法中設計了基于整數序規范的輔助算子；戎麗霞[9]針對同樣的問題，運用遺傳算法進行了求解；吳天羿等[10]運用遺傳算法研究了該問題，在算法中運用掃描算子進行種群的初始化，設計了專門的混合交叉算子和差分掃描變異算子；Lian xue[11]利用改進的差分進化算法進行求解，在交叉環節，交叉概率隨迭代次數線性增加；R.J.Kuo等[12]將粒子群算法和遺傳算法結合，通過每個粒子與其自身經歷過的最優狀態及粒子群最優粒子之間的多次交叉操作，選取較優的子代粒子替代當前粒子；Cao Erbao等[13]用所有車輛的總距離（包括計劃行駛距離和額外行駛距離的）作為尋優的目標，設計了相應的隨機模擬算法來估算額外行駛距離，針對有可能產生的不可行解，引入了相應的懲罰函數，最后利用差分進化算法進行了求解；Yang Peng等[14]針對帶模糊需求量的VRP問題，提出了基于整數編碼的粒子群算法，對粒子更新過程中產生的實數，利用基于升序的排序規則，將實數轉換成整數。

在考慮模糊環境時，以車輛旅行時間為特征的文獻有：Y.Zeng和B.Liu[15]運用混合遺傳算法研究了帶模糊旅行時間的車輛路徑問題；Ghannadpour等[16]提出了一類帶模糊旅行時間和客戶滿意度的多目標動態VRP問題，并提出了基于遺傳算法的動態解決策略。Jianyong Zhang 等[17]分析了一類旅行時間具有模糊特征的VRP問題，建立了以最小化總模糊旅行時間為目標的數學模型，提出了針對決策者偏好和旅行時間的模糊集，并建立了基于模糊邏輯的優化選擇規則，最后針對該問題，提出了一種混合遺傳算法。Seyed Farid Ghannadpour等[18]考慮了帶模糊旅行時間的動態多目標VRP問題，運用遺傳算法進行了優化。

從有關模糊VRP問題的文獻來看，模型主要集中于帶模糊需求量的VRP問題上，對具有模糊旅行時間的VRP問題研究文獻還不多，特別是同時帶模糊需求量、模糊車輛旅行時間、模糊卸貨時間特征的文獻更少。本文考慮同時帶模糊需求量、模糊旅行時間、模糊卸貨時間的VRP問題，并假設車輛到達客戶處時，不管到達時間是否處于時間窗口內，均立即卸貨，基于此假設，構建相應的模糊機會約束規劃模型，利用改進的粒子群算法進行優化。

2 模糊可信性理論

Zadeh于1965年提出了模糊理論，劉寶碇等[19]在此基礎上,提出了模糊可信性理論。假設Θ為非空集合，Ρ(Θ)表示 Θ的冪集，若 Pos是可能性測度，則(Θ,Ρ(Θ),Pos)為可能性空間，若A是冪集Ρ(Θ)中的一個元素，則為事件A的必要性測度；(Pos{} A+Nec{}

A)稱為事件A的可信性測度。

假設 q，ξ均為三角模糊數，q=(q1,q2,q3)，ξ=(r1,r2,r3)，Q、a、b為常數且a＜b，根據可信性理論，可知：

Cr{a ≤ξ≤b}的取值經過歸類，分為7種情況，見表1。

表1 Cr} ≤ξ≤b的各種取值情況

表1 Cr} ≤ξ≤b的各種取值情況

Cr{ } a≤ξ≤b Cr{ } a≤ξ≤b , 0 b-r3r2-r3條件b＜r1或者a＞r3r1≤b＜r2a＜r1且r2≤b≤r3a＜r1且b＞r31-12max{ } a-r1r2-r1(b-r1) 2(r2-r1) 2r2-r3-b 2(r2-r3) 1 2r2-r1-a 2(r2-r1)條件r1≤a＜r2且r2≤b≤r3r1≤a＜r2且b＞r3r2≤a≤r3(a-r3) 2(r2-r3)

3 帶模糊時間和模糊需求量的VRP模型

本文描述的帶模糊時間和模糊需求量的VRP問題為：一個配送中心（用“0”表示）為客戶提供送貨服務；該配送中心有m輛車可以利用，每輛車的標記載重量固定不變；每輛車一次只能有一條行駛路線；每輛車從配送中心出發，完成若干客戶的送貨任務后返回；每個客戶每次只能由一輛車提供服務；每個客戶均有一個服務時間窗口，送貨盡可能在此范圍內完成（同時假設配送中心也有一個時間窗口，所有車輛在某一時間前按時返回）；每個客戶的貨物需求不確定，為三角模糊數；每輛車的途中旅行時間和在客戶處的卸貨時間均不確定，為三角模糊數。本問題的實質是在滿足一些列的約束條件下，為每輛車選擇相應的客戶，并合理地安排送貨順序，安排每輛車從配送中心出發的時間，使得某一個目標最優（如距離最短）。為方便敘述，給出如下符號：

i=0,1,2,...,n，其中0表示配送中心，1,2,…,n表示客戶，客戶總數為n；

k=1,2,...,m表示車輛編號，車輛總數量為m；

qi表示客戶i的貨物需求量，i=1,2,...,n；qi為一個三角模糊數(qi1,qi2,qi3)；

Qk表示車輛k的標記載重量，k=1,2,...,m；

Dij表示客戶i和 j之間的距離，i,j=0,1,2,...,n；

[ai,bi]為客戶i的服務時間窗口，i=0,1,2,...,n；

Tij表示車輛從客戶i到客戶 j的途中旅行時間，i,j=0,1,2,...,n；Tij為一個三角模糊數(Tij1,Tij2,Tij3)；

Si表示車輛在客戶i處的持續卸貨時間，i=1,2,...,n；Si為一個三角模糊數(Si1,Si2,Si3)；

fi為車輛抵達客戶i的時間，i=1,2,...,n；車輛到達客戶處時，不管是否處于時間窗口[ai,bi]內，均立即卸貨。

定義問題的變量為yik、xijk和tk，其含義分別如下：當客戶i由車輛k送貨時，yik取值為1，其他情況時yik取值為0；當車輛k由客戶i訪問客戶 j時，xijk取值為1，其他情況時xijk取值為0；tk表示車輛k從配送中心出發的時間。

由于qi均為三角模糊數，因此qiyik也為一個三角模

糊數。

車輛抵達客戶 j的時間 fj為：

該問題的模型如下：

該模型中：式（3）表示模型的目標函數；式（4）表示車輛能力約束，即每輛車所裝貨物的總重量小于其額定載重量的可信性大于給定的主觀決策值α；式（5）表示客戶的時間約束，車輛到達客戶的時間位于時間窗口內的可信性大于給定的主觀決策值β；式（6）表示每個客戶由且只由一輛車提供送貨服務；式（7）和式（8）表示yik和xijk之間的關系，且保證每個客戶只被訪問一次；式（9）為消去支路約束；式（10）表示每輛車從車場出發，送完貨后需要返回車場。

4 算法介紹

4.1 問題解的編碼及解碼

為方便粒子的更新操作，以實數形式進行編碼，編碼結構為(Ge1,Ge2,…,Gen,t1,t2,…,tm)，每個元素和客戶及車輛的對應關系見表2。

表2 問題解與客戶和車輛對應關系

其中：Ge1,Ge2,…,Gen分別對應客戶1,2,…,n，為區間(1,m+1)內的實數；t1,t2,…,tm依次代表第1,2,...,m輛車的出發時間，限定在區間(a0,b0)內，當某輛車不執行任務時，為了編碼和解碼的方便，也給其一個出發時間。

對于上述編碼方式，按照以下方法解碼：

Step1:對于Ge1,Ge2,…,Gen部分的元素，取其整數部分。根據整數部分進行分組，如整數部分為1的客戶均由第1輛車提供送貨服務，依次類推。

Step2:對同一個組內的客戶，再取其元素Gei中小數部分，按照從小到大排列，作為該車輛送貨的順序。

如一個由10個客戶、4輛車構成的問題，某編碼如下：

根據Step1，得到如下四組：（1.92，1.07），（2.94，2.82），（3.42，3.46），（4.80，4.56，4.04，4.28），然后根據Step2，可知第1輛車服務的客戶按順序為8、2，出發時間為8.02；第2輛車服務的客戶按順序為7、4，出發時間為8.17；第3輛車服務的客戶按順序為3、10，出發時間為8.40；第4輛車服務的客戶按順序為6、9、5、1，出發時間為8.00。將問題解所對應的車輛配送路線用一個矩陣code表示如下：

圖1 問題解對應的code矩陣

在該矩陣中，第k行中非0元素依次表示第k輛車服務的客戶編號及訪問的順序，0元素表示此處無安排。由此可知，上述編碼方式肯定能滿足問題的約束條件（6）-（10）。

4.2 模糊因素的處理

對問題解進行解碼后，可知每輛對應的客戶及送貨順序，車輛k所裝載貨物的總重量為qiyik，由于qi均為三角模糊數(qi1,qi2,qi3)，根據模糊理論，iyik也為三角模糊數，令：

同理，由于Si、Tij均為三角模糊數，tk為實數，根據模糊理論，則車輛抵達客戶 j的時間 fj也為三角模糊數。由式（2），當i=0且xijk=1時有：Cr{aj≤fj≤bj}的值即可根據表1得到。

4.3 問題解的修復

對本文所描述的問題解，在進行解碼后，可根據4.2部分判斷出該問題解是否滿足車輛能力約束（4）和客戶的時間約束（5），若不滿足，則表示該問題解為不可行解，需要按照如下思路進行修正：

（1）若車輛k不滿足能力約束，表明車輛k所在的子路徑內客戶數量過多，需要調整。將對應矩陣code中第k行（如圖2中第4輛車）最后的一個非0元素（假設為客戶i，如圖2中客戶1）用0代替，同時該客戶i加入到其他車輛（假設為車輛k'，圖2中第1輛車）所在的子路徑中（優先選擇已執行任務且服務客戶數最少的那輛車），且將該客戶i插入到新車輛k'當前子路徑最后一個客戶（假設為i'）之后，與此對應，該問題解中客戶i所對應的基因Gei用區間(Gei',k'+1)內的任意一個實數代替（Gei'

為客戶i'對應的基因），然后重新判斷每輛車是否滿足能力約束，若該方法在所有車輛上均嘗試過后還不滿足約束條件，則新開一輛車。

圖2 客戶在子線路間的調整

（2）若滿足車輛能力約束，但不滿足客戶的時間約束，則表明各子路徑客戶數量沒有問題，但是子路徑內客戶順序及車輛出發時間需要調整。由此，若客戶i不滿足時間約束，則根據以下情況進行分析：若客戶i位于子路徑內第1個位置，則說明車輛出發時間需要調整；否則，將客戶i依次與前面或后面的其他客戶（假設為客戶 j）進行位置交換（如圖3中客戶5和1交換），與此對應，將該問題解中客戶i所對應的基因Gei和客戶 j所對應的基因Gej進行交換。然后判斷是否滿足該約束，若客戶i與該子路徑內的其它所有客戶均交換完畢，仍然不能滿足約束，則對車輛出發時間進行變異，隨機生成一個新的出發時間tk，直至滿足約束條件。

圖3 客戶在子線路內的調整

4.4 改進的粒子群算法

設粒子群集合為pop，種群規模為popsize，粒子的狀態采用4.1所述的編碼結構 (Ge1,Ge2,…,Gen,t1,t2, …,tm)，粒子的速度向量具有和粒子狀態相同的維數，每個粒子的適應度為：

每個粒子 pop[p]（p=1,2,...,popsize）在迭代時，采用如下的規則進行更新：

式（16）和（17）中，popt[p]和popt+1[p]分別表示第 p個粒子 pop[p]在第t代和第t+1代的狀態，Vt[p]和Vt+1[p]分別表示粒子 pop[p]在第t代和第t+1代的速度，Pind_best[p]為 pop[p]經歷過的最優狀態，Pg_best表示粒子群經歷過的最優狀態。ω表示慣性權重，c1和c2分別為加速度常數，rand()為0到1之間的隨機數。

根據有關粒子群算法的研究文獻表明，慣性權重ω和加速度常數c1、c2對粒子群算法的尋優性能有著非常顯著的影響，其中慣性權重ω對算法的尋優性能影響最為顯著，ω越大，算法的全局尋優能力越強，局部尋優能力越弱；反之，則算法的局部尋優能力越強。通過調整ω的值，控制以前速度對當前速度的影響，在全局尋優和局部尋優之間取得相對的平衡。

采用兩種動態調整慣性權重ω的方法：

（1）線性權重調整法

式（18）中ωmax和ωmin分別表示最大慣性權重和最小慣性權重，max_iter為最大迭代次數，iter為當前迭代次數。

（2）自適應權重調整法。借鑒文獻[20]的方法，采用自適應慣性權重調整方案，即每個粒子根據其當前速度、當前位置與自身經歷過的最優位置的距離，以及與種群最優位置的距離三部分信息，動態調整其下一步的飛行速度。具體方法如下：

首先定義第p個粒子pop[p]與當前種群最優粒子Pg_best的距離為，第 p個粒子 pop[p]與自身經歷過的最優位置Pind_best[p]的距離為則對于任意粒子pop[p]，當其不處于種群最優位置和自身經歷過的最優位置上時，locp表示其位置比，見公式（19）：

則粒子pop[p]在第t+1代的慣性權重ωp可以表示為：

式（20）中ωinitial表示權重的初始值，一般設定為1。當粒子處于種群最優位置或自身經歷過的最優位置上時，其慣性權重保持不變，為上次移動時的慣性權重。

4.5 算法步驟

Step1：初始化粒子群規模 popsize、迭代次數max_iter、慣性權重ω、加速度常數c1和c2等參數。

Step2：令t=1，初始化粒子群pop的狀態popt[p]和速度Vt[p]，并令Pind_best[p]=popt[p]，（p=1,2,...,popsize）。將處于最優狀態的粒子popt[p]賦給Pg_best。

Step3：計算每個粒子popt[p]的適應度Fpopt[p]。

Step4：對每個粒子，若其適應度Fpopt[p]＞FPind_best[p]，則令 Pind_best[p]=popt[p] ；若 Fpopt[p]＞FPg_best，則 令 Pg_best= popt[p]。

Step5：令t=t+1，若t＞max_iter，則終止迭代，否則，根據公式（16）—（20）更新每個粒子的狀態。

Step6：進行元素取值范圍判斷。若更新后的粒子元素Ge1,Ge2,…,Gen部分取值超過區間(1,m+1)，則隨機產生一個位于區間(1,m+1)的實數，取代該元素。若t1,t2,…,tm部分的元素超過區間(a0,b0)，則隨機產生一個位于(a0,b0)的實數，取代該元素。

Step7：進行約束條件判斷。若滿足約束條件（4）和（5），則該粒子可行，返回Step3；否則，按照4.3所述對粒子進行修正，并返回Step3。

5 仿真實例

本文以一個含20個客戶、4輛車的模糊VRP問題為例進行仿真，部分數據如車輛運載能力、各節點之間的距離和旅行時間、各客戶的時間窗口來源于文獻[19]，部分數據如模糊需求、模糊卸貨時間基于假設，見表3，置信水平α和β均為0.6。（1）實驗結果。利用Matlab進行仿真實驗，仿真參數如下：粒子群規模 popsize=100、迭代次數max_iter=1 000、加速度常數c1=1.5、c2=1.5。最大慣性權重ωmax=1、最小慣性權重ωmin=0.1。經過Matlab 7.0編程，慣性權重采用自適應權重調整法時得到問題的最優解為：

表3 各客戶的模糊需求、模糊卸貨時間(單位：min)

該編碼進行解碼，得到其對應的配送方案為：

車輛1的行駛路線為：0-7-12-5-15-14-6-13-0，服務的客戶數量為7，其出發時間為8.332 6；車輛2的行駛路線為：0-3-9-18-1-11-16-2-0，服務的客戶數量為7，其出發時間為8.395 2；車輛3不執行任務；車輛4的行駛路線為：0-4-17-19-20-10-8-0，服務的客戶數量為6，其出發時間為8.248 3。該配送方案對應的總行駛里程為740。

圖4為粒子群算法1 000次迭代后總行駛里程的迭代示意圖。

圖4 總行駛里程迭代結果

（2）對比分析。將本文所提的算法與傳統的遺傳算法、模擬退火算法進行對比，在種群規模均為100，迭代次數均為1 000的前提下，平均運行10次，統計各種算法運行10次所取得的最優值、平均值、均方差以及獲取最優解時的平均迭代次數，見表4。

表4 本文算法與遺傳算法、模擬退火算法的比較

表4中算法1為慣性權重采用線性權重調整的粒子群算法，算法2為慣性權重采用自適應權重調整的粒子群算法。從表4可以看出，本文所提算法1略優于遺傳算法，但遜于模擬退火算法，主要原因是由于慣性權重采用線性調整，且是針對整個粒子群的，即在一次迭代中，每個粒子都使用相同的慣性權重，此方法還不能較好地反映算法的動態性能。算法2的結果最優，這得益于該算法采用慣性權重自適應調節的策略，每個粒子在選擇下一時刻的飛行速度時，根據其當前速度和位置、所在環境等因素自動調節，且每個粒子的慣性權重不一樣，這能更好地保證種群的多樣化，能在更大范圍內搜索到最優解。

6 結束語

本文考慮了一類車輛旅行時間、卸貨時間和客戶需求量均為模糊變量的VRP問題，在該問題中假設車輛到達客戶處時，不管到達時間是否處于時間窗口內，均立即卸貨，基于此假設，建立了基于可信性測度的模糊機會約束規劃模型，并用改進的粒子群算法進行優化。最后給出了仿真實驗，通過仿真實驗證明，該算法對于解決此類模糊VRP問題是行之有效的。

[1]Dantzing G,Ramser J.The truck dispatching problem[J].Management Science,1959,10(6):80-91.

[2]Teodorovic D,et al.The fuzzy set theory approach to the vehicle routing problem when demand at nodes is uncertain[J]. Fuzzy Sets and Systems,1996,82:307-317.

[3]祝崇雋,劉民,吳澄,等.針對模糊需求的VRP的兩種2-OPT算法[J].電子學報,2001,29(8):1-2.

[4]張建勇,郭耀煌,李軍.模糊需求信息條件下的車輛路徑問題研究[J].系統工程學報,2004,19(1):74-78.

[5]張建勇,李軍.模糊車輛路徑問題的一種混合遺傳算法[J].管理工程學報,2005,19(2):23-26.

[6]張建勇,李軍.模糊需求VRP的一種Sweeping啟發式算法[J].中國管理科學,2007,15(10):71-75.

[7]曹二保,賴明勇,張漢江.模糊需求車輛路徑問題研究[J].系統工程,2007,25(11):14-18.

[8]曹二保,賴明勇,李董輝.基于混合差分進化算法的模糊需求車輛路徑問題[J].系統工程理論與實踐,2009,29(2):106-113. [9]戎麗霞.模糊需求條件下車輛路徑問題的模糊模擬[J].計算機工程與應用,2010,46(18):209-210.

[10]吳天羿,許繼恒.基于混合遺傳算法的模糊需求車輛路徑問題[J].解放軍理工大學學報(自然科學版),2014,15(5):475-482.

[11]Lian Xue.Fuzzy Simulation on the Vehicle Routing Problem[J]. Information Technology Journal,2013,12(21):6 098-6 102.

[12]R J Kuo,Ferani E,Zulvia,Kadarsah Suryadi.Hybrid particle swarm optimization with genetic algorithm for solving capacitated vehicle routing problem with fuzzy demand A case study on garbage collection system[J].Applied Mathematics and Computation,2012,219:2 574-2 588.

[13]Cao Erbao,Lai Ming yong.The open vehicle routing problem with fuzzy demands[J].Expert Systems with Application,2010, 37(3):2 405-2 411.

[14]Yang Peng,Ye-mei Qian.A particle swarm optimization to vehicle routing problem with fuzzy demands[J].Journal of Convergence Information Technology,2010,8(5).

[15]Zheng Y,Liu B.Fuzzy vehicle routing model with credibility measure and its hybrid intelligent algorithm[J].Applied Mathematics and Computation.2006,176:673-683.

[16]Ghannadpour,S F,Noori S,Tavakkoli-Moghaddam R.Multiobjective Dynamic Vehicle Routing Problem With Fuzzy Travel Times and Customers’Satisfaction in Supply Chain Management[J].IEEE Transactions on Engineering Management, 2013,60(4).

[17]Jianyong Zhang.A hybrid genetic algorithm to the vehicle routing problem with fuzzy cost coefficients[A].11th International Conference on Fuzzy Systems and Knowledge Discovery[C].2014 147-152.

[18]Seyed Farid Ghannadpour,Siamak Noori,Reza Tavakkoli-Moghaddam.Multiobjective dynamic vehicle routing problem with fuzzy travel times and customers’satisfaction in supply chain management[J].IEEE transactions on engineering management,2013,(4):777-790.

[19]劉寶碇，趙瑞清，王綱.不確定規劃及應用[M].北京:清華大學出版社.2003.

[20]吳斌.車輛路徑問題的粒子群算法研究與應用[D].杭州:浙江工業大學,2007.

Study on VRP with Fuzzy Time and Demand Based on Modified Particle Swarm A lgorithm

Zhu Hao
(Huzhou Vocational &Technical College,Huzhou 313000,China)

In this paper, in view of the vehicle routing problem where the vehicle traveling time, cargo unloading time and customer demand volume were all fuzzy, we built a fuzzy opportunity constraint programming model based on credibility measure, then used the modified particle swarm algorithm to optimize it, designed a special corrective operator for the infeasible solutions, and at the end, through a simulation example, proved the validity of this algorithm in the solution of similar fuzzy VRPs.

VRP; fuzzy traveling time; fuzzy demand volume; particle swarm algorithm

F224.0

A

1005-152X(2017)04-0084-06

2017-03-06

湖州市自然科學基金（2015YZ07）

朱顥（1980－），男，講師，碩士，研究方向：車輛路徑問題。

doi∶10.3969/j.issn.1005-152X.2017.04.020