求解動(dòng)態(tài)需求車輛調(diào)度問(wèn)題的自適應(yīng)量子遺傳算法*

鄭丹陽(yáng)， 毛劍琳， 郭 寧, 曲蔚賢， 王昌征

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

?

求解動(dòng)態(tài)需求車輛調(diào)度問(wèn)題的自適應(yīng)量子遺傳算法*

鄭丹陽(yáng)， 毛劍琳， 郭 寧, 曲蔚賢， 王昌征

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

針對(duì)物流配送過(guò)程中存在的動(dòng)態(tài)車輛調(diào)度問(wèn)題，即帶載車量約束的實(shí)時(shí)優(yōu)化車輛路徑問(wèn)題，提出一種自適應(yīng)量子遺傳算法，用于最小化配送成本。根據(jù)搜索點(diǎn)目標(biāo)函數(shù)的變化率，提出一種自適應(yīng)量子旋轉(zhuǎn)門更新方式，并通過(guò)子種群適應(yīng)度值的變化確定量子旋轉(zhuǎn)角的方向和大小，進(jìn)而引導(dǎo)種群進(jìn)化方向，提高算法的全局搜索廣泛性；設(shè)計(jì)了一種變異操作，用于保持自適應(yīng)量子遺傳算法的種群多樣性，進(jìn)而提高算法全局搜索的寬泛性；引入基于兩元素搜索原則的局部搜索方法來(lái)增強(qiáng)算法的局部?jī)?yōu)化能力。仿真實(shí)驗(yàn)和算法比較驗(yàn)證了所提算法的有效性和優(yōu)越性。

物流配送; 自適應(yīng)量子遺傳算法； 動(dòng)態(tài)車輛路徑問(wèn)題； 全局搜索； 局部?jī)?yōu)化

0 引 言

帶約束能力的動(dòng)態(tài)車輛調(diào)度(capacitated dynamic vehicle routing problem,DVRP)是通過(guò)對(duì)實(shí)時(shí)出現(xiàn)的客戶新需求的配送順序進(jìn)行優(yōu)化調(diào)度，使某種指標(biāo)達(dá)到最優(yōu)。

在求解DVRP方面主流的智能優(yōu)化算法主要包括遺傳算法(GA)[1]、蟻群算法(ACA)[2]、粒子群優(yōu)化(PSO)算法[3]、模擬退火算法(SA)等。使用智能算法求解組合優(yōu)化問(wèn)題，已經(jīng)成為智能計(jì)算領(lǐng)域研究的熱點(diǎn)[4]。例如，文獻(xiàn)[5]提出利用貪婪算法和GA求解倉(cāng)儲(chǔ)車輛調(diào)度問(wèn)題。文獻(xiàn)[6]提出了利用混合PSO算法對(duì)初始階段進(jìn)行優(yōu)化，再利用貪婪插入算法實(shí)現(xiàn)再優(yōu)化，實(shí)現(xiàn)對(duì)動(dòng)態(tài)車輛調(diào)度問(wèn)題的求解。文獻(xiàn)[7]利用改進(jìn)的ACA對(duì)飛機(jī)沖突解脫的路徑進(jìn)行規(guī)劃，并驗(yàn)證了改進(jìn)的算法在求解的優(yōu)越性。

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

本文提出一種自適應(yīng)量子旋轉(zhuǎn)門更新方式，自適應(yīng)量子遺傳算法(SAQGA)用于求解最小配送成本指標(biāo)下的DVRP問(wèn)題。通過(guò)搜索點(diǎn)目標(biāo)函數(shù)的變化率構(gòu)造量子旋轉(zhuǎn)門更新調(diào)整策略，同時(shí)設(shè)計(jì)一種變異操作，保持算法的種群多樣性，并引入兩元素鄰域搜索來(lái)增強(qiáng)算法的局部開(kāi)發(fā)能力。仿真實(shí)驗(yàn)和算法比較驗(yàn)證了SAQGA的有效性和優(yōu)越性。

1 問(wèn)題描述

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

目標(biāo)函數(shù)

(1)

約束條件

(2)

(3)

(4)

(5)

(6)

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

在執(zhí)行預(yù)優(yōu)化階段配送任務(wù)的某時(shí)刻進(jìn)行再優(yōu)化，在開(kāi)始時(shí)刻，由于執(zhí)行預(yù)優(yōu)化階段的配送任務(wù)，配送中心的部分車輛已離開(kāi)配送中心并已服務(wù)部分客戶，導(dǎo)致配送的車輛位于不同的客戶處，擁有不同的剩余裝載量，直接調(diào)度無(wú)法進(jìn)行，所以,需引入虛擬配送中心的概念，將車輛所在的客戶點(diǎn)視為虛擬配送中心。

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

目標(biāo)函數(shù)

(7)

約束條件

(8)

(9)

(10)

(11)

(12)

(13)

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

2 SAQGA

2.1 自適應(yīng)量子旋轉(zhuǎn)門更新機(jī)制

本文提出的SAQGA是通過(guò)更新量子旋轉(zhuǎn)角的大小和方向，進(jìn)而指導(dǎo)種群的進(jìn)化方向，因而量子旋轉(zhuǎn)角的大小和方向是影響算法性能的關(guān)鍵。SAQGA采用根據(jù)搜索點(diǎn)目標(biāo)函數(shù)的變化率來(lái)確定量子旋轉(zhuǎn)角的大小和方向。

自適應(yīng)量子旋轉(zhuǎn)角的定義如式(14)所示

(14)

式中θ0為初始旋轉(zhuǎn)角;sign(A)為矩陣A的符號(hào)，同時(shí)決定旋轉(zhuǎn)角的方向，旋轉(zhuǎn)角的旋轉(zhuǎn)方向由以下規(guī)則決定：當(dāng)A≠0，旋轉(zhuǎn)方向?yàn)?sign(A);當(dāng)A=0，方向可正可負(fù)。A的定義如式(15)所示

(15)

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

(16)

(17)

(18)

(19)

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

(20)

2.2 變異操作

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

1)對(duì)于第gen代種群中的每一個(gè)量子位(i,j)，隨機(jī)產(chǎn)生變異概率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 兩元素局部搜索

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

圖1 兩元素局部搜索原理

2.4 適應(yīng)度值計(jì)算

首先根據(jù)生成的可執(zhí)行調(diào)度路線及每輛車的裝載量確定每輛車的首個(gè)客戶和最后一個(gè)客戶，再進(jìn)行行車路程及運(yùn)輸成本的計(jì)算，具體操作步驟如下：

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

2)形成新的帶車輛的可執(zhí)行調(diào)度路線圖。

3)計(jì)算可執(zhí)行調(diào)度路線圖的路程和運(yùn)輸成本。

2.5 SAQGA步驟

結(jié)合2.1～2.4，SAQGA的步驟如下：

1)令進(jìn)化代數(shù)gen=1;

2)種群初始化，隨機(jī)產(chǎn)生初始種群p;

3)染色體解碼并計(jì)算每條染色體的適應(yīng)度值;

4)量子旋轉(zhuǎn)門更新;

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

6)對(duì)所形成的初始路徑進(jìn)行局部搜索，并進(jìn)一步得到全局最優(yōu)個(gè)體;

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

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

3 仿真實(shí)驗(yàn)與算法比較

3.1 實(shí)驗(yàn)設(shè)置

為了對(duì)SAQGA的性能進(jìn)行驗(yàn)證，將SAQGA與兩種SAQGA的變形算法和一種其他文獻(xiàn)中的算法進(jìn)行比較。所有算法的測(cè)試程序均由Matlab編碼實(shí)現(xiàn)，操作系統(tǒng)的CPU主頻為2.8GHz，內(nèi)存為1.0GB。每種算法均獨(dú)立重復(fù)運(yùn)行20次，每次運(yùn)行的迭代次數(shù)為100。

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

1)QGA：標(biāo)準(zhǔn)的量子遺傳算法，使用文獻(xiàn)[11]所述的兩階段實(shí)時(shí)優(yōu)化規(guī)則，所有參數(shù)的設(shè)置與文獻(xiàn)一致;

2)SAQGA_V1：標(biāo)準(zhǔn)的量子遺傳算法，使用自適應(yīng)量子旋轉(zhuǎn)門調(diào)整策略，參數(shù)設(shè)置與QGA一致;

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

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

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

3.2SAQGA與其變形算法比較

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

圖2 算法迭代

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

表1 SAQGA與其變形算法比較結(jié)果

3.3 SAQGA與其他算法比較

采用文獻(xiàn)[11]中的實(shí)驗(yàn)數(shù)據(jù)設(shè)置，每種算法均獨(dú)立重復(fù)運(yùn)行20次，每次運(yùn)行的迭代次數(shù)為100。SAQGA與GA,IGA,ACA,IACA的比較結(jié)果如表2所示。

表2 SAQGA與其他算法比較結(jié)果

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

4 結(jié)束語(yǔ)

本文提出了一種SAQGA，用于求解動(dòng)態(tài)車輛調(diào)度問(wèn)題。首次將SAQGA用于求解該類問(wèn)題。在算法改進(jìn)上，SAQGA采用一種新的策略更新量子旋轉(zhuǎn)門，進(jìn)而使種群的進(jìn)化方式得到了改進(jìn)，使算法的搜索方向更加明確；此外，SAQGA融合了變異操作，有效保持了算法進(jìn)化過(guò)程中的種群多樣性水平；最后，通過(guò)引入兩元素局部搜索來(lái)增強(qiáng)算法的局部開(kāi)發(fā)能力。通過(guò)仿真實(shí)驗(yàn)和算法比較驗(yàn)證了SAQGA求解DVRP的有效性和優(yōu)越性。下一步將針對(duì)多車場(chǎng)動(dòng)態(tài)車輛調(diào)度問(wèn)題設(shè)計(jì)基于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] 肖健梅,黃有方,李軍軍.基于離散微粒子群優(yōu)化的物流配送車輛路徑問(wèn)題[J].系統(tǒng)工程,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] 王友釗,彭宇翔,潘芬蘭.基于貪心算法和遺傳算法的倉(cāng)儲(chǔ)車輛調(diào)度算法[J].傳感器與微系統(tǒng),2012,31(10):125-128.

[6] 周 慧,周 良,丁秋林.多目標(biāo)動(dòng)態(tài)車輛路徑問(wèn)題建模及優(yōu)化[J].計(jì)算機(jī)科學(xué)，2015,42(6):204-209.

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

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

[9] 趙燕偉.多車型同時(shí)取送貨問(wèn)題的低碳路徑研究[J].浙江工業(yè)大學(xué)學(xué)報(bào)，2015,43(1):18-23.

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

[11] 陸建山,周鴻波,謝偉東.基于量子粒子群優(yōu)化的動(dòng)態(tài)標(biāo)定辨識(shí)方法[J].傳感器與微系統(tǒng),2016,35(6):27-30.

[12] 沙林秀,賀昱曜.一種新的自適應(yīng)量子遺傳算法[J].計(jì)算機(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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61163051); 云南省應(yīng)用基礎(chǔ)研究基金資助項(xiàng)目(2009ZC050M)

TP 301.6

A

1000—9787(2017)08—0130—04

鄭丹陽(yáng)(1992-)，女，碩士研究生，研究方向?yàn)樗惴▋?yōu)化，車輛調(diào)度。