混合量子粒子群算法求解車輛路徑問題

黃震

惠州學院計算機科學系，廣東惠州 516007

混合量子粒子群算法求解車輛路徑問題

黃震

惠州學院計算機科學系，廣東惠州 516007

1 引言

車輛路徑問題廣泛地應用于交通和物流領域，已經引起了國內外學者對該問題進行深入的研究，產生了許多種經典、智能的求解方法，其中粒子群算法在求解車輛路徑問題上也成為了研究熱點。針對粒子群算法容易陷入局部最優的缺點，很多學者利用改進的粒子群算法對車輛路徑問題進行求解，馬慧民等[1]提出一種引入模擬退火機制的并行粒子群算法對車輛路徑問題進行求解，該算法可以提高進化后期的收斂精度，具有良好的性能。陳嚴等[2]在基本粒子群算法的基礎上引入了雜交PSO模型和變異算子，并且運用罰函數法將約束優化問題轉化為無約束優化問題，同時采用實數編碼方案，將離散的車輛路徑問題轉化成準連續優化問題。張思亮等[3]提出一種粒子群算法和蛙跳算法的混合算法求解車輛路徑問題，采用粒子群算法產生階段最優解，利用蛙跳算法對階段最優解進一步優化，取得比較理想的效果。李婭等[4]提出一種改進的混沌粒子群優化算法求解車輛路徑問題，在基本混沌粒子群優化算法基礎上，引入邏輯斯特函數對慣性權重因子w進行非線性調整，提高了算法的尋優能力，有效避免了算法陷入局部最優并防止過早收斂。李德富等[5]提出了掃描粒子群算法，運用掃描算法對礦點進行掃描，生成初始可行解鏈，將其作為粒子的初始位置代入到粒子群中搜索，得到粒子種群歷史最優位置，將種群粒子最優位置逆轉錄生成對應的可行解鏈。

本文首先使用量子粒子群算法[6-7]求解車輛路徑問題，實驗結果表明該算法存在容易陷入局部最優的缺點，于是參考了文獻[8]提出的將粒子群算法和遺傳算法相結合的思想，在基于量子粒子群算法更新了粒子位置之后再進行交叉和變異操作，實驗結果表明改進后的算法不僅可以提高局部搜索能力，而且具有良好的全局尋優能力和較快的收斂速度。

2 車輛路徑問題的數學模型

車輛路徑問題（Vehicle Routing Problem，VRP）是由Dantzig和Ramser于1959年首先提出的[9]，基本車輛路徑問題的描述為某配送中心（編號為0）有K輛車，每輛車最大載重量為w，對N個客戶（編號為1，2，…，n）進行貨物配送，每輛車從配送中心出發給若干客戶送貨，最后回到配送中心，設客戶i對貨物的需求量為qi(i=1,2,…,n)，cij表示客戶之間的距離。

根據基本車輛路徑問題的描述，配送系統的變量和數學模型定義如下：

其中，式（1）、式（2）為變量的定義，式（3）是保證每輛車的運載能力約束，式（4）是保證每個用戶被服務，式（5）、式（6）保證每個用戶有且僅被一輛車訪問，式（7）是本配送系統的目標函數。

3 改進的量子粒子群算法求解車輛路徑問題

3.1 量子粒子群算法

量子粒子群算法（QPSO）是指具有量子行為的粒子群算法，根據文獻[10]的描述，算法中粒子的狀態由波函數ψ(x,t)決定，通過Monte Carlo方法模擬得出粒子位置更新方程如下：

式（8）中p由式（9）給出，式（9）中α1和α2為[0，1]上的均勻分布的隨機數，best_l為粒子在第t次迭代的局部最優值，best_g為粒子在第t次迭代的全局最優值；式（8）中β表示慣性權值，其值隨著迭代動態變化，一般按照式（10）求值，其中t表示當前迭代次數，tmax表示最大迭代次數；式（8）中mbest由式（11）給出，表示第t次迭代時每個粒子在局部搜索到的最優位置的平均值；式（8）中u指的是[0，1]上的均勻分布的隨機數，在迭代過程中當u＞0.5時β前的符號取負號，否則取正號。

量子粒子群算法對比粒子群算法具有參數少、收斂速度快的優點，但是由于只有一個參數β來控制粒子的更新，β是隨著迭代次數的增加而線性減少的，而解決實際問題時搜索過程往往是比較復雜的、非線性的，所以在實際的優化搜索過程中容易陷入局部最優，出現早熟收斂現象。

3.2 改進算法求解車輛路徑問題

針對QPSO可能出現早熟收斂現象，本文對QPSO進行了改進，借鑒了遺傳算法的交叉和變異操作。改進的算法流程如圖1所示。

圖1 改進算法流程圖

3.2.1 初始化粒子群

利用粒子群算法求解實際問題時，首先需要解決的是粒子的編碼問題，本文參考了文獻[11]，采用整數編碼，具體方式如下：

（1）采用整數i表示配送中心和客戶，其中0表示配送中心（有K輛車），1，2，…，n表示客戶。

（2）每個粒子由一個n維整型向量[a1,a2,…,an]表示，ai∈[1,n]，每個ai對應一個客戶號。

（3）每個粒子的解路徑由一個n+K+1維的整型向量[b1,b2,…,b(n+K+1)]表示，bj∈[0,n]，每個bj代表配送中心或客戶，粒子的解路徑按照如下方法求解：

①定義變量W，初始值為0，解路徑的第一維b1賦值為0（表示配送中心）。

②先將粒子向量的第一維a1對應客戶的需求量與變量W相加，如果W沒超過車輛限重則將a1加入到解向量中，即將a1賦值給解路徑向量的第二維b2，按同樣的方法繼續計算后面的每一維，若W不超重則將粒子的當前維ai加入到解路徑向量中，若W超重則結束，并且不把粒子的當前維加入到解路徑向量，這樣之前加入到解路徑向量中的客戶就構成了子路徑1。

③在解路徑向量中子路徑1的后面一維分量賦值為0（表示配送中心），然后按照步驟②的方法遍歷粒子向量剩下的維分量，可以求出所有子路徑。

例如某配送中心有2輛車，每輛車限重8噸，為8個客戶送貨，客戶的需求量分別是：1，2，1，2，1，4，2，2，設向量[4 2 8 5 3 1 6 7]為一個粒子，按照上述方法可以求出其解路徑為[0 4 2 8 5 0 3 1 6 7 0]，對應的子路徑為：0-4-2-8-5-0和0-3-1-6-7-0，每個子路徑對應一輛車。

按照上述的粒子編碼方式，本文的初始化粒子群的步驟如下：

（1）隨機產生1個粒子，計算其解路徑，如果解路徑非法則通過3.2.5節的方法進行調整，如果調整不成功則重新產生一個粒子，按照這種方法產生40個粒子。

（2）計算40個粒子的適應值，適應值是指解路徑中各點之間的距離之和。

3.2.2 更新粒子位置

本文采用Matlab編寫代碼，根據公式（8）對粒子位置更新，實現步驟如下：（1）計算每次迭代所有粒子局部最優的平均值mbest。（2）使用unifrnd（0，1）產生2個隨機數α1和α2，根據公式（9）計算p。

（3）根據公式（10）計算慣性權值β，β的值隨著迭代次數t增加由1.0減至0.5。

（4）使用unifrnd（0，1）產生隨機數u，根據u的值來確定公式（8）的正負號。

（5）計算的結果會出現小數，本算法采用的是整數編碼，所以要對結果進行規格化，才能得到合法的粒子，規格化方法如下：

①將更新后的粒子向量的每一維排序。

②將每一維分量的排名賦值給粒子向量。

例如粒子[8 2 7 4 3 6 5 1]按照上述步驟更新后得到向量[36.66 38.40 38.47 34.93 35.63 37.97 37.96 38.46]，規格化后的粒子向量為[3 6 8 1 2 5 4 7]。

3.2.3 交叉操作

本文加入了遺傳算法中的交叉操作，交叉是指將兩個父代個體的部分基因加以替換重組而生成新個體的操作，是產生新個體的主要方法，決定了遺傳算法的全局搜索能力，在遺傳算法中起關鍵作用[12]，本文采用了算術交叉算子，具體操作步驟如下：

（1）首先選擇進行交叉的兩個父代個體，本文選擇當前局部最優的個體作為父代1，另外再選擇一個父代2即可，選擇的主要原則[13]是要有一定差異的兩個個體，這樣利于后代性狀進化，可以在選擇前先設定某個閾值Y，嘗試在當前所有粒子中隨機選擇一個作為父代2，將兩個父代的適應值S1和S2代入公式（12）計算出d，當d大于給定閾值時進行交叉，否則重新選擇父代2，公式（12）中的Smax和Smin分別是當前迭代次數的最大適應值和最小適應值：

（2）在父代1中隨機產生2個不同的交叉位作為交叉區域。

（3）將父代2中與父代1交叉區域中相同的客戶點逐一刪除，每刪除一個客戶點的同時將后續客戶點全部前移。

（4）將父代1交叉區域中的客戶點插入到父代2的末尾，構成子代粒子。

（5）計算交叉后粒子的適應值，如果更優則保留子代粒子。

例如，父代1為粒子[8 7 4 2 6 5 3 1]，父代2為粒子[7 8 1 3 6 2 4 5]，隨機產生2個交叉位分別為2和5，取出父代1的第2至第5位[7 4 2 6]作為交叉區域，將父代2中與交叉區域相同的客戶點刪除并將交叉區域插入到末尾，得到子代粒子為[8 1 3 5 7 4 2 6]。

3.2.4 變異操作

變異操作是指將個體編碼中的某個基因值用其他等位基因來替換，從而形成一個新的個體，它是產生新個體的輔助方法，可以改善遺傳算法的局部搜索能力[12]。本文采用的是不同子路徑間單點變異，具體方法是在粒子解路徑的2個子路徑上分別產生1個變異位，嘗試將兩者位置交換，如果交換后適應值更優則保留變異后的粒子，否則不交換。

例如粒子[4 6 2 1 3 5 8 7]對應的解路徑為[0 4 6 2 0 1 3 5 8 7 0]，對應有2個子路徑：0-4-6-2-0和0-1-3-5-8-7-0，如圖2所示。

圖2 變異前的路徑圖

假設在子路徑1中產生變異位為7號客戶，在子路徑2產生變異位為2號客戶，將兩者位置交換完成變異操作，變異后的粒子為[4 6 7 1 3 5 8 2]，變異后的路徑如圖3所示。

圖3 變異后的路徑圖

3.2.5 非法解的調整

初始化粒子群或者在算法進行過程中產生的粒子可能會出現非法的解路徑，例如存在一個粒子[2 8 5 3 6 7 1 4]，按照3.2.1節的方法可以求出其解路徑為[0 2 8 5 3 0 6 7 1 0 4]，對應的子路徑為：0-2-8-5-3-0、0-6-7-1-0和0-4-0，需要3輛車才能完成配送任務，而配送中心只有2輛車，明顯這是個非法的解路徑。本文參考了文獻[14]的方法對非法解進行調整，具體步驟如下：

（1）將最后兩條子路徑合并，合并后上述粒子的子路徑為：0-2-8-5-3-0、0-6-7-1-4-0，這樣就轉化為解決最后一條子路徑超重的問題。

（2）針對最后一條子路徑，先取出第一個客戶號，嘗試放入之前的子路徑中是否超重，如果不超重則將第一個客戶加入到之前的子路徑中，然后再判斷最后一條子路徑是否超重，如果不超重則調整結束，得到合法解，否則取后續客戶號重復之前的操作。

（3）如果最后一條子路徑的每一個客戶號按照步驟（2）操作都不能得到合法解，則取第一個客戶號嘗試與之前子路徑的每一個客戶號交換位置，如果交換后之前的子路徑不超重且最后一條子路徑也不超重則進行交換，此時調整結束得到合法解，否則取后續客戶號重復之前的操作。

（4）如果上述步驟都不能得到合法解，則舍棄該非法粒子。

按照上述方法調整非法解路徑[0 2 8 5 3 0 6 7 1 0 4]可以得到合法解路徑[0 7 2 8 5 3 0 6 1 4 0]。

4 實驗仿真結果與分析

4.1 實驗1

實驗1的數據采用文獻[4]中的數據，即有1個配送中心配有2輛車，每輛車限載重8噸，需要服務8個客戶，具體數據如表1所示，表1中第1行和第1列中的0表示配送中心，1～8表示各客戶號，最后一行表示各客戶的需求量（單位為t），表1中的其余數據表示配送中心與各客戶之間的距離（單位為km）。

本文使用Matlab7.0進行編程，分別利用QPSO和本文算法對實驗1的數據進行仿真，兩種算法的粒子數設置為40，迭代次數設置為50，本文算法的交叉概率為0.55，變異概率為0.02，對兩種算法的仿真程序分別運行20次，得到運送貨物的總運輸距離，結果如表2所示。為了說明本文算法的有效性，表2中加入了文獻[4]的實驗結果。

表1 各客戶間的距離及各客戶的需求量

表2 實驗1結果對比1）

已知實驗1的理想解為67.5，由表2的結果可知，QPSO僅獲得5次理想解，平均解為69.3；文獻[4]的算法獲得14次理想解，平均解為68.37；本文算法20次的運行結果都獲得了理想解67.5，明顯優于QPSO，也優于文獻[4]的算法，實驗結果說明本文算法可以很好地解決小規模的車輛路徑問題。

4.2 實驗2

實驗2使用的數據是中等規模實例VRPNC1，VRPNC1是通用的VRP測試數據[15]，VRPNC1中有1個配送中心，配5輛車，每輛車限量160，為50個客戶運送貨物，已知VRPNC1實例的理想解為524.61。分別用QPSO、遺傳算法（GA）和本文算法進行仿真實驗，設置粒子數為40，迭代次數為400，本文算法的交叉概率為0.55，變異概率為0.02，閾值為0.2。三種算法各運行20次，計算出運送貨物的總運輸距離，運行結果如表3所示。

表3 實驗2結果對比

由表3可知，QPSO和GA算法在20次運行中得到的解與VRPNC1實例的理想解的誤差率都比較大。本文算法在運行過程中獲得了VRPNC1實例的理想解524.61，最差解的誤差率為4.1%，平均解的誤差率僅為2.5%，取得了比較好的運行結果。

圖4 三種算法的迭代過程

三種算法得到的最好解的迭代過程如圖4所示。

由圖4可知，本文算法的最終結果明顯優于QPSO和GA算法，收斂性也更好，QPSO的收斂性較好，但是容易陷入局部最優，本文算法很好地解決了這個問題。

由于本文算法加入了交叉和變異操作以及每次產生新的粒子都需要檢測是否為非法解，需要對非法解進行調整，所以運行時間較長。在迭代次數同為400次，運行20次的情況下，QPSO的平均運行時間是8.8 s，GA的平均運行時間是8.3 s，本文算法的平均時間為23.2 s，這是本文算法需要改進的地方。

5 結束語

本文將量子粒子群算法和遺傳算法相結合對車輛路徑問題進行求解，給出了具體的粒子位置更新方法、交叉和變異的方法以及對非法粒子的調整方法。分別對8個客戶的小規模實例和50個客戶的中等規模實例進行仿真，實驗結果表明小規模實例可以迅速得到理想解，中等規模實例可以得到理想解，而且平均解與理想解的誤差率也比較小，說明本文算法可以有效求解車輛路徑問題，但是本文算法的運行時間較長，需要在這方面進行改進。

[1]馬慧民，吳勇，葉春明.車輛路徑問題的并行粒子群算法研究[J].上海理工大學學報，2007，29（5）：435-439.

[2]陳嚴，劉利民.改進型PSO算法在VRP中的應用[J].計算機工程，2011，37（1）：170-172.

[3]張思亮，葛洪偉.粒子群和蛙跳的混合算法求解車輛路徑問題[J].計算機工程與應用，2011，47（21）：246-248.

[4]李婭，李丹，王東，等.改進的混沌粒子群算法求解車輛路徑問題[J].計算機應用研究，2011，28（11）：4107-4110.

[5]李德富，郭海湘，劉龍輝，等.改進型粒子群優化算法求解車輛徑優化問題[J].計算機工程與應用，2012，48（20）：216-223.

[6]Sun Jun，Feng Bin，Xu Wenbo.Particle swarm optimization with particles having quantum behavior[C]//Proceedings of the 2004 Congress on Evolutionary Computation.Portland，OR：IEEE Press，2004：325-331.

[7]dos Santos Coelho L.A quantum particle swarm optimizer with chaotic mutation operator[J].Chaos，Soliton and Fractals，2008，37：1409-1418.

[8]黃為勇.一種采用完全Logistic混沌的PSO-GA優化方法[J].計算機應用研究，2012，29（9）：3236-3239.

[9]Dantzig G B，Ramser J H.The truck dispatching problem[J]. Management Science，1959，6（1）：80-91.

[10]靳雁霞，韓燮，周漢昌.具有量子行為的粒子群優化算法的改進[J].計算機工程與應用，2009，45（35）：41-43.

[11]楊虎林.改進粒子群優化算法求解車輛路徑問題的研究[D].南寧：廣西師范學院，2012.

[12]葛繼科，邱玉輝，吳春明，等.遺傳算法研究綜述[J].計算機應用研究，2008，25（10）：2911-2916.

[13]周艷聰，孫曉晨，余偉翔.基于改進遺傳算法的物流配送路徑優化研究[J].計算機工程與科學，2012，34（10）：118-122.

[14]熊寧.基于粒子群優化算法求解車輛調度問題[D].廣州：華南理工大學，2012.

[15]戴樹貴，姜昌華，潘蔭榮，等.求解車輛路徑安排問題的混合遺傳算法[J].計算機工程與應用，2007，43（21）：225-228.

HUANG Zhen

Department of Computer Science,Huizhou University,Huizhou,Guangdong 516007,China

Quantum Particles Swarm Optimization（QPSO）algorithm partly solves the shortcoming such that Particle Swarm Optimization algorithm rate of convergence is not fast enough,while in solving the Vehicle Routing Problem（VRP）.But there is still disadvantage.QPSO falls into local optimum easily.This paper proposes a hybrid Quantum Particle Swarm Optimization algorithm to solve the vehicle routing problem.It uses the QPSO to update particles of initial particle swarm;the crossover operating to particles can improve the global search ability;the mutation operating to particles can improve the local search ability. Applying Matlab as tool for simulation experiment,the experimental result shows that the improved algorithm had good performance to deal with VRP.It can avoid falling into local optimum,and it is better than QPSO and genetic algorithm.

Particles Swarm Optimization（PSO）algorithm;Quantum Particles Swarm Optimization（QPSO）algorithm;crossover;mutation;vehicle routing problem

量子粒子群算法在求解車輛路徑問題時一定程度上解決了基本粒子群算法收斂速度不夠快的缺點，但是量子粒子群算法仍然存在容易陷入局部最優的缺點。利用混合量子粒子群算法對車輛路徑問題進行求解，運用量子粒子群算法對初始粒子群的粒子進行更新，對粒子進行交叉操作，可以提高算法的全局搜索能力，進行變異操作，可以改善算法的局部搜索能力。以Matlab為工具進行仿真實驗，實驗結果表明改進后的算法在求解車輛路徑問題時具有良好的性能，可以避免陷入局部最優，對比量子粒子群算法和遺傳算法具有一定的優勢。

粒子群算法；量子粒子群算法；交叉；變異；車輛路徑問題

A

TP301.6

10.3778/j.issn.1002-8331.1306-0353

HUANG Zhen.Hybrid quantum Particle Swarm Optimization algorithm for vehicle routing problem.Computer Engineering and Applications,2013,49（24）：219-223.

廣東省惠州市科技計劃項目（No.2012-10）；廣東省惠州學院自然科學研究項目（No.2012QN11）。

黃震（1980—），男，講師，主要研究方向：智能算法。E-mail：195146501@qq.com

2013-07-01

2013-08-19

1002-8331（2013）24-0219-05

CNKI出版日期：2013-10-11http://www.cnki.net/kcms/detail/11.2127.TP.20131011.1653.008.html