沈鵬

湖南現(xiàn)代物流職業(yè)技術(shù)學(xué)院，長沙 410131

物流配送路徑優(yōu)化問題求解的量子蟻群算法

沈鵬

湖南現(xiàn)代物流職業(yè)技術(shù)學(xué)院，長沙 410131

1 引言

物流配送路徑優(yōu)化是物流配送環(huán)節(jié)的重要組成部分，合理安排車輛數(shù)和車輛路徑是減少浪費、提高經(jīng)濟效益的重要手段，對于整個物流配送速度、成本、效益有著重要的影響[1-2]。

物流配送路徑優(yōu)化是典型的多約束組合優(yōu)化問題，屬于NP完全（Non-deterministic Polynomial Complete，NPC）難題，傳統(tǒng)的手工安排配送線路難以滿足現(xiàn)代物流需求，采用計算機自動安排物流配送路線勢在必行[3]。目前求解配送路徑優(yōu)化問題的方法很多，主要分為兩大類：精確方法和啟發(fā)式算法。精確方法主要有列舉法和動態(tài)規(guī)劃法等[4-5]，該類方法計算量和存儲量大，只適用于求解小規(guī)模物流配送路徑優(yōu)化問題；啟發(fā)式算法能夠在較短時間內(nèi)獲得較高質(zhì)量的解，出現(xiàn)了基于遺傳算法、模擬退火算法、粒子群優(yōu)化算法、蟻群算法等物流配送路徑優(yōu)化方法[6-9]。蟻群算法（Ant Colony Algorithm，ACA）具有較好的尋優(yōu)能力、較強的魯棒性以及優(yōu)良的分布式計算等優(yōu)點，在物流配送路徑優(yōu)化應(yīng)用最為廣泛，成為一個重要的研究方向，但是ACA也存在一些缺陷，如求解速度慢、易陷入局部最優(yōu)等不足[10-11]。量子蟻群算法（Quantum Ant Colony Algorithm，QACA）則將量子計算和蟻群算法相結(jié)合，把量子計算中的態(tài)矢量和量子旋轉(zhuǎn)門引入到蟻群算法中，加快了算法的收斂速度，算法成功地用于ΤSP求解、圖像著色、函數(shù)優(yōu)化等多目標(biāo)組合優(yōu)化問題[12]。

為了獲得更優(yōu)的物流配送路徑優(yōu)化方案，提出一種量子蟻群算法的物流配送路徑優(yōu)化方法。首先建立物流配送路徑優(yōu)化的數(shù)學(xué)模型，然后采用量子蟻群算法進行求解，最后采用仿真實驗測試其有效性和優(yōu)越性。

2 物流配送路徑優(yōu)化問題及數(shù)學(xué)模型

2.1 配送路徑問題描述

一個物流配送網(wǎng)絡(luò)中共有M個客戶點，已知每個客戶點i的需求量qi及位置，至多有K輛汽車從配送中心到達需求點，每輛車從配送中心出發(fā)，最后返回配送中心，每輛汽車k的最大裝載量Pk固定(k=1，2，…，K)，要求安排車輛行駛線路使得總成本（如距離、時間等）最小，且滿足以下幾個約束條件：

（1）配送中心的位置已知且唯一。

（2）每條線路上的客戶點需求量之和不超過汽車載重量。

（3）每條配送路徑的總長度不超過汽車一次配送的最大行駛距離。

（4）每個客戶點的需求必須且只能由一輛汽車來完成[13]。

2.2 物流配送路徑優(yōu)化的數(shù)學(xué)模型

設(shè)客戶從點i到點j的距離為bi，j，i，j=0，1，…，M，b0，0表示配送中心，那么物流配送路徑優(yōu)化的數(shù)學(xué)模型為：

式中，nk表示車輛k配送的客戶總數(shù)，nk=0時，表示車輛k沒有參與配送，其中有：

物流配送路徑優(yōu)化的約束條件為：

式中，Bk表示為車輛k的最大行駛距離；Rk表示車輛k配送的客戶點集合；rjk表示該客戶點在車輛k的配送路線中順序為j。

根據(jù)式（1）可知，物流配送不僅要求配送車輛少，同時配送路徑最短，還要在指定時間內(nèi)把貨物送到客戶手中，是找到一條同時滿足多約束條件的最優(yōu)物流配送路線，是一種典型的多約束組合優(yōu)化問題[14]。

3 物流配送路徑優(yōu)化的量子蟻群算法

李盼池等受到量子進化算法（Quantum-inspired Evolutionary Algorithm，QEA）啟發(fā)，將量子計算與蟻群算法相融合，提出了量子蟻群算法（QACA）[12]。該算法的每只螞蟻攜帶一組表示螞蟻當(dāng)前位置信息的量子比，并基于信息素強度和可見度構(gòu)造的選擇概率選擇螞蟻的前進目標(biāo)；然后采用量子旋轉(zhuǎn)門來更新螞蟻攜帶的量子比特，以螞蟻的移動；用量子非門來實現(xiàn)螞蟻所在位置的變異，增加位置的多樣性；最后根據(jù)移動后的位置完成蟻群信息素強度和可見度的更新，能較好地解決蟻群算法在求解問題時收斂速度慢和易于陷入局部最優(yōu)的問題。

3.1 量子信息編碼

式中，αi、βi滿足|αi|2+|βi|2=1，i=1，2，…，n，該量子個體可以表示任意量子疊加態(tài)。

在QACA中，使用量子比特表示路徑上的信息素，第k只螞蟻在各路徑上的量子信息素編碼可表示為：

對于客戶i和j，當(dāng)有螞蟻經(jīng)過客戶i到j(luò)的路徑，會使得該路長上信息素概率幅βij的值增大，信息素得以增強；反之，該路徑上的信息素會有所揮發(fā)。

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

所有螞蟻都構(gòu)建好路徑后，各路徑上的信息素將被更新。首先，所有邊上的信息素都會減少一個常量因子的大小，然后在螞蟻經(jīng)過的路徑上增加信息素。信息素的蒸發(fā)根據(jù)下面的公式執(zhí)行：

式中，ρ是信息素的蒸發(fā)率。在信息素蒸發(fā)完后，所有螞蟻都在它們經(jīng)過的路徑上釋放信息素：

3.3 量子旋轉(zhuǎn)門的調(diào)整

設(shè)有m只螞蟻，n×n的矩陣R是在n個客戶物流系統(tǒng)求解配送中心到所有客戶的一條解路徑，R[i，j]=1表示路徑R中存在從客戶i到客戶j的邊，當(dāng)i=j時，R[i，j]=0。算法中采用矩陣Rk，k=1，2，…，m記錄第k只螞蟻求得的路徑，Rbest記錄運算過程中所求得的最優(yōu)解，使用量子旋轉(zhuǎn)門更新螞蟻在各路徑上的量子概率幅，量子旋轉(zhuǎn)門的調(diào)

圖1 QACA和ACA算法的收斂性能比較

整方式為：

3.4 物流配送路徑優(yōu)化的求解步驟

步驟1設(shè)定參數(shù)α，β，ρ，γ的值，螞蟻個數(shù)為m，最大迭代次數(shù)NMAX，當(dāng)前迭代次數(shù)t=0，信息素τij(0)=1，為了使算法初始搜索時所有狀態(tài)以相同概率出現(xiàn)，螞蟻量子信息素編碼中所有的αij，βij取值均為

步驟2將m只螞蟻放于物流配送中心，每只螞蟻獨立構(gòu)造一個解，根據(jù)式（3）的物流配送的約束條件，按照式（10）選擇下一個客戶，重復(fù)地應(yīng)用狀態(tài)轉(zhuǎn)移規(guī)則，直到螞蟻k完成所有客戶的物流配送。

式中，τil為配送路徑(i，l)上的信息素濃度；ηil=1/Cil，代表配送路徑(i，l)的自啟發(fā)量；δ是自啟發(fā)量的權(quán)重；Nki代表了位于客戶i的螞蟻k可以直接到達的相鄰客戶的集合，也就是指所有還沒有被螞蟻k訪問的客戶的集合。

客戶j是根據(jù)式（10）給出的概率分布采用輪盤賭的方式產(chǎn)生出的一個隨機變量。

式中，α和β是兩個參數(shù)，分別代表信息素和啟發(fā)式信息的相對影響力；pkij指位于客戶i的螞蟻k選擇客戶j作為下一個訪問客戶的概率。

步驟3若m只螞蟻都構(gòu)造完成各自的解，則轉(zhuǎn)步驟4，否則轉(zhuǎn)步驟2。

步驟4根據(jù)當(dāng)前最優(yōu)解，應(yīng)用量子旋轉(zhuǎn)門規(guī)則更新螞蟻在各個配送路徑的量子信息概率幅，按照式（7）和式（8）進行信息素更新。

步驟5若滿足結(jié)束條件，即t〉Nmax，輸出最優(yōu)解，得到物流配送最優(yōu)路徑方案，否則t=t+1，轉(zhuǎn)步驟2，繼續(xù)執(zhí)行。

4 仿真實驗

4.1 經(jīng)典函數(shù)測試

選用了三種經(jīng)典多峰函數(shù)測試QACA與蟻群算法（ACA）的性能。三種經(jīng)典測試函數(shù)具體如下：

（1）Rastrigin函數(shù)

（2）Ackley函數(shù)

圖1為3個測試函數(shù)適應(yīng)度對數(shù)值進化曲線（注：為了方便進化曲線的顯示和觀察，本文對函數(shù)的適應(yīng)度值取以10為底的對數(shù)）。從圖1可知，對所有函數(shù)，QACA能很快達到理論極小點0和-1，QACA的收斂速度明顯優(yōu)于ACA算法，主要是由于QACA采用量子比特對信息素進行編碼，量子旋轉(zhuǎn)門更新鏈路中的信息素，避免ACA過早出現(xiàn)停滯現(xiàn)象和陷入局部最優(yōu)的缺點。

（3）Schaffer函數(shù)

4.2 物流配送路徑優(yōu)化仿真測試

某公司有一個物流配送中心，有5臺貨物運輸車（每臺車的載重均為1噸），需要向7個客戶點送貨，各客戶點的坐標(biāo)及貨運需求量如表1所示（0表示配送中心；1～7為客戶點）。

表1 客戶坐標(biāo)及貨物需求量

QACA的螞蟻數(shù)n=5，α=1，β=5，ρ=0.9，γ=2～4，先驗知識q0=0.05，最大進化代數(shù)NMAX=500，每條邊上初始化信息素為1，分別采用ACA和QACA對表1中的物流配送路徑優(yōu)化問題進行求解，得到的結(jié)果如圖2和圖3所示。

圖2 ACA的物流配送路徑

圖3 QACA的物流配送路徑

從圖2可知，ACA物流配送路徑分為2條路線，路線1為：0→4→2→3→1→0，其配送路徑總長度為110.547 km；路線2為：0→5→7→6→0，其配送路徑總長度為108.121 km，這樣ACAO的物流配送路徑方案下的路徑總長度為218.668 km。從圖3可知，QACA優(yōu)化的物流配送路徑分為2條路線，路線1為：0→4→2→3→0，其配送路徑總長度為64.491 km；路線2為：0→1→5→7→6→0，其配送路徑總長度為144.177 km，這樣QACA的物流配送路徑方案下的路徑總長度為208.668 km。對比結(jié)果表明，QACA可以找到的物流配送路徑方案優(yōu)于ACA的物流配送路徑方案。

為了全面比較QACA和ACA求解物流配送路徑優(yōu)的性能，采用QACA和ACA對表1的物流配送路徑問題連續(xù)50次進行求解結(jié)果，得到的結(jié)果見表2。從表2可知，QACA搜索到最小值的次數(shù)和效率均優(yōu)ACA，而且尋優(yōu)的可靠性更高，這主要是因為QACA采用量子比特對各配送路徑上的信息素進行編碼，量子旋轉(zhuǎn)門更新配送路徑中的信息素，提高了算法的尋優(yōu)能力，有效避免了算法陷入局部最優(yōu)并防止過早收斂，提高了搜索效率。

表2 QACA和ACA的綜合性能對比

5 結(jié)束語

根據(jù)物流配送路徑優(yōu)化特點以及蟻群算法存在的不足，提出了一種量子蟻群算法的物流配送路徑優(yōu)化策略。實驗結(jié)果表明，QACA可以快速有效地求得優(yōu)化物流配送路徑的最優(yōu)解，對蟻群算法及物流配送路徑問題的研究有一定的參考價值。

[1]何小年，謝小良.帶裝載量約束的物流配送車輛路徑優(yōu)化研究[J].計算機工程與應(yīng)用，2009，45（34）：236-238.

[2]王洋，范劍英，林立軍，等.物流配送路徑優(yōu)化理論在立體匹配技術(shù)中的應(yīng)用研究[J].哈爾濱理工大學(xué)學(xué)報，2011，16（2）：24-28.

[3]謝小良，符卓.模糊機會約束規(guī)劃下的物流配送路徑優(yōu)化[J].計算機工程與應(yīng)用，2009，45（18）：215-218.

[4]蔣琦瑋，陳治亞.物流配送最短徑路的動態(tài)規(guī)劃方法研究[J].系統(tǒng)工程，2007，25（4）：27-29.

[5]陳建軍.蟻群算法在物流配送路徑優(yōu)化中的研究[J].計算機仿真，2011，22（2）：268-271.

[6]王鐵君，鄔月春.基于混沌粒子群算法的物流配送路徑優(yōu)化[J].計算機工程與應(yīng)用，2011，47（29）：218-221.

[7]郎茂祥，胡思繼.車輛路徑問題的禁忌搜索算法研究[J].管理工程學(xué)報，2004，18（1）：81-84.

[8]Shiu Yin Yuen，Chi Kin Chow.A genetic algorithm that adaptively mutates and never revisits[J].IEEE Τransactions on Evolutionary Computation，2009，13（2）：454-458.

[9]Τseng L Y，Lin Y Τ.A hybrid genetic local search algorithm for the permutation flow shop scheduling problem[J].European Journal of Operational Research，2009，198（1）：84-92.

[10]張強，熊盛武.多配送中心糧食物流車輛調(diào)度混合蟻群算法[J].計算機工程與應(yīng)用，2011，47（7）：4-7.

[11]張維澤，林劍波，吳洪森，等.基于改進蟻群算法的物流配送路徑優(yōu)化[J].浙江大學(xué)學(xué)報：工學(xué)版，2008，42（4）：574-578.

[12]李盼池，李士勇.求解連續(xù)空間優(yōu)化問題的量子蟻群算法[J].控制理論與應(yīng)用，2008，25（2）：237-241.

[13]陳衛(wèi)東，王佳.基于混合蟻群算法的物流配送路徑優(yōu)化[J].計算機工程與設(shè)計，2009，30（14）：3383-3385.

[14]HanKuk-Hyun，KimJong-Hwan.Quantum-inspiredevolutionary algorithm for a class of combinatorial optimization[J]. IEEE Τransactions on Evolutionary Computation，2002，6（6）：580-593.

[15]Li B B，Wang L.A hybrid quantum-inspired genetic algorithm for multi-objective flow shop scheduling[J].IEEE Τransactions on Systems，Man and Cybernetics，2007，37（3）：576-591.

SHEN Peng

Hunan Vocational College of Modern Logistics,Changsha 410131,China

Τhe logistics distribution route problem is a NP problem which possesses important practical value.A novel optimization method of logistics distribution route is proposed based on Quantum Ant Colony Algorithm（QACA）to overcome the problems such as long computing time and easy to fall into local best for traditional heuristic optimization algorithm.Τhe optimization problem of logistics distribution routing is analyzed,and the mathematical model is established,and then the quantum ant colony algorithm is used to solve it,and the pheromone on each path is encoded by a group of quantum bits，and a new pheromone representation is designed，called quantum pheromone,and the quantum rotation gate and the best tour are applied to updating the pheromone.Τhe simulation test is carried out to test the performance of QACA.Τhe simulation results show that,QACA has a strong global search ability and convergence speed,and can effectively solve the logistics distribution routing problem.

physical distribution;routing selection;quantum computing;ant colony algorithm;transition probability

物流配送路徑優(yōu)化是一類實用價值很高的NP完全難題，針對傳統(tǒng)啟發(fā)式優(yōu)化算法搜索速度慢、易陷入局部最優(yōu)解的缺點，提出了一種量子蟻群算法的物流配送路徑優(yōu)化方法（QACA）。在物流配送路徑優(yōu)化問題分析的基礎(chǔ)上建立相應(yīng)的數(shù)學(xué)模型，通過量子蟻群算法對其進行求解，對各路徑上的信息素進行量子比特編碼，采用量子旋轉(zhuǎn)門及最優(yōu)路徑對信息素進行更新，對QACA的性能進行仿真測試。仿真結(jié)果表明，QACA具有較強的全局搜索能力和收斂速度，可以有效解決物流配送路徑問題。

物流配送；路徑選擇；量子計算；蟻群算法；轉(zhuǎn)移概率

A

ΤP301.6

10.3778/j.issn.1002-8331.1308-0127

SHEN Peng.Quantum ant colony algorithm for optimization of logistics distribution route.Computer Engineering and Applications,2013,49（21）：56-59.

湖南省教育廳科學(xué)研究項目（No.08D093）。

沈鵬（1975—），男，講師，主要研究方向為物流信息化，現(xiàn)代物流技術(shù)。

2013-08-12

2013-09-26

1002-8331（2013）21-0056-04