求解車輛路徑問題的量子差分進化算法

2

(1.浙江工業大學 特種裝備制造與先進加工技術教育部重點實驗室，浙江 杭州 310014；2.中國計量大學 現代科技學院，浙江 杭州 310018)

量子進化算法最早由Han等[1]在Narayanan等[2]的量子遺傳算法概念基礎上提出，用于求解組合優化問題。該算法將量子理論與進化計算相融合，用量子位編碼表示染色體，通過量子門旋轉實現進化操作，具有并行度高、全局搜索能力強和收斂速度快的特點，已被應用于多種類型的車輛路徑問題，如王萬良等[3]將其應用于求解車輛共享帶軟時間窗的動態需求VRP問題；李川[4]應用量子進化算法解決了隨機車輛路徑問題；趙燕偉等[5]應用其求解了多車型同時取送貨的低碳路徑問題，研究結果表明量子進化算法對VRP，TSP等問題具有良好的求解效果。近年來對車輛路徑問題的求解研究趨向于多種方法融合，如陳曉瞇[6]將禁忌搜索算法與交叉算子相結合求解動態車輛路徑問題；趙燕偉等[7]提出用超啟發式算法求解選址-路徑問題。與其他算法的融合也正成為量子進化算法研究的一個重要趨勢，量子差分算法由Wang等[8]提出將差分進化算法較強的局域搜索能力與量子進化算法的全局搜索能力相結合，實現更高效的搜索效果。張曉雷[9]將該算法應用于函數極值優化，多個案例的應用比較結果顯示算法的尋優能力得到明顯改進；常新功等[10]提出了分解的多目標量子差分算法，并將其應用于測試函數，驗證了算法在非凸函數收斂性及分布性方面的改善；陳曉峰等[11]提出了一種實數編碼的量子差分算法，將量子比特概率幅表示為染色體的實數編碼，并與差分算法相結合提高算法的性能，在對函數極值及TSP的測試中驗證了算法的有效性。

盡管量子差分進化算法在解決眾多的NP-hard問題時獲得了良好的效果，但這種算法應用于VRP的效果還有待于研究。筆者將量子差分進化算法應用于求解車輛路徑問題(CVRP)，根據VRP問題特征，基于差分進化策略設計了量子交叉和變異方法以控制種群的進化方向，同時設計動態量子旋轉門的量子進化算法進行變領域搜索，通過兩種方法的協同進化增強算法的全局搜索能力，典型算例及標準算例的仿真實驗結果驗證了算法的有效性及魯棒性。

1 模型構建

1.1 問題描述

CVRP可以描述為由一個配送中心為多個顧客服務，車輛從配送中心出發，配送完成后返回到出發的配送中心，問題的目標是獲得總距離最小的最佳配送方案。將顧客與配送中心組成的網絡圖設為G=(N，A),N=Nm∪Nc，Nm=0為配送中心集合，Nc=(1,2,…,c)為顧客點集合，A={(i,j)∶i,j∈N,i≠j}點i，j的弧集合，K=(1,2,…,k)為車輛集合，dij為i,j的距離，車輛的載重限制為QC，qi為i點需求。為了便于建模，對問題進行如下假設[4]：1) 車輛勻速行駛，路上無擁堵現象，路況平穩；2) 配送車輛數量不限，車輛類型只有一種；3) 客戶需求已知并確定，每個客戶必須且只能被服務一次。

1.2 模型建立

(1)

約束條件為

(2)

(3)

(4)

(5)

(6)

xijk∈{0,1} ?i,j∈N，k∈K

(7)

其中：式(1)表示距離最短的目標函數；式(2，3)保證每個顧客只能被服務一次；式(4)為顧客需求限制；式(5)消除顧客點間出現的子回路，式中S為非空顧客點集；式(6)保證每輛車配送完后回配送中心；式(7)表示變量的取值。

2 量子差分進化算法

2.1 量子編碼與解碼

量子差分進化算法(QDE)采用與量子進化算法相同的染色體表示形式，將量子比特Q-bit(又稱量子位)組成的串作為量子染色體，一個量子位|φ>可以處于|1>或者|0>狀態，也可以是兩種狀態的線性疊加，即可以將量子位表示為|φ>=α|0>+β|1>，α，β分別表示0>和1>的概率幅；|α|2表示量子位處于|0>的概率，|β|2表示量子位處于|1>的概率，α2+β2=1，通過量子門的驅動實現最優進化。

將α，β矩陣轉換成二進制矩陣G，即

(8)

式中r為均勻分布的隨機數0～1。

將G矩陣解碼成滿足車輛載重要求的顧客集，解碼過程為從G中隨機選擇第一個顧客i，若其滿足式(4)的載重要求，則將其放入該車顧客集中，針對所有未放入車中在待配送顧客，確定下一個配送顧客l，即

(9)

若l滿足式(4)載重要求，則將其放入該車中，將l移出待配送顧客集，否則計算其他未配送顧客與i的距離，按式(9)依次選擇，若沒有顧客能放入該車輛，則建立一個新的車輛群重復前面的過程，直到所有顧客都分配車輛，圖1為某一解碼后的結果，圖1表示15 個顧客的配送方案。由圖1可知：該方案需要兩輛車，第一輛車的配送順序為“配送中心0-6-2-9-4-11-13-配送中心”，第二輛車為“配送中心-5-1-3-7-8-10-12-14-15-配送中心”。

圖1 解碼結果示例
Fig.1 Example of a problem decoding

2.2 量子變異

(10)

式中：m1,m2,m3∈{1,2,…,Popsize},m1≠m2≠m3；F為收縮因子，其取值為[0,1]的值；rand為[0,1]間的隨機數；g+1為當前代數的下一代。

2.3 量子交叉

量子交叉的發生概率由交叉因子Cr值控制，對選定的父代個體進行交叉混合，以產生新的多樣性個體，即

(11)

2.4 量子更新

量子門旋轉是量子進化算法實現狀態轉移的主要方法，筆者設計動態量子旋轉門進行狀態的更新與轉移，即

(12)

由式(12)可知，旋轉角與當前代數的解及當前最優解有關，且隨著迭代次數的增加，旋轉角逐步減小，從而有利于在最優解附近進行局部搜索。

其中

(13)

(14)

2.5 量子選擇

對由量子交叉、變異及量子旋轉更新后的量子比特按照貪婪原則進行選擇，具體操作為

(15)

式中f為解碼后的適應度函數。由式(15)可知：若通過量子交叉、變異后解碼得到的解優于當前解時則將其量子比特由量子交叉、變異更新，否則將量子由量子旋轉門更新。

2.6 局部優化

筆者算法的局部優化采用2-Opt和Move方式。

1) 2-Opt：將線路中用(i，j)和(i+1，j+1)代替(i，i+1)和(j，j+1)，同時線路方向反轉，若交換后，線路距離減少，則交換，圖2是其示意圖。

圖2 2-Opt操作過程示意圖Fig.2 Representation of 2-Opt operator

2) Move：依次將同車輛中的顧客移動到該車其他位置，若其距離減少，則執行該操作。

2.7 量子差分進化算法的求解流程

量子差分進化算法流程如下。

Step1初始化令n=1,θ=θ0，α=αt，β=βt，生成初始量子比特種群Q(t)。

Step2按2.1節解碼生成初始路線。

Step3按2.6節的局部優化方法調整方案，若調整后解獲得改善，則替換原方案，否則不替換；按式(1)計算目標函數值，保留最優個體。

Step4判斷是否滿足終止條件，若滿足，則輸出最優解；若不滿足，則轉Step 5。

Step5按式(14)進行量子選擇，得到新的下一代量子比特種群Q(t+1)。

Step6t=t+1，轉Step 2繼續執行。

3 實驗及結果分析

3.1 參數設置

取收縮因子F=0.05，量子交叉Cr=0.5，Δθt=0.05π采用matlab2010b編程，計算機配置為Intel Core i7-3630QM 2.40 GHz，8 GB RAM，在Windows 7系統執行，以最大循環次數為結束條件。

3.2 實驗一

針對小規模的車輛路徑問題，選用文獻[12-14]的案例，針對8 個顧客，1 個配送中心，車輛限額為8 t，顧客之間的距離矩陣如表1所示。

表1 中心與顧客距離及需求情況Table 1 Distance from depot center to customers

設置與文獻[12-14]相同的種群數(種群規模=60)及最大進化代數(進化代數=50)，將筆者提出的量子差分進化算法計算結果與其他啟發式算法進行對比，結果如表2所示。由表2可知：在20 次的運算中量子差分進化算法以100%的次數獲得最優解，相對于其他3 種算法，筆者算法的搜索性能更具有優勢。

表2 量子差分算法與其他算法求解結果對比Table 2 Comparison for the performance of the proposed QDE algorithm

3.3 實驗二

為了進一步測試算法性能，將筆者算法與標準CVRP進行對比，數據來源于http://Branch and cut.org/vrp/data/，每個案例計算10 次，以最大循環次數為結束條件，設置種群數為200，最大循環次數為500。將筆者算法與近3 年SC-ESA[15]，CRO[16]和KmeansFnO[17]3 種新型算法最優解進行對比，比較結果如表3所示，表中第2列是標準算例結果，第3列是筆者算法的最優結果，4～6列為其他算法最優結果。

表3 QDE與其他3 種算法的標準算例結果對比Table 3 Comparison for the performance of the proposed QDE algorithm in benchmark

由表3可知：筆者算法在顧客數為19～22的P算例中均求得了與標準算例相同的解，說明筆者算法對小型規模算例的求解效果較好，相比較SC-ESA在同等問題中只有1 個解與標準算例相同，KmeansFnO有2 個解與標準算例結果相同，筆者算法對小型P問題算例的求解效果較好，在中型規模A算例中，QDE算法優于KmeansFnO但不及SC-ESA和CRO，對大型規模算例的求解效果不及其他3 種算法。

表4是量子差分進化算法、量子進化算法及差分進化算法的求解結果對比，表中3 種算法的種群均為200，最大循環次數均為500。

表4 量子差分進化算法與量子進化算法及差分進化算法結果比較Table 4 Comparison for the performance of the proposed QDE algorithm with QEA and DE

由表4可知：量子差分進化算法有56%(5/9)的算例最優值優于量子進化算法，有22%(2/9)的算例結果與量子進化算法相同，與差分進化算法相比，量子差分進化算法100%的結果優于差分進化算法，因此量子差分進化算法的求解效果整體優于量子進化算法及差分進化算法。

圖3是P-n20-k2求解迭代過程與量子進化算法及差分進化算法的比較，圖中實線為量子差分進化算法，虛線為量子進化算法，點線為差分進化算法。由圖3可知：進化前期，3 種算法均能實現快速優化，相對而言，差分進化算法在進化前期的進化速度最快，但隨著進化代數的增加，差分進化算法的搜索性能下降，最終的收斂解最差；量子進化算法的前期搜索效果較好，隨著迭代次數的增加，其進化速度變慢；而量子差分進化算法結合其他兩種算法的優點，在搜索后期持續優化，搜索到更好的解。因此，相對量子進化算法及差分進化算法，筆者算法在求解VRP問題時具有更強的全局搜索能力。

圖3 進化過程對比Fig.3 Comparison for the evolution of the proposed QDE algorithm

4 結 論

設計了量子差分進化算法求解車輛路徑問題，通過量子交叉、變異及動態量子旋轉門實現量子種群的多樣化進化。算法在典型實例求解中以100%的成功率獲得最優解，優于雙種群遺傳算法、人工蜂群算法、改進和聲算法；基于標準CVRP算例將筆者算法與CRO，SC-ESA，KmeansFnO 3 種新型算法進行對比，結果顯示筆者算法對小型規模算例的求解效果優于SC-ESA及KmeansFnO，對中型規模算例的求解效果優于KmeansFnO但不及SC-ESA和CRO，對大型規模算例的求解效果不及其他3 種算法；與量子進化算法及差分進化算法的收斂對比實驗顯示筆者算法相對于其他兩種算法具有更好的全局搜索能力。因此筆者算法是求解中、小型規模CVRP的一種有效算法，但對于大型規模CVRP問題，筆者算法求解效果一般，還需要進一步優化。