模糊車輛配送問題的改進螞蟻算法

摘要：模糊車輛配送問題是物流調度領域中一個具有現實意義的多目標FVRP問題。論文針對問題的特性，提出了一種結合啟發式初始種群以及推—碰撞—擲規則，并引進了服務緊急程度影響因子的改進螞蟻算法。實驗結果表明，改進螞蟻算法能夠得到較好的模糊車輛配送問題滿意解。

關鍵詞：螞蟻算法；模糊車輛路徑；車輛配送；多目標優化

中圖分類號：F506文獻標識碼：A文章編號：1002-3100(2008)02-0024-04

Abstract: Fuzzy vehicles distribution is a multi-objective FVRP optimization with practical significance in the field of logistics. In view of the problem's characteristics in this paper， an advanced ants algorithm is proposed， which combines the heuristic initial population method and push-bump-throw rules and introduces the service urgency factor. The experimental results show that the better satisfactory solutions to the fuzzy vehicles distribution can be gotten by the algorithm.

Key words: ants algorithm; fuzzy vehicle routing problem; vehicles distribution; multi-objective optimization

0引言

車輛路徑問題（Vehicle Routing Problem，VRP）最早于1959年由Dantzig和Ramser提出[1]。但在大多數VRP問題的研究中，所構造路徑的信息是確定的，包括路況交通、客戶信息、車輛信息等。而在實際應用當中，這些因素存在不確定性，如道路維修、交通堵塞。此外，客戶對于服務的時間滿意程度是不一樣的。在這些情況下，確切條件下的VRP理論和方法難以解決不確定、具有模糊特性的VRP問題。Cheng和Gen描述了模糊車輛調度問題（Fuzzy Vehicle Routing Problem，FVRP）[2-3]，客戶的偏好信息可表達為滿足服務時間意義上的模糊數。本文針對這種模糊特性，在傳統VRP問題和理論上提出了求解模糊車輛配送問題的一種新方法。

1問題描述與數學模型

式（2）表示最小化車輛數；式（3）表示最大化平均客戶滿意度；式（4）表示最小化總行駛路程；式（5）表示最小化總等待時間；式（6）確保對每個客戶的服務時間在時間容忍區間內；式（7）確保每輛車服務的客戶需求不超過它的能力；式（8）確保每個客戶只由一輛車服務；式（9）、（10）表示對于每個客戶，只有兩個客戶與它相連，車輛由一個直接駛向它，又由它直接駛向另一個；式（11）描述車輛k直接運行和顧客數的關系。可以看出，這是一個多目標優化的模型，考慮的目標有最小化車隊大小，最小化總行進路徑，最大化客戶滿意度，最小化車輛等待時間。這就需要在各個目標之間進行權衡。

2模糊車輛配送改進螞蟻算法的基本思想

螞蟻算法（Ant Colony Algorithm）[4]，是由意大利學者Dorigo和Maniezzo等提出的一種新的仿生優化算法，已經先后被應用到TSP問題、圖著色問題、車間調度等NP-Hard問題。螞蟻算法是依據各條路徑上的信息素分布濃度來選擇下個訪問的點。許多學者提出了改進的螞蟻算法，其中Thomas提出了Max-Min螞蟻算法[5]。MMAS算法能更好地避免算法出現過早停滯現象。本文結合模糊車輛配送問題特點，在MMAS算法基礎上進行改進。

2.1蟻群初始化

2.2狀態轉移

2.3最大化客戶滿意程度

一次分配之后，每條路徑是能力和時間上的可行調度。需要進一步確定每個客戶的最好服務時間以最大化客戶總滿意程度。這里采用推—碰撞—擲（Push-Bump-Throw）的規則[2-3]。在一個可行路徑中包含了一些緊路徑和松路徑。緊路徑指任何相鄰客戶間具有零等待時間順序的客戶列表；松路徑指任何相鄰客戶間具有非零等待時間順序的客戶列表。推—碰撞—擲過程掃描可行車輛路徑調度，試圖在緊路徑上找到可能的向前推動。

4實驗及分析

設有19個客戶和1個配送中心，隨機分布在邊長20公里的正方形區域內，配送中心位于坐標0，0處，每輛車的最大負荷為10t，車輛行駛速度為36kmh。實驗數據如表1：

通過120次迭代，得到了最好解，總距離89.3km客戶平均滿意度71％。可見，對于本文所研究的FVRP問題，利用改進后的螞蟻算法能夠實現找到滿意解。

5結論

模糊車輛配送問題是NP-hard難題，精確求解很困難，尤其對于多目標優化。螞蟻算法是一種來自生物界的隨機搜索尋優方法，是生物群體啟發行為，已經應用于TSP問題、二次分配等組合優化問題并取得很好的效果。本文針對FVRP問題，引用了啟發式的初始化方法、引入了服務緊急程度影響因子并結合推—碰撞—擲的方法等，對MMAS算法進行改進。實驗結果表明這種改進的螞蟻算法能夠找到滿意解，能夠較好地解決FVRP問題。

參考文獻：

[1]Bodin， L.， B. Golden， A. Assad， and M. Ball. Routing and scheduling of vehicles and crews; the state of the art[J]. Computers and Operations Research， 1983，10:62-212.

[2]Cheng， R. and M. Gen. Fuzzy vehicle routing and scheduling problem using genetic algorithm[J]. Genetic Algorithm and Soft Computing， 1996，13(6):683-709.

[3]Cheng， R. and M. Gen. Vehicle routing problem with fuzzy due-time using genetic algorithm[J]. Japanese Journal of Fuzzy Theory and System， 1995，7(5):1050-1061.

[4]Colorni. A， Dorigo. M， Maniezzo. V. Distributed Optimization by Ant Colonies[C] // A.Proceedings BCAL91. Proceedings of the First European Conference on Artificial Life. Paris， France: Elsevier Publishing， 1992:134-142.

[5]T. Stuetzle. The Max-Min Ant System and Local Search for the Traveling Salesman Problem[C] // Proceedings of the IEEE Conference on Evolution Computing， 1997:309-314.

[6]Gillett. B， Miller. L. A Heuristic Algorithm for the Vehicle Dispatch Problem[J]. Operations Research， 1974，22(2):340-349.

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