多車場動態(tài)路徑問題的自適應(yīng)量子蟻群算法

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

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

多車場動態(tài)路徑問題的自適應(yīng)量子蟻群算法

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

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

針對物流配送過程中存在的多配送中心動態(tài)需求車輛調(diào)度問題即多車場動態(tài)車輛調(diào)度問題(MDDVRP)，提出了一種自適應(yīng)量子蟻群算法(SAQACA)，用于最小化路徑。根據(jù)量子的相位編碼方式，提出了對蟻群的信息素矩陣進(jìn)行直接編碼，進(jìn)而實(shí)現(xiàn)由量子旋轉(zhuǎn)門更新完成螞蟻移動；根據(jù)搜索點(diǎn)的量子相位特點(diǎn)及目標(biāo)函數(shù)的變化率，提出了一種自適應(yīng)量子旋轉(zhuǎn)門更新方式，進(jìn)而提高了算法的全局搜索深度；引入基于兩元素搜索策略的局部搜索方法提高了算法的局部優(yōu)化能力，從而對可行解進(jìn)行改進(jìn)。仿真實(shí)驗(yàn)與算法比較驗(yàn)證了所提算法的有效性和優(yōu)越性。

多車場動態(tài)車輛調(diào)度問題； 量子相位編碼； 自適應(yīng)量子旋轉(zhuǎn)門； 兩元素搜索策略； 量子蟻群算法

0 引 言

多車場動態(tài)車輛調(diào)度問題(multi depot dynamic vehicle routing problem,MDDVRP)是由經(jīng)典動態(tài)車輛調(diào)度問題中的單個(gè)車場變?yōu)槎鄠€(gè)車場衍生而來。目前，較為成熟的啟發(fā)式算法主要包括遺傳算法[1]、蟻群算法[2]、粒子群算法[3]、模擬退火算法等。

在量子算法和蟻群算法應(yīng)用方面，文獻(xiàn)[4]應(yīng)用改進(jìn)蟻群算法對飛機(jī)路徑進(jìn)行規(guī)劃并驗(yàn)證了該算法具有較高的求解精度和較快的收斂速度。文獻(xiàn)[5]提出了將量子算法與粒子群算法相結(jié)合，并通過比較驗(yàn)證了其有效性。文獻(xiàn)[6]將雙向蟻群算法與微正則退火算法相結(jié)合用于求解旅行商問題，并驗(yàn)證了其優(yōu)越性。文獻(xiàn)[7]將改進(jìn)蟻群算法應(yīng)用于邊緣檢測中，并通過仿真驗(yàn)證了其可行性。

在車輛調(diào)度與路徑規(guī)劃方面，文獻(xiàn)[8]提出了分散搜索算法并驗(yàn)證了算法的有效性；文獻(xiàn)[9]提出了改進(jìn)粒子群算法求解多車場車輛路徑問題并驗(yàn)證了算法在速度和尋優(yōu)效率的有效性和優(yōu)越性；文獻(xiàn)[10]提出了貪婪算法和遺傳算法求解倉儲車輛調(diào)度問題。文獻(xiàn)[11]提出行為控制的智能車輛路徑規(guī)劃方式并通過對比實(shí)驗(yàn)取得了滿意結(jié)果。

本文提出了一種自適應(yīng)量子蟻群算法求解最小配送成本指標(biāo)下的MDDVRP。在自適應(yīng)量子蟻群算法(self-adaptive quantum ant colony algorithm,SAQACA)中，將量子相位編碼應(yīng)用于蟻群編碼中。同時(shí)，提出了一種新的量子旋轉(zhuǎn)門更新方式。此外，引入局部搜索對可行解進(jìn)行再優(yōu)化，增強(qiáng)算法的局部開發(fā)能力。仿真實(shí)驗(yàn)和對比算法驗(yàn)證了SAQACA的有效性和優(yōu)越性。

1 問題描述及解決方案

1.1 問題描述及數(shù)學(xué)模型

多車場動態(tài)車輛路徑問題可描述為:有N個(gè)車場，擁有容量為Q的配送車輛Km，m=1,2,…,N輛，現(xiàn)已知客戶i到客戶j的距離為dij，需對M個(gè)客戶進(jìn)行服務(wù)，客戶i的貨物需求為qi，i=1,2,…,M，且qi

設(shè)客戶編碼為1,2,…,M，車場編碼為M+1,M+2,…，M+N，定義變量如式(1)所示

(1)

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

(2)

約束條件

(3)

(4)

(5)

i=m∈{M+1,M+2,…,M+N},k∈{1,2,…,Km}

(6)

k∈{1,2,…,Km}

(7)

k∈{1,2,…,Km}

(8)

模型中，式(2)為目標(biāo)函數(shù)，為最短路徑；式(3)確保車場的車輛足夠?yàn)榭蛻舴?wù)；式(4)、式(5)確保每個(gè)客戶由一輛車服務(wù)一次；式(6)確保每輛車均返回車場；式(7)確保每輛車的裝載量不超過其容量；式(8)確保車輛不能從一個(gè)車場行駛到另一個(gè)車場。

在某時(shí)刻，出現(xiàn)t個(gè)新用戶，此時(shí)假設(shè)未服務(wù)客戶數(shù)與新客戶的總和為r,已派出車輛數(shù)為s,每輛車的剩余裝載量為Qs,s=1,2,…,S，虛擬配送中心編號為T+1,T+2,…,T+S，原車場編號為T+S+1,T+S+2,…，T+S+N，車場剩余的可用車輛為Rm，m=1,2,…,N輛，即

(9)

i=m∈{T+S+1,T+S+2,…,T+S+N}

(10)

(11)

(12)

(13)

i=m∈{T+1,T+2,…,T+S+N},

k∈{1,2,…,Rm}

(14)

k∈{1,2,…,Rm}

(15)

S+N},k∈{1,2,…,Rm}

(16)

模型中，式(9)為目標(biāo)函數(shù);式(10)、式(11)確保所派車輛數(shù)不超過車場所擁有的車輛數(shù)；式(12)、式(13)確保每個(gè)客戶僅被服務(wù)一次；式(14)確保每輛車均返回車場；式(15)、式(16)確保每輛車均不超過其裝載量。

1.2 解決方案

采用擇近原則對每個(gè)客戶進(jìn)行車場分配，具體流程如圖1所示。

圖1 MDDVRP分配流程

2 SAQACA

2.1 量子相位編碼信息素矩陣

SAQACA采用量子相位編碼方式對信息素矩陣進(jìn)行編碼，達(dá)到由量子位直接控制螞蟻的移動方向和增大算法搜索范圍的效果，即對問題規(guī)模為m+n，m為需求客戶數(shù)，n為車場數(shù)，則生成[2×(m+n)]×(m+n)的信息素矩陣。

2.2 信息素更新規(guī)則

信息素矩陣更新策略的設(shè)計(jì)直接影響算法的收斂速度和尋優(yōu)效果。在SAQACA中，信息素矩陣更新策略是將螞蟻當(dāng)前位置的適應(yīng)度值函數(shù)與信息素相結(jié)合,即

τij(t+1)=(1-ρ)τij(t)+Q/Lk,0<ρ<1

式中ρ為信息素的揮發(fā)程度；Q為常系數(shù)；Lk為第k只螞蟻經(jīng)過路徑的總長。

2.3 螞蟻移動規(guī)則

(17)

2.4 自適應(yīng)量子旋轉(zhuǎn)門與相位更新

在SAQACA中，根據(jù)搜索點(diǎn)的量子比特和目標(biāo)函數(shù)的變化率設(shè)計(jì)量子旋轉(zhuǎn)門的更新策略,即

(18)

2.5 SAQACA步驟

SAQACA主要包括信息素矩陣的量子比特編碼、信息素更新、自適應(yīng)量子旋轉(zhuǎn)門更新、兩元素再優(yōu)化等，使算法的收斂性和尋優(yōu)性有所提高，SAQACA步驟如圖2所示。

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

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

為了對SAQACA的性能進(jìn)行驗(yàn)證，將SAQACA與2種其變形算法進(jìn)行比較。對一個(gè)隨機(jī)生成的MDDVRP進(jìn)行求解，車場和用戶均分布在100×100的范圍內(nèi)，車輛的最大容量為25，具體如表1～表3所示。每種算法均獨(dú)立重復(fù)運(yùn)行20次，每次運(yùn)行的迭代次數(shù)為100次。

圖2 SAQACA算法流程

SAQACA的關(guān)鍵操作主要包括：使用QACA;使用非確定旋轉(zhuǎn)角的自適應(yīng)量子旋轉(zhuǎn)門更新策略;使用最優(yōu)解再優(yōu)化策略。

為了考察上述操作的有效性，考慮如下變形算法：

1)QACA。

2)自適應(yīng)量子旋轉(zhuǎn)門調(diào)整策略代替標(biāo)準(zhǔn)的量子旋轉(zhuǎn)門的量子蟻群算法(SAQACA_V1)。

3)在SAQACA_V1的基礎(chǔ)上加入兩元素鄰域搜索進(jìn)行最優(yōu)解再優(yōu)化SAQACA。

表1 原始客戶

表2 新增客戶

表3 配送中心坐標(biāo)

3.2 SAQACA與其變形算法比較

SAQACA與其變形算法的比較結(jié)果如表4所示。

表4 SAQACA與其變形算法比較結(jié)果

由表4可知:SAQACA_V1解的質(zhì)量明顯優(yōu)于QACA，說明在求解MDDVRP時(shí)，自適應(yīng)量子旋轉(zhuǎn)門更新策略優(yōu)于傳統(tǒng)量子旋轉(zhuǎn)門更新機(jī)制；SAQACA解優(yōu)于SAQACA_V1，表明加入有效的局部搜索對可行解進(jìn)行再優(yōu)化可再提高最優(yōu)解的質(zhì)量。綜上，SAQACA中的自適應(yīng)量子旋轉(zhuǎn)門更新策略有助于提高算法的全局搜索能力，基于兩元素局部搜索可加強(qiáng)算法的局部搜索能力，從而使算法在全局搜索和局部搜索之間達(dá)到較好的平衡，有效求解MDDVRP。

3.3 SAQACA與其他算法比較

標(biāo)準(zhǔn)量子遺傳算法(QGA),QACA,以及采用非固定旋轉(zhuǎn)角的自適應(yīng)量子旋轉(zhuǎn)門更新方式，即自適應(yīng)量子遺傳算法(SAQGA)。采用實(shí)驗(yàn)設(shè)置中的數(shù)據(jù)， SAQACA與QGA,QACA,SAQGA的比較結(jié)果如表5所示。

表5 SAQACA與其他算法比較結(jié)果

由表5可知，SAQACA的結(jié)果明顯優(yōu)于QGA和QACA,SAQGA2種算法，表明SAQACA求解MDDVRP的優(yōu)越性和有效性。綜上所述，SAQACA是求解MDDVRP的一種優(yōu)越且有效的算法。

4 結(jié)束語

首次提出了一種SAQACA用于求解多車場動態(tài)車輛調(diào)度問題。在算法改進(jìn)上，SAQACA將量子相位編碼應(yīng)用于蟻群編碼中，使量子比特控制螞蟻的移動；此外，SAQACA應(yīng)用一種新的改善蟻群的進(jìn)化方向的量子旋轉(zhuǎn)門策略更新提高了算法的全局搜索能力；最后，通過引入再優(yōu)化策略提高了算法的局部搜索能力。通過算法比較驗(yàn)證了SAQACA求解MDDVRP的有效性和優(yōu)越性。下一步工作將針對調(diào)度問題和量子算法進(jìn)行更深入研究。

[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] Wang Gengsheng,Yu Yunxin.An improved ant colony algorithm for VRP problem[C]∥Intelligent Information Technology and Security Informatics,2011:129-133.

[3] Zhu Yuhua,Ge Hongyi,Zhen Tong.Hybrid particle swarm algorithm for grain logistics vehicle routing problem[C]∥Intelligent Information Technology Application,2009:364-367.

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

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

[6] 周浩理，李太君，肖 沙,等.微正則退火的雙向蟻群優(yōu)化算法[J].傳感器與微系統(tǒng),2016,35(4):127-129,133.

[7] 李國寧，李沛齊，王燕芩.基于改進(jìn)蟻群算法的軌道圖像邊緣檢測方法[J].傳感器與微系統(tǒng),2013,32(6):130-133.

[8] 張 軍,唐加福,潘震東.求解多車場車輛路徑問題的分散搜索算法[J].系統(tǒng)工程,2009,27(6):83-90.

[9] 王鐵君,鄔開俊.多車場車輛路徑問題的改進(jìn)粒子群算法[J].計(jì)算機(jī)工程與應(yīng)用,2013,49(2):5-8.

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

[11] 李舜酩,沈 峘,鮑慶勇.未知環(huán)境下基于行為控制的智能車輛路徑規(guī)劃研究[J].傳感器與微系統(tǒng),2010,29(4):67-70.

Self-adaptivequantumantcolonyalgorithmforsolvingmultidepotdynamicvehicleschedulingproblem

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

(SchoolofInformationEngineeringandAutomation,KunmingUniversityofScienceandTechnology,Kunming650500,China)

Aiming at multi depot dynamic vehicle routing problem(MDDVRP)existed in the process of logistics distribution,self-adaptive quantum ant colony algorithm(SAQACA)is proposed to minimize the distribution cost.According to the quantum phase encoding method,directly encoding of pheromone matrix of ant colony is presented to complete the movement of ants.According to quantum phase characteristics of search point and object functions change rate,a mode of adaptive quantum rotation gate is presented,to enhance global search depth,the local search method based on the principle of the two elements is introduced to enhance local optimization ability,so as to improve feasible solution. Simulation experiments and algorithm comparison demonstrate the effectiveness and the superiority of proposed algorithm.

multi depot dynamic vehicle routing problem(MDDVRP); quantum phase encoding; adaptive quantum rotation gate; two element search strategy; quantum ant colony algorithm

10.13873/J.1000—9787(2017)10—0133—04

2016—08—22

TP 301.6

A

1000—9787(2017)10—0133—04

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