基于量子微粒群算法的車輛路徑問題研究

摘要：提出一種基于量子行為的微粒群智能優化算法，使用量子角表示量子比特的狀態，并引入微粒群算法中，對量子群中的各量子角進行自適應動態調整，設計一種新的編碼方式，用于求解車輛路徑問題，通過計算表明，該算法是解決車輛路徑問題的有效方法。

關鍵詞：量子算法；粒子群算法；車輛路徑問題

中圖分類號：TP14文獻標識碼：A

文章編號：1002-3100(2008)05-0012-03

Abstract: Quantum-Behaved Particle Swarm Optimization was applied to solve the discrete Vehicle Routing Problem（VRP）. The quantum angle is emplyed in the quantum bit and the improved particle swarm optimization is adopted to update the Q-bit automatically. It has been proved that QPSO is an effective algorithm solving the Vehicle Routing Problems.

Key words: quantum algorithm; particle swarm optimization; vehicle routing problems

0引言

車輛路徑問題（Vehicle Routing Problem）是由Dantzig等提出的，它是物流活動的關鍵環節之一，其任務是選派合適的車輛，確定行車路線﹑時間及服務對象，以降低配送費用和提高服務質量。車輛路徑問題是一類具有廣泛應用的NP難題，國內外學者已經提出了許多求解該問題的啟發式算法，如禁忌搜索算法﹑遺傳算法﹑節約算法﹑蟻群算法等。

量子進化計算（Quantum Computation， QC）是一種將量子機制與基本進化計算相結合的概率搜索算法，其本質特征是充分利用了量子態的疊加性和相干性，量子計算以其并行性﹑指數級存儲容量和指數加速度特征展示了其強大的功能。本文采用量子算法與微粒群算法相結合，提出了一種新的基于量子行為的微粒群算法（QPSO）求解VRP問題，取得了較好的效果。

1車輛路徑問題的模型描述

2算法原理及描述

2.1量子進化算法（QEA）

4實驗結果及其分析

實驗結果表明，QPSO方法對該問題具有較高的搜索成功率100%，且QPSO的運算時間和整體搜索成功率也較高。

5結束語

本文將粒子群算法和量子算法結合，運用到物流車輛配送問題中，通過實驗表明QPSO算法是解決VRP問題的一種有效的方法，具有較好的運算速度和尋優能力。本文只研究了規模較小情況的量子微粒群算法的尋優能力，規模較大的情況還有待進一步深入的研究和討論。

參考文獻：

[1] 李軍，郭耀煌. 物流配送車輛優化調度理論與方法[M]. 北京：中國物資出版社，2001.

[2] 王巖，路春一，豐小月，等. 一種新的量子群進化算法研究[J]. 小型微型計算機系統，2006，2(8):1478-1482.

[3]Kennedy J， Eberhart R C. Particle swarm optimization: Developments， Applications and Resources[C] // Proc. Congress on Evolutionary Computation 2001. Piscataway， NJ: IEEE Press， 1999:1931-1938.

[4]Ayed Salmen， Imtiaz Ahmad， Sabah AI-Madani. Particle swarm optimization for task assignment problems[J]. Microprocessors and Microsystems， 2002(26):363-371.

[5]SUN， XU WE. A global Search Strategy of Quantum-behaved Particle Swarm Optimization[C] // Proceedings of IEEE Conference on Cybemetics and Intelligent Systems， 2004:111-116.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。