求解CVRP的改進量子遺傳算法研究

曹云+向鳳紅+毛劍琳

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

關鍵詞：車輛路徑問題；量子遺傳算法；量子旋轉門；量子變異

DOIDOI：10.11907/rjdk.171907

中圖分類號：TP312

文獻標識碼：A 文章編號：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年提出，廣泛應用于物流配送、交通線路規劃和快遞收發系統。傳統精確算法僅適用于小規模問題，而啟發式算法難以獲得精確解，因此，智能算法受到人們青睞。趙燕偉等[2]提出了一種雙種群遺傳算法用來求解CVRP，根據兩個種群各自特點進行不同進化，同時交換種群間的優質個體信息，使算法避免陷入局部最優；Wang等[3]提出了一種混合遺傳算法來求解CVRP，利用響應面法對變異、交叉概率進行優化操作，同時將改進的掃描法插入到遺傳算法以增加種群的多樣性，使算法的搜索能力得以提高；Dorronsoro等[4]提出了一種元胞遺傳混合算法，全局搜索用遺傳算法，局部捜索采用交換操作結合2-opt法提高算法搜索性能；蔡蓓蓓等[5]提出一種混合量子遺傳算法求解CVRP，在傳統的量子遺傳算法基礎上加入免疫算子，算法的局部捜索能力明顯改善；WANG等[6]提出一種元胞蟻群算法，實驗證明該算法具有較好的捜索能力。

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

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

1 CVRP及數學模型

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

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

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

2.2.5 客戶節點重置和2-opt法

為增強算法的局部開發能力，改進的QGA引入客戶點重置結合2-opt法局部搜索。

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

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

3 算法性能測試

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

本文將改進的量子遺傳算法（KQGA）與GA算法和HGA算法進行比較，所得結果如表2所示。從表2可以看出，對于同樣的數據，3種算法在同樣運行10次時改進量子遺傳算法要優于其它兩種算法。圖4為3種算法的適應度曲線。因為目標函數是求運輸成本，所以適應度越小越好。從圖中可以看出，本文提出的算法適應度最小。

4 結語

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

參考文獻：

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

[2] 趙燕偉，吳斌，蔣麗，等.車輛路徑問題的雙種群遺傳算法求解方法[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中的應用[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] 郎茂祥，胡思繼.用混合遺傳算法求解物流配送路徑優化問題的研究[J].中國管理科學，2002，10（5）：51-56.

（責任編輯：杜能鋼）