多車場動態路徑問題的自適應量子蟻群算法

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

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

多車場動態路徑問題的自適應量子蟻群算法

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

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

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

多車場動態車輛調度問題； 量子相位編碼； 自適應量子旋轉門； 兩元素搜索策略； 量子蟻群算法

0 引 言

多車場動態車輛調度問題(multi depot dynamic vehicle routing problem,MDDVRP)是由經典動態車輛調度問題中的單個車場變為多個車場衍生而來。目前，較為成熟的啟發式算法主要包括遺傳算法[1]、蟻群算法[2]、粒子群算法[3]、模擬退火算法等。

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

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

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

1 問題描述及解決方案

1.1 問題描述及數學模型

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

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

(1)

目標函數

(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)為目標函數，為最短路徑；式(3)確保車場的車輛足夠為客戶服務；式(4)、式(5)確保每個客戶由一輛車服務一次；式(6)確保每輛車均返回車場；式(7)確保每輛車的裝載量不超過其容量；式(8)確保車輛不能從一個車場行駛到另一個車場。

在某時刻，出現t個新用戶，此時假設未服務客戶數與新客戶的總和為r,已派出車輛數為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)為目標函數;式(10)、式(11)確保所派車輛數不超過車場所擁有的車輛數；式(12)、式(13)確保每個客戶僅被服務一次；式(14)確保每輛車均返回車場；式(15)、式(16)確保每輛車均不超過其裝載量。

1.2 解決方案

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

圖1 MDDVRP分配流程

2 SAQACA

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

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

2.2 信息素更新規則

信息素矩陣更新策略的設計直接影響算法的收斂速度和尋優效果。在SAQACA中，信息素矩陣更新策略是將螞蟻當前位置的適應度值函數與信息素相結合,即

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

式中ρ為信息素的揮發程度；Q為常系數；Lk為第k只螞蟻經過路徑的總長。

2.3 螞蟻移動規則

(17)

2.4 自適應量子旋轉門與相位更新

在SAQACA中，根據搜索點的量子比特和目標函數的變化率設計量子旋轉門的更新策略,即

(18)

2.5 SAQACA步驟

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

3 仿真實驗與算法比較

3.1 實驗設置

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

圖2 SAQACA算法流程

SAQACA的關鍵操作主要包括：使用QACA;使用非確定旋轉角的自適應量子旋轉門更新策略;使用最優解再優化策略。

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

1)QACA。

2)自適應量子旋轉門調整策略代替標準的量子旋轉門的量子蟻群算法(SAQACA_V1)。

3)在SAQACA_V1的基礎上加入兩元素鄰域搜索進行最優解再優化SAQACA。

表1 原始客戶

表2 新增客戶

表3 配送中心坐標

3.2 SAQACA與其變形算法比較

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

表4 SAQACA與其變形算法比較結果

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

3.3 SAQACA與其他算法比較

標準量子遺傳算法(QGA),QACA,以及采用非固定旋轉角的自適應量子旋轉門更新方式，即自適應量子遺傳算法(SAQGA)。采用實驗設置中的數據， SAQACA與QGA,QACA,SAQGA的比較結果如表5所示。

表5 SAQACA與其他算法比較結果

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

4 結束語

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

[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].傳感器與微系統,2016,35(4):130-133.

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

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

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

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

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

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

[11] 李舜酩,沈 峘,鮑慶勇.未知環境下基于行為控制的智能車輛路徑規劃研究[J].傳感器與微系統,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-)，女，碩士研究生，研究方向為算法優化，車輛調度。