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

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

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

中圖分類號: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)不僅對服務造成很大的局限性，還會導致費用的增加。因為如果要嚴格遵守時間窗的限制開始服務，相對來講則要增加車輛數。考慮到現實生活中，有些客戶如果對其服務的時間不在他要求的范圍之內，只要肯給予一定的賠償他會接受服務提前或延遲。對供應商來說，雖然這種服務方式增加了一定的懲罰費用，但如果能夠節省車輛，縮短路程，以此來減少人力、物力，則最終的總費用反而有可能減少。VRPSTW是在VRPTW基礎上結合實際改進產生的，也是VRP的一種擴展類型。VRPSTW同樣也是NP難題[2]。相對于硬時間窗，對軟時間窗的研究較少[3~8]。

參照VRPTW的定義，VRPSTW的一般提法為:已知有一批客戶，每個客戶點的位置坐標和貨物需求已知，車輛的負載能力一定，每輛車都從起點(Depot)出發，完成若干客戶點的運送任務后再回到起點。假設每個客戶被而且只被訪問一次，每輛車所訪問的客戶的需求總和不能超過車輛的負載能力。每個客戶i帶有一個時間窗[ei，li]，ei為客戶i允許服務的最早開始時間，li為客戶i允許服務的最晚開始時間，車輛對客戶的服務時間必須在這個范圍內。如果車輛早于ei或者晚于li到達客戶i，仍可服務，但必須給予客戶一定的賠償。問題的最終目標是以最小的總費用完成所有任務。本文的總費用設為是關于車輛數，總路程，總懲罰費用的函數。

至于給予客戶的賠償，可以根據客戶的要求或者重要性不同而有所不同。比如有些特別緊急的、對時間要求比較苛刻的客戶，其懲罰費用系數可能相對較大;而相對要求沒那么嚴格的客戶其懲罰費用系數則相對較小，以此來體現放松時間窗對總費用的影響。

2 數學模型

其中|S|為集合S中所含圖G的頂點個數，約束(a)為車輛負載限制;約束(b)則保證每輛車對每個客戶只能訪問一次;約束(c)、(d)、(e)則是為了保證能形成回路;約束(f)表示一條線路上兩鄰接任務存在的條件。目標為以最小的總費用完成所有任務，其中A，B(A0，B0)分別表示所需車輛數和總路程及總懲罰費用在總費用中的權重系數。

3 蜂群算法(Wasp Colony Algorithm)

3.1 基本原理

蜜蜂是社會化的昆蟲群體，蜜蜂個體可以擔任不同的角色，能夠完成覓食，照顧后代和御敵等工作，并且能夠自發地在這些角色之間進行轉換。目前國外對蜂群群體智能研究的機構主要是卡內基-梅隆大學的機器人研究所。Theraulaz通過對一種俗稱叫歐洲紙蜂的黃蜂的研究，提出了建立在反應闕值變化基礎上的黃蜂與環境之間的信息交互實現任務分配的模型[10~12]。在該模型中，蜜蜂根據反應闕值和外界的刺激信號來自行安排為幼蟲覓食的工作。對蜂巢中的每個區域，蜜蜂都有相應的反應闕值;同時蜂巢中每個區域內的幼蟲也會給蜜蜂相應的刺激信號。蜜蜂對某個區域的反應闕值越低，或者這個區域內的幼蟲給蜜蜂的刺激信號值越高時，蜜蜂為這個區域內的幼蟲采集食物的概率就越高[13~15]。

4 實例求解與分析

由于VRPSTW沒有現成的測試數據庫，大部分軟時間窗文獻采用的是隨機數據，為了通用性，因此本文還是采用Solomon的標準測試問題。本文算法在Windous XP用Miscroft Visual Studio 2005求解了國際上公開的Solomon提供的VRPTW測試問題。由于采用標準測試問題，故本文將算法結果與VRPTW的最好解進行比較。另外，VRPSTW沒有很多使用標準測試問題的結果可以比較，故本文僅將算法結果與同樣用標準問題測試的蟻群算法結果作比較和分析。經過大量的測試實驗，說明了該算法在帶軟時間窗車輛路徑問題上的有效性，因為已知最好解通常都是幾種啟發式算法嵌套甚至是借助于某些經典算法所求得的結果。而且本文蜂群算法的結果也大大優于運用比較成熟的蟻群算法的結果。從時間復雜性來看，本文的蜂群算法的時間復雜性為O(m#8226;n2)。隨著問題規模的增大，可以通過人為控制循環次數來限制算法的運行時間。

限于篇幅，這里僅能給出一部分比較結果(見表1)，由表中可以看出，在軟時間窗問題中，可以通過少量的懲罰費用而達到同時減少較多車輛數，減少一定車輛總行程的效果。因此雖然增加了一定的懲罰費用，但因為車輛數和車輛總行程的減少反而可能導致總費用減少。因此實際問題的求解中，決策者可以依據車輛的固定費用、車輛的行駛費用以及顧客要求的懲罰費用等來決定各個因素的費用系數，從而調控最后的總費用。

5 結論

軟時間窗的車輛路徑問題是在考慮到硬時間窗對服務造成的不便以及容易引起車輛資源浪費的情況下，對VRPTW的一種改進類型。VRPSTW由于沒有一個完全統一的提法和標準測試庫，目前對VRPSTW研究的文獻著重點和方法也各不相同。因此，對于VRPSTW的求解沒有VRPTW那么多求解方法和結果供參考和比較[17~19]。從實驗結果來看，蜂群算法可作為解決本身解決方法不多的VRPSTW問題的又一種新的可行手段。另外，目前國內外關于蜂群算法的文獻較少，且應用范圍較窄，故本文不失為是拓寬蜂群算法應用范圍的一種有效的嘗試。

參 考 文 獻:

[1]Koskosidis Y A， Powell W B， Solomon M M. An optimization-based heuristic for vehicle routing and scheduling with soft time window constraints[J]. Transportation Science， 1992， 26(2): 69-85.

[2]Solomon M M. Algorithms for the vehicle routing and scheduling problems with time windows constraints

[J]. Operations Research， 1987， 3(5): 254-265.

[3]Ioannou G， Kritikos M， Prastacos G. A problem generator solver heuristic for vehicle routing with soft time windows[J]. Omega， 2003， 31: 41-53.

[4]Colorni A， et al.. Heuristics from nature for hard combinatorial optimization problems[J]. International Transcations in Operational Research， 1996， 3(1): 1-21.

[5]賓松，符卓.求帶軟時間窗的車輛路徑問題的改進遺傳算法[J].系統工程，2003，21(6):12-15.

[6]肖雁，符卓.帶軟時間窗的車輛路徑問題及其應用前景探討[A].中國運籌學會第六屆學術交流會論文集[C].香港:Global-Link出版社，2000.634-638.

[7]劉誠，陳治亞，封全喜.帶軟時間窗物流配送車輛路徑問題的并行遺傳算法[J].系統工程，2005，23(10):7-11.

[8]張海剛，顧幸生，徐震浩.基于免疫算法的帶軟時間窗車輛調度問題[J].華東理工大學學報(自然科學版)，2007，33(1):104-107.

[9]Balakrishnan N. Simple heuristics for the vehicle routing problem with soft time windows[J]. Journal of the Operational Research Society， 1993， 44(3): 279-287.

[10]Theraulaz G， Bonabeau E， Deneubourg J L. Response threshold reinforcement and division of labour in insect societies[A]. Proceedings of the Royal Society of London B[C]. PMC， USA， 1998. 327-335.

[11]Theraulaz G， Bonabeau E， Deneubourg J L. Self-organization of hierarchies in animal societies: the case of the primitively eusocial wasp polistes dominulus christ[J]. Journal of Theoretical Biology， 1995， 174: 313

-323.

[12]Cicirello V A， Smith S F. Wasp nests for self-configurable factories[A]. Proceedings of the Fifth International Conference on Autonomous Agents[C]. ACM Press， 2001. 473-480.

[13]Theraulaz G， Goss S， Gervet J， et al.. Task differentiation in polistes wasp colonies: a model for self-organizing groups of robots[A]. From Animals to Animals: Proceedings of the First International Conference on Simulation of Adaptive Behavior[C]. MIT Press， 1991.346-355.

[14]Bonabeau E， Sobkow ski A， Theraulaz G， et al.. Adaptive task allocation inspired by a model of division of labor in social insects[A]. In Lundh D， Olsson B， eds. Proceeding of Biocomputing and Emergent Computing[C].World Scientific， Singapore， 1997. 36-45.

[15]Cicirello V A， Smith S F. Improved routing wasps for distributed factory control[A]. IJCAI-01 Workshop on AI and Manufacturing[C]. Aiedam Press， Massachusetts(USA)， 2001. 26-32.

[16]馬良，朱剛，寧愛兵.蟻群優化算法[M].北京:科學出版社，2008.

[17]Laporte G. The vehicle routing problem: an overview of exact and approximation algorithms[J]. European Journal of Operational Research， 1992， 5(9): 345-358.

[18]Dorigo M， Maniezzo V， Colorni A. Ant system: Optimization by a colony of cooperation agents[J]. IEEE Transactions on Systems， Man， and Cybernetics， 1996， 26(1): 29-41.

[19]Kolen A W J， Kan A H G R， Trienekens H W J M. Vehicle routing with time windows[J]. Operations Research， 1987， 3(5): 266-273.