蜂群優(yōu)化算法在帶軟時間窗的車輛路徑問題中的應用

摘 要:本文給出了帶軟時間窗的車輛路徑問題的一種新的算法，蜂群算法。通過計算若干benchmark問題，并將結果與硬時間窗的目前最好解及蟻群算法的相應解作比較與分析，驗證了算法的有效性。蜂群算法是剛剛起步的智能優(yōu)化算法，目前國內(nèi)外關于蜂群算法的文獻較少，研究范圍較窄，故本文不僅是拓寬蜂群算法應用范圍的有效嘗試，同時也給本身求解方法不多的軟時間窗車輛路徑問題提供了一種新解決方法。

關鍵詞:帶軟時間窗車輛路徑問題; 蜂群算法; 反應闕值; 刺激信號值

中圖分類號:TP18 文獻標識碼:A 文章編號:1003-5192(2010)06-0067-04

Wasp Colony Algorithm for Vehicle Routing Problem with Soft Time Windows

YANG Jin1， MA Liang2

(1.Science School， University of Shanghai for Science and Technology， Shanghai 200093， China; 2.Management School， University of Shanghai for Science and Technology， Shanghai 200093， China)

Abstract:This paper proposes a new algorithm， wasp colony algorithm， for vehicle routing problem with soft time windows. Series of benchmark problems are tested and verify the validity of the algorithm through comparing the results with the best known solutions of the VRPTW and the results of the ant algorithm. The wasp colony algorithm has just begun to develop and due to now it has been only used in few problems at home and abroad.Therefore this paper not only expands the application scope of the wasp colony algorithm but also gives a new method to solve the vehicle routing problem with soft time windows which solve methods are few.

Key words:vehicle routing problem with soft time windows;wasp colony algorithm;response threshold; stimulus value

1 引言

VRPSTW(Vehicle Routing Problem with Soft Time Windows)即軟時間窗車輛路徑問題[1]，它允許車輛對客戶開始服務的時間早于客戶允許的最早開始時間或晚于客戶允許的最遲開始時間，但是要給予一定的懲罰。我們知道，硬時間窗(VRPTW)不僅對服務造成很大的局限性，還會導致費用的增加。因為如果要嚴格遵守時間窗的限制開始服務，相對來講則要增加車輛數(shù)。考慮到現(xiàn)實生活中，有些客戶如果對其服務的時間不在他要求的范圍之內(nèi)，只要肯給予一定的賠償他會接受服務提前或延遲。對供應商來說，雖然這種服務方式增加了一定的懲罰費用，但如果能夠節(jié)省車輛，縮短路程，以此來減少人力、物力，則最終的總費用反而有可能減少。VRPSTW是在VRPTW基礎上結合實際改進產(chǎn)生的，也是VRP的一種擴展類型。VRPSTW同樣也是NP難題[2]。相對于硬時間窗，對軟時間窗的研究較少[3~8]。

參照VRPTW的定義，VRPSTW的一般提法為:已知有一批客戶，每個客戶點的位置坐標和貨物需求已知，車輛的負載能力一定，每輛車都從起點(Depot)出發(fā)，完成若干客戶點的運送任務后再回到起點。……