求解車輛路徑問題的量子差分進(jìn)化算法

2

(1.浙江工業(yè)大學(xué) 特種裝備制造與先進(jìn)加工技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，浙江 杭州 310014；2.中國(guó)計(jì)量大學(xué) 現(xiàn)代科技學(xué)院，浙江 杭州 310018)

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

盡管量子差分進(jìn)化算法在解決眾多的NP-hard問題時(shí)獲得了良好的效果，但這種算法應(yīng)用于VRP的效果還有待于研究。筆者將量子差分進(jìn)化算法應(yīng)用于求解車輛路徑問題(CVRP)，根據(jù)VRP問題特征，基于差分進(jìn)化策略設(shè)計(jì)了量子交叉和變異方法以控制種群的進(jìn)化方向，同時(shí)設(shè)計(jì)動(dòng)態(tài)量子旋轉(zhuǎn)門的量子進(jìn)化算法進(jìn)行變領(lǐng)域搜索，通過兩種方法的協(xié)同進(jìn)化增強(qiáng)算法的全局搜索能力，典型算例及標(biāo)準(zhǔn)算例的仿真實(shí)驗(yàn)結(jié)果驗(yàn)證了算法的有效性及魯棒性。

1 模型構(gòu)建

1.1 問題描述

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

1.2 模型建立

(1)

約束條件為

(2)

(3)

(4)

(5)

(6)

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

(7)

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

2 量子差分進(jìn)化算法

2.1 量子編碼與解碼

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

將α，β矩陣轉(zhuǎn)換成二進(jìn)制矩陣G，即

(8)

式中r為均勻分布的隨機(jī)數(shù)0～1。

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

(9)

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

圖1 解碼結(jié)果示例
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]間的隨機(jī)數(shù)；g+1為當(dāng)前代數(shù)的下一代。

2.3 量子交叉

量子交叉的發(fā)生概率由交叉因子Cr值控制，對(duì)選定的父代個(gè)體進(jìn)行交叉混合，以產(chǎn)生新的多樣性個(gè)體，即

(11)

2.4 量子更新

量子門旋轉(zhuǎn)是量子進(jìn)化算法實(shí)現(xiàn)狀態(tài)轉(zhuǎn)移的主要方法，筆者設(shè)計(jì)動(dòng)態(tài)量子旋轉(zhuǎn)門進(jìn)行狀態(tài)的更新與轉(zhuǎn)移，即

(12)

由式(12)可知，旋轉(zhuǎn)角與當(dāng)前代數(shù)的解及當(dāng)前最優(yōu)解有關(guān)，且隨著迭代次數(shù)的增加，旋轉(zhuǎn)角逐步減小，從而有利于在最優(yōu)解附近進(jìn)行局部搜索。

其中

(13)

(14)

2.5 量子選擇

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

(15)

式中f為解碼后的適應(yīng)度函數(shù)。由式(15)可知：若通過量子交叉、變異后解碼得到的解優(yōu)于當(dāng)前解時(shí)則將其量子比特由量子交叉、變異更新，否則將量子由量子旋轉(zhuǎn)門更新。

2.6 局部?jī)?yōu)化

筆者算法的局部?jī)?yōu)化采用2-Opt和Move方式。

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

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

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

2.7 量子差分進(jìn)化算法的求解流程

量子差分進(jìn)化算法流程如下。

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

Step2按2.1節(jié)解碼生成初始路線。

Step3按2.6節(jié)的局部?jī)?yōu)化方法調(diào)整方案，若調(diào)整后解獲得改善，則替換原方案，否則不替換；按式(1)計(jì)算目標(biāo)函數(shù)值，保留最優(yōu)個(gè)體。

Step4判斷是否滿足終止條件，若滿足，則輸出最優(yōu)解；若不滿足，則轉(zhuǎn)Step 5。

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

Step6t=t+1，轉(zhuǎn)Step 2繼續(xù)執(zhí)行。

3 實(shí)驗(yàn)及結(jié)果分析

3.1 參數(shù)設(shè)置

取收縮因子F=0.05，量子交叉Cr=0.5，Δθt=0.05π采用matlab2010b編程，計(jì)算機(jī)配置為Intel Core i7-3630QM 2.40 GHz，8 GB RAM，在Windows 7系統(tǒng)執(zhí)行，以最大循環(huán)次數(shù)為結(jié)束條件。

3.2 實(shí)驗(yàn)一

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

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

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

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

3.3 實(shí)驗(yàn)二

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

表3 QDE與其他3 種算法的標(biāo)準(zhǔn)算例結(jié)果對(duì)比Table 3 Comparison for the performance of the proposed QDE algorithm in benchmark

由表3可知：筆者算法在顧客數(shù)為19～22的P算例中均求得了與標(biāo)準(zhǔn)算例相同的解，說明筆者算法對(duì)小型規(guī)模算例的求解效果較好，相比較SC-ESA在同等問題中只有1 個(gè)解與標(biāo)準(zhǔn)算例相同，KmeansFnO有2 個(gè)解與標(biāo)準(zhǔn)算例結(jié)果相同，筆者算法對(duì)小型P問題算例的求解效果較好，在中型規(guī)模A算例中，QDE算法優(yōu)于KmeansFnO但不及SC-ESA和CRO，對(duì)大型規(guī)模算例的求解效果不及其他3 種算法。

表4是量子差分進(jìn)化算法、量子進(jìn)化算法及差分進(jìn)化算法的求解結(jié)果對(duì)比，表中3 種算法的種群均為200，最大循環(huán)次數(shù)均為500。

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

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

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

圖3 進(jìn)化過程對(duì)比Fig.3 Comparison for the evolution of the proposed QDE algorithm

4 結(jié) 論

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