求解動態需求車輛調度問題的自適應量子遺傳算法*

鄭丹陽， 毛劍琳， 郭 寧, 曲蔚賢， 王昌征

(昆明理工大學 信息工程與自動化學院，云南 昆明 650500)

?

求解動態需求車輛調度問題的自適應量子遺傳算法*

鄭丹陽， 毛劍琳， 郭 寧, 曲蔚賢， 王昌征

(昆明理工大學 信息工程與自動化學院，云南 昆明 650500)

針對物流配送過程中存在的動態車輛調度問題，即帶載車量約束的實時優化車輛路徑問題，提出一種自適應量子遺傳算法，用于最小化配送成本。根據搜索點目標函數的變化率，提出一種自適應量子旋轉門更新方式，并通過子種群適應度值的變化確定量子旋轉角的方向和大小，進而引導種群進化方向，提高算法的全局搜索廣泛性；設計了一種變異操作，用于保持自適應量子遺傳算法的種群多樣性，進而提高算法全局搜索的寬泛性；引入基于兩元素搜索原則的局部搜索方法來增強算法的局部優化能力。仿真實驗和算法比較驗證了所提算法的有效性和優越性。

物流配送; 自適應量子遺傳算法； 動態車輛路徑問題； 全局搜索； 局部優化

0 引 言

帶約束能力的動態車輛調度(capacitated dynamic vehicle routing problem,DVRP)是通過對實時出現的客戶新需求的配送順序進行優化調度，使某種指標達到最優。

在求解DVRP方面主流的智能優化算法主要包括遺傳算法(GA)[1]、蟻群算法(ACA)[2]、粒子群優化(PSO)算法[3]、模擬退火算法(SA)等。使用智能算法求解組合優化問題，已經成為智能計算領域研究的熱點[4]。例如，文獻[5]提出利用貪婪算法和GA求解倉儲車輛調度問題。文獻[6]提出了利用混合PSO算法對初始階段進行優化，再利用貪婪插入算法實現再優化，實現對動態車輛調度問題的求解。文獻[7]利用改進的ACA對飛機沖突解脫的路徑進行規劃，并驗證了改進的算法在求解的優越性。

在混合量子研究方面，文獻[8]提出量子進化算法，同時采用鄰近插入法結合兩元素法再優化線路內次序的方式增強局部開發能力。文獻[9]提出將量子計算與ACA相結合的量子蟻群算法。文獻[10]提出量子遺傳算法用于求解車輛路徑問題，用于最小化配送路程，得到的解均優于現存方法。文獻[11]提出將量子算法與PSO算法相結合，并與其他算法比較，驗證了其有效性。

本文提出一種自適應量子旋轉門更新方式，自適應量子遺傳算法(SAQGA)用于求解最小配送成本指標下的DVRP問題。通過搜索點目標函數的變化率構造量子旋轉門更新調整策略，同時設計一種變異操作，保持算法的種群多樣性，并引入兩元素鄰域搜索來增強算法的局部開發能力。仿真實驗和算法比較驗證了SAQGA的有效性和優越性。

1 問題描述

設配送中心(i=0)可用k輛配送車輛,k=1,2,…,K,對M位客戶進行運輸配送，每個車輛載重量為Q,每個各戶的需求量為qi，且qi

目標函數

(1)

約束條件

(2)

(3)

(4)

(5)

(6)

式(1)為目標函數,表示運輸成本最低,式(1)保證車輛k所承擔的運輸任務總和不超過本身的載重量；式(3)保證每個客戶都被訪問；式(4)和式(5)保證每個客戶僅被一輛車訪問一次；式(6)用于消除子回路。

在執行預優化階段配送任務的某時刻進行再優化，在開始時刻，由于執行預優化階段的配送任務，配送中心的部分車輛已離開配送中心并已服務部分客戶，導致配送的車輛位于不同的客戶處，擁有不同的剩余裝載量，直接調度無法進行，所以,需引入虛擬配送中心的概念，將車輛所在的客戶點視為虛擬配送中心。

設預優化階段未服務客戶數與第二階段新增加的客戶總數N,預優化階段派出 輛車，每輛車的剩余裝載量為Qs,s=1,2,…,S虛擬配送中心編號為N+1,N+2,…,N+S,新排出的車輛數為T,即：

目標函數

(7)

約束條件

(8)

(9)

(10)

(11)

(12)

(13)

式(7)為目標函數,表示運輸成本最低；式(8)和式(9)保證車輛k所承擔的運輸任務總和不超過本身的載重量；式(10)保證每個客戶都被訪問；式(11)和式(12)保證每個客戶僅被一輛車訪問一次；式(13)用于消除子回路。

2 SAQGA

2.1 自適應量子旋轉門更新機制

本文提出的SAQGA是通過更新量子旋轉角的大小和方向，進而指導種群的進化方向，因而量子旋轉角的大小和方向是影響算法性能的關鍵。SAQGA采用根據搜索點目標函數的變化率來確定量子旋轉角的大小和方向。

自適應量子旋轉角的定義如式(14)所示

(14)

式中θ0為初始旋轉角;sign(A)為矩陣A的符號，同時決定旋轉角的方向，旋轉角的旋轉方向由以下規則決定：當A≠0，旋轉方向為-sign(A);當A=0，方向可正可負。A的定義如式(15)所示

(15)

式中α0和β0(本代)為全局最優解的概率幅;α1和β0為第t代的量子比特概率幅。自適應因子B的定義如式(16)所示

(16)

(17)

(18)

(19)

在式(17)～式(19)中，i=1,2,…m,m為種群大小；j為量子比特；Xp和Xc分別為父代與子代染色體。

(20)

2.2 變異操作

為防止算法陷入局部最優而導致“早熟收斂”，在SAQGA中引入變異操作，對gen代種群依照概率pmutation進行變異操作，得到變異后的種群，進而提高了種群的多樣性和SAQGA的全局搜索的寬度。變異操作的步驟如下：

1)對于第gen代種群中的每一個量子位(i,j)，隨機產生變異概率pmutation_rand(i,j);

2)如果pmutation>pmutation_rand(i,j),則θij=0.5π-θij;否則,θij=θij;

3)u=[cosθij-sinθijcosθijsinθij],y=u×[a;b]T。

2.3 兩元素局部搜索

為增強算法的局部開發能力，SAQGA引入了兩元素局部搜索。兩元素局部搜索法通過對邊交換,在初始可行解的鄰域中對初始解進行調整，每次交換使可行解得到改進，直到鄰域中不能再改進為止。如圖1所示,以(i,j),(i+1,j+1)代替(j,i+1),(j,j+1),交換后線路中的路徑被反向，若交換后的行車路線長度變小，則采用兩元素法形成的新路線為更優解;否則,將原行車路線定位更優解。

圖1 兩元素局部搜索原理

2.4 適應度值計算

首先根據生成的可執行調度路線及每輛車的裝載量確定每輛車的首個客戶和最后一個客戶，再進行行車路程及運輸成本的計算，具體操作步驟如下：

1)根據每輛車的裝載量確定每輛車所要服務的客戶。

2)形成新的帶車輛的可執行調度路線圖。

3)計算可執行調度路線圖的路程和運輸成本。

2.5 SAQGA步驟

結合2.1～2.4，SAQGA的步驟如下：

1)令進化代數gen=1;

2)種群初始化，隨機產生初始種群p;

3)染色體解碼并計算每條染色體的適應度值;

4)量子旋轉門更新;

5)量子比特種群變異操作;

6)對所形成的初始路徑進行局部搜索，并進一步得到全局最優個體;

7)gen=gen+1,如果gen≤gen_max,則轉步驟(2)，否則,輸出最優路徑。

由SAQGA步驟可知:SAQGA通過自適應量子旋轉門操作，使算法獲得更加明確的搜索方向和尺度，進而提高算法全局搜索的廣泛性；通過變異操作，有效地保持種群的多樣性，提高算法全局搜索的寬泛性；通過引入基于兩元素的局部搜索，提高算法的局部搜索能力。綜上所述，SAQGA在全局探索方式和局部搜索策略上均做了有效改進，算法有望取得DVRP的優良解。

3 仿真實驗與算法比較

3.1 實驗設置

為了對SAQGA的性能進行驗證，將SAQGA與兩種SAQGA的變形算法和一種其他文獻中的算法進行比較。所有算法的測試程序均由Matlab編碼實現，操作系統的CPU主頻為2.8GHz，內存為1.0GB。每種算法均獨立重復運行20次，每次運行的迭代次數為100。

SAQGA的關鍵操作主要包括：1)使用量子遺傳算法(QGA)；2)使用基于搜索點目標函數的變化率原則的量子自適應旋轉門調整策略；3)使用變異操作；4)使用基于兩元素鄰域搜索的局部搜索。為了考察上述操作的有效性，考慮如下變形算法：

1)QGA：標準的量子遺傳算法，使用文獻[11]所述的兩階段實時優化規則，所有參數的設置與文獻一致;

2)SAQGA_V1：標準的量子遺傳算法，使用自適應量子旋轉門調整策略，參數設置與QGA一致;

3)SAQGA_V2：在SAQGA_V1的基礎上加入變異操作;

4)SAQGA_V3：在SAQGA_V1的基礎上加入兩元素局部搜索操作;

5)SAQGA：在SAQGA_V2的基礎上加入兩元素鄰域搜索。

3.2SAQGA與其變形算法比較

由圖2可知，量子遺傳算法在55代左右收斂，自適應量子遺傳算在45代左右收斂，加入變異操作和兩元素局部搜索的自適應量子遺傳算法在30代左右收斂，這得益于自適應量子遺傳算法以及變異操作和局部搜索的有效性。

圖2 算法迭代

QGA,SAQGA_V1,SAQGA_V2,SAQGA_V3與SAQGA的比較結果如表1所示。由表1可知:SAQGA_V1解的質量明顯優于QGA，表明在求解DVRP時，自適應量子旋轉門更新機制更加有效，這是由于DVRP帶有容量約束，同時又帶有行車距離的限制；SAQGA_V2解優于SAQGA_V1，表明在自適應量子混合算法中加入變異操作后，有利于提高解的質量；SAQGA_V3解優于SAQGA_V1，雖然SAQGA_V3中的全局搜索不如SAQGA_V1中的有效，但加入有效的局部搜索后，仍然能明顯提升算法的性能；SAQGA的解明顯優于SAQGA_V2和SAQGA_V3，表明同時采用改進的全局搜索和有效的局部搜索可獲得問題的優質解。綜上所述，SAQGA中的自適應量子旋轉門更新機制有助于提高算法的全局搜索能力，基于兩元素局部搜索和變異操作可加強算法的局部搜索能力，從而使算法在全局搜索和局部搜索之間達到較好的平衡，有效求解DVRP。

表1 SAQGA與其變形算法比較結果

3.3 SAQGA與其他算法比較

采用文獻[11]中的實驗數據設置，每種算法均獨立重復運行20次，每次運行的迭代次數為100。SAQGA與GA,IGA,ACA,IACA的比較結果如表2所示。

表2 SAQGA與其他算法比較結果

從表2可知，SAQGA的結果明顯優于兩種傳統啟發式算法和兩種自適應啟發式算法，從而表明了SAQGA求解DVRP的優越性。雖然SAQGA中加入兩元素局部搜索，但其搜索成功率明顯優于其他4種算法，從而表明了SAQGA求解DVRP的有效性。綜上所述，SAQGA是求解DVRP的一種優越且有效的算法。

4 結束語

本文提出了一種SAQGA，用于求解動態車輛調度問題。首次將SAQGA用于求解該類問題。在算法改進上，SAQGA采用一種新的策略更新量子旋轉門，進而使種群的進化方式得到了改進，使算法的搜索方向更加明確；此外，SAQGA融合了變異操作，有效保持了算法進化過程中的種群多樣性水平；最后，通過引入兩元素局部搜索來增強算法的局部開發能力。通過仿真實驗和算法比較驗證了SAQGA求解DVRP的有效性和優越性。下一步將針對多車場動態車輛調度問題設計基于QGA的有效求解算法。

[1] Berger J,Salois M,Begin R.A hybrid genetic algorithm for the vehicle routing problem with time windows[C]∥12th Biennial Conference of the Canadian Society for Computational Studies of Intelligence on Advances in Artificial Intelligence,1998:114-127.

[2] Czech Z J,Czarnas P.Parallel simulated for the vehicle routing problem with time windows[C]∥Proceedings of 10th Euromicro Workshop on Parallel,Distributed and Network-based Processing,2002:376-383.

[3] 肖健梅,黃有方,李軍軍.基于離散微粒子群優化的物流配送車輛路徑問題[J].系統工程,2005,23(4):97-100.

[4] Dantzing G B,Ramser J H.The truck dispatching problem[J].Management Science,1959,4(6):80-91.

[5] 王友釗,彭宇翔,潘芬蘭.基于貪心算法和遺傳算法的倉儲車輛調度算法[J].傳感器與微系統,2012,31(10):125-128.

[6] 周 慧,周 良,丁秋林.多目標動態車輛路徑問題建模及優化[J].計算機科學，2015,42(6):204-209.

[7] 倪 壯，肖 剛，敬忠良,等.改進蟻群算法的飛機沖突解脫路徑規劃方法[J].傳感器與微系統,2016,35(4):130-133.

[8] 趙燕偉，彭典軍，張景玲，等.有能力約束車輛路徑問題的量子進化算法[J].系統工程理論與實踐，2009,29(2):159-167.

[9] 趙燕偉.多車型同時取送貨問題的低碳路徑研究[J].浙江工業大學學報，2015,43(1):18-23.

[10] 王 旭,葛顯龍.基于兩階段求解算法的動態車輛調度問題研究[J].控制與決策，2012,27(2):175-181.

[11] 陸建山,周鴻波,謝偉東.基于量子粒子群優化的動態標定辨識方法[J].傳感器與微系統,2016,35(6):27-30.

[12] 沙林秀,賀昱曜.一種新的自適應量子遺傳算法[J].計算機工程，2013,39(9):218-221.

Self-adaptive quantum genetic algorithm for dynamic vehicle scheduling problem*

ZHENG Dan-yang, MAO Jian-lin, GUO Ning, QU Wei-xian, WANG Chang-zheng

(School of Information Engineering and Automation,Kunming University of Science and Technology,Kunming 650500,China)

Aiming at dynamic vehicle scheduling problem that is dynamic vehicle routing problem(DVRP)with vehicle capacity constraints in real time existed in process of logistics distribution,self-adaptive quantum genetic algorithm(SAQGA)is proposed to minimize the distribution cost.According to change rate of search point target functions, a new update mode adaptive quantum rotation gate is presented,and direction and magnitude of the quantum rotating angle is determined by changes in fitness values of sub-propulation,thus evolutionary direction of population is guided to improve depth of global search of algorithm.A mutation operation is designed to keep the population diversity of the self-adaptive quantum genetic algorithm and width of the global search of algorithm is improved.To enhance the local optimization ability,local search method based on the principle of two elements search is introduced.Simulation experiments and algorithm comparisons demonstrate the effectiveness and the superiority of the proposed algorithm.

logistics distribution; self-adaptive quantum genetic algorithm(SAQGA); dynamic vehicle routing problem(DVRP); global search; local optimization

10.13873/J.1000—9787(2017)08—0130—04

2016—07—27

國家自然科學基金資助項目(61163051); 云南省應用基礎研究基金資助項目(2009ZC050M)

TP 301.6

A

1000—9787(2017)08—0130—04

鄭丹陽(1992-)，女，碩士研究生，研究方向為算法優化，車輛調度。