曹云+向鳳紅+毛劍琳

摘要：車輛路徑問題屬于離散NP-hard組合優(yōu)化問題，傳統(tǒng)的量子遺傳算法存在儲(chǔ)存量大和易陷入局部最優(yōu)解等問題。提出一種新的量子遺傳算法用于最小化運(yùn)輸成本。設(shè)計(jì)一種將量子比特編碼轉(zhuǎn)換為實(shí)數(shù)的編碼方法，每條染色體代表一種行車路線方案，利用改進(jìn)的旋轉(zhuǎn)門對種群進(jìn)行更新操作，采用動(dòng)態(tài)調(diào)整旋轉(zhuǎn)角機(jī)制對量子步長實(shí)現(xiàn)自適應(yīng)搜索，擴(kuò)大全局搜索范圍；引入一種變異操作，用于保持算法的種群多樣性，從而提高算法的全局搜索寬度；采用客戶節(jié)點(diǎn)重置和2-opt法對線路進(jìn)行再優(yōu)化，增強(qiáng)算法的局部搜索能力。仿真實(shí)驗(yàn)和算法比較，驗(yàn)證了該算法的優(yōu)越性和有效性。

關(guān)鍵詞：車輛路徑問題；量子遺傳算法；量子旋轉(zhuǎn)門；量子變異

DOIDOI：10.11907/rjdk.171907

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2017）012-0060-04

Abstract：The vehicle routing problem is the NP-Hard combinatorial optimization discrete problem， The traditional quantum genetic algorithm has many problems such as large storage capacity and easy to fall into local optimal solution， so in this paper， a new quantum genetic algorithm is proposed to minimize transportation cost. This paper designs a coding method to transform the common coding into quantum bits，each chromosome represents a routing scheme，the update operation by using the improved rotating door population，adaptive search of quantum step size by dynamic adjustment of rotation angle mechanism， improve global search local. A mutation operation is introduced to maintain the population diversity of the algorithm， so as to improve the global search width of the algorithm. Finally， the customer node reset and the 2-opt method are used to optimize the circuit to enhance the local search capability of the algorithm. The advantages and effectiveness of the algorithm are verified by experimental simulation and algorithm comparison.

Key Words：vehicle routing problem； quantum genetic algorithm； quantum rotating gate； quantum mutation

0 引言

車輛路徑問題（Vehicle Routing Problem， VRP）是典型的NP-hard問題，由Dantzing和Ramser [1]于1959年提出，廣泛應(yīng)用于物流配送、交通線路規(guī)劃和快遞收發(fā)系統(tǒng)。傳統(tǒng)精確算法僅適用于小規(guī)模問題，而啟發(fā)式算法難以獲得精確解，因此，智能算法受到人們青睞。趙燕偉等[2]提出了一種雙種群遺傳算法用來求解CVRP，根據(jù)兩個(gè)種群各自特點(diǎn)進(jìn)行不同進(jìn)化，同時(shí)交換種群間的優(yōu)質(zhì)個(gè)體信息，使算法避免陷入局部最優(yōu)；Wang等[3]提出了一種混合遺傳算法來求解CVRP，利用響應(yīng)面法對變異、交叉概率進(jìn)行優(yōu)化操作，同時(shí)將改進(jìn)的掃描法插入到遺傳算法以增加種群的多樣性，使算法的搜索能力得以提高；Dorronsoro等[4]提出了一種元胞遺傳混合算法，全局搜索用遺傳算法，局部捜索采用交換操作結(jié)合2-opt法提高算法搜索性能；蔡蓓蓓等[5]提出一種混合量子遺傳算法求解CVRP，在傳統(tǒng)的量子遺傳算法基礎(chǔ)上加入免疫算子，算法的局部捜索能力明顯改善；WANG等[6]提出一種元胞蟻群算法，實(shí)驗(yàn)證明該算法具有較好的捜索能力。

量子遺傳算法（QGA）是由A Narayannan和Kuk-Hylun Han[7]等首先提出的，是一種受到量子計(jì)算啟發(fā)，并成功借鑒量子計(jì)算中的部分概念和理論形成的概率遺傳算法。它的優(yōu)點(diǎn)是豐富的種群多樣性以及全局尋優(yōu)能力，為求解車輛調(diào)度問題提供了新的思路。QGA的染色體用量子位表示，通過量子門更新完成進(jìn)化搜索。

作為VRP最基本的約束模型，CVRP在求解方面效果不是很理想。本文將量子和遺傳算法結(jié)合，針對問題本身特點(diǎn)對算法作了進(jìn)一步改進(jìn)。采用客戶與虛擬配送中心共同排列的編碼方式表示客戶位置，并利用改進(jìn)的旋轉(zhuǎn)門對種群進(jìn)行更新操作，采用動(dòng)態(tài)的調(diào)整旋轉(zhuǎn)角機(jī)制對量子步長實(shí)現(xiàn)自適應(yīng)搜索，引入量子變異從而防止算法的早熟問題。仿真結(jié)果表明，改進(jìn)的QEA算法比文獻(xiàn)[8]中的混合遺傳算法尋優(yōu)能力更強(qiáng)。

1 CVRP及數(shù)學(xué)模型

1.1 帶容量的車輛路徑問題描述

帶容量約束的車輛路徑問題描述為：有一個(gè)車場，共有K輛車，每輛車的最大載重為Q，這些車輛為L個(gè)客戶服務(wù)，客戶i的需求為qi，每個(gè)客戶可由任一輛車進(jìn)行服務(wù)，但只能被一輛車服務(wù)一次，每輛車服務(wù)完后必須返回原車場。其目標(biāo)是找到一個(gè)合適的車輛調(diào)度方案，在滿足客戶需求的同時(shí)使車輛的運(yùn)輸成本最低。

1.2 帶容量的車輛路徑問題模型

2.2.5 客戶節(jié)點(diǎn)重置和2-opt法

為增強(qiáng)算法的局部開發(fā)能力，改進(jìn)的QGA引入客戶點(diǎn)重置結(jié)合2-opt法局部搜索。

客戶節(jié)點(diǎn)重置是將一個(gè)客戶節(jié)點(diǎn)從一條線路移到另一條線路。如圖2所示，節(jié)點(diǎn)i距離節(jié)點(diǎn)j是最短的，則將節(jié)點(diǎn)i重置到一個(gè)線路，與j相鄰。重置時(shí)需考慮以下情況：i重置到線路r1，i在j之前或之后；j重置到線路ri，i在j之前或之后。選擇滿足車輛的容量限制且路程最短的一種重置。

2-opt法是針對一條線路的兩個(gè)客戶進(jìn)行交換，如圖3所示。將（i，j），（i+1，j+1）替換原來的（i，i+1），（j，j+1）。若交換后的路線長度變短則采用此算法，并將采用此算法形成的新路線作為最優(yōu)解，否則將原來的解定位為最優(yōu)解。

3 算法性能測試

在CPU為E5800 3.20GHz，內(nèi)存為2.96GB，操作系統(tǒng)為Windows 10的計(jì)算機(jī)上，采用文獻(xiàn)[8]中的算例與之對比，對算法進(jìn)行驗(yàn)證。配送中心共有5輛貨車，貨車的最大載重量均為8t，最大行駛距離均為50km，要求向20個(gè)客戶送貨，車場（即配送中心）坐標(biāo)為（14.5km，13.0km），客戶的位置坐標(biāo)和需求量如表1所示。

本文將改進(jìn)的量子遺傳算法（KQGA）與GA算法和HGA算法進(jìn)行比較，所得結(jié)果如表2所示。從表2可以看出，對于同樣的數(shù)據(jù)，3種算法在同樣運(yùn)行10次時(shí)改進(jìn)量子遺傳算法要優(yōu)于其它兩種算法。圖4為3種算法的適應(yīng)度曲線。因?yàn)槟繕?biāo)函數(shù)是求運(yùn)輸成本，所以適應(yīng)度越小越好。從圖中可以看出，本文提出的算法適應(yīng)度最小。

4 結(jié)語

本文針對傳統(tǒng)的量子遺傳算法存儲(chǔ)量大且易陷入局部最優(yōu)等問題，提出了一種改進(jìn)的量子遺傳算法。采用動(dòng)態(tài)調(diào)整旋轉(zhuǎn)角機(jī)制對量子步長實(shí)現(xiàn)自適應(yīng)搜索，從而加快了算法收斂速度，提高了搜索深度。引入量子自適應(yīng)變異操作防止了早熟問題。局部搜索采用客戶節(jié)點(diǎn)重置和2-opt法結(jié)合對線路進(jìn)行優(yōu)化，使解的質(zhì)量明顯提高。通過與傳統(tǒng)的GA和HGA對比，證明了該算法具有較強(qiáng)的尋優(yōu)能力。目前，KQGA只是針對靜態(tài)的帶容量車輛調(diào)度問題進(jìn)行研究，今后將對動(dòng)態(tài)車輛調(diào)度進(jìn)行研究，并驗(yàn)證其有效性。

參考文獻(xiàn)：

[1] DANTZIGC RAMSERJ.The truck dispatching problem[J].Management，Science，1959（6）：80-91.

[2] 趙燕偉，吳斌，蔣麗，等.車輛路徑問題的雙種群遺傳算法求解方法[J].計(jì)算機(jī)集成制造，2004，10（3）：303-306.

[3] WANG C H， LU J Z. A hybrid genetic algorithm that optimizes capacitated vehicle routing problems[J].Expert Systems with Applications，2009，36（2）：2921-2936.

[4] DORRONSORO B，ARIAS D，LUNA F.A grid-based hybrid cellular genetic algorithm for very largr scale instances of the CVRP[C].High Performance Computing & Simulation Conference，2007：759-765.

[5] 蔡蓓蓓，張興華.混合量子遺傳算法及其在VRP中的應(yīng)用[J].計(jì)算化仿真，2010，27（7）：267-270.

[6] WANG Y.Solving the capacitated vehicle routing problem by cellular ant algortithm[EB/OL].http：//comnection.ebscohost.com/c/articles/74249351.

[7] HARYNANAN A，MOORE M.Quantum-inspired genetic algorithms[C].Proceeding of IEEE International ConferenceonEvolutionary Computation，Nagoya，Japan，1996：61-66.

[8] 郎茂祥，胡思繼.用混合遺傳算法求解物流配送路徑優(yōu)化問題的研究[J].中國管理科學(xué)，2002，10（5）：51-56.

（責(zé)任編輯：杜能鋼）