求解車輛路徑問題的量子差分進化算法

2

(1.浙江工業大學 特種裝備制造與先進加工技術教育部重點實驗室，浙江 杭州 310014；2.中國計量大學 現代科技學院，浙江 杭州 310018)

量子進化算法最早由Han等[1]在Narayanan等[2]的量子遺傳算法概念基礎上提出，用于求解組合優化問題。該算法將量子理論與進化計算相融合，用量子位編碼表示染色體，通過量子門旋轉實現進化操作，具有并行度高、全局搜索能力強和收斂速度快的特點，已被應用于多種類型的車輛路徑問題，如王萬良等[3]將其應用于求解車輛共享帶軟時間窗的動態需求VRP問題；李川[4]應用量子進化算法解決了隨機車輛路徑問題；趙燕偉等[5]應用其求解了多車型同時取送貨的低碳路徑問題，研究結果表明量子進化算法對VRP，TSP等問題具有良好的求解效果。近年來對車輛路徑問題的求解研究趨向于多種方法融合，如陳曉瞇[6]將禁忌搜索算法與交叉算子相結合求解動態車輛路徑問題；趙燕偉等[7]提出用超啟發式算法求解選址-路徑問題。與其他算法的融合也正成為量子進化算法研究的一個重要趨勢，量子差分算法由Wang等[8]提出將差分進化算法較強的局域搜索能力與量子進化算法的全局搜索能力相結合，實現更高效的搜索效果。張曉雷[9]將該算法應用于函數極值優化，多個案例的應用比較結果顯示算法的尋優能力得到明顯改進；常新功等[10]提出了分解的多目標量子差分算法，并將其應用于測試函數，驗證了算法在非凸函數收斂性及分布性方面的改善；……