蟻群最佳化演算法於載重限制之車輛途程問題的研究

羅敏華(Min-Hua Luo)

指導教授 ： 梁韵嘉

元智大學/工程學院/工業工程與管理學系/碩士(2003年)

摘要

為了貫徹螞蟻演算法之中心思想，本研究嘗試模擬螞蟻實際覓食方式，提出同時釋放並且同時行進之螞蟻建構路線模式，以節省法(Savings)建構初始路線，蟻群最佳化演算法(Ant Colony Optimization, ACO)求解具車輛容量與車輛路線長度限制之車輛途程問題(The Vehicle Routing Problem under Capacity and Distance Constraints, DCVRP)，以5隻螞蟻建構所有之問題路線，並且以2-opt交換法做鄰近解搜尋，直到無法再進行改善後停止，加入候選人名單(Candidate List)，以減少計算時間同時達到事先淘汰不良路徑的目的。本研究根據Bullnheimer 等學者(1999)之研究文獻中的測試問題，選擇以Christofides 等學者(1979)於1979年所提出之標準測試例題進行測試，並將其結果與其他方法做比較，發現本研究在具路線長度限制之問題中，明顯優於ASold (Bullnheimer 等學者,1999)、AS(Bullnheimer 等學者,1998)與SavingsAnt(Doerner等學者,2002)三種螞蟻方法，與四種傳統啟發式方法表較中ACO-DCVRP表現最好，在萬用啟發式方法中，ACO-DCVRP之結果亦明顯優於另外四種啟發式方法：Taburoute(Gendreau 等學者,1994)、Osman’s Ts(Osman,1993)、GTS(Toth等學者,1998)與SA (Osman ,1993)。

關鍵字

蟻群最佳化演算法 ； 車輛途程 ； 2-opt交換法 ； 鄰近解搜尋

並列摘要

無資料

並列關鍵字

HASH(0x9d4ff6c)

參考文獻

A. S. Alfa, S. S. Heragu, and M. Chen, “A 3-opt Based Simulated Annealing Algorithm for Vehicle Routing Problem,” Computers & Industrial Engineering, vol. 21, pp. 635-639, 1991.

J. E. Beasley, “Route-First Cluster-Second Methods for Vehicle Routing,” Omega, vol. 11, pp. 403-408, 1983.

L. Bodin and L. Berman, “Routing and Scheduling of school buses by computer,” Transportation Science, vol. 13, no. 2, pp. 113-129, 1979.

L. Bodin and S. Kursh, “A detailed Description of a Street Sweeper Routing and Scheduling System,” Computers and Operations Research, vol. 6, pp. 191-198, 1979.

L. Bodin and S. Kursh, “A Computer-Assisted System for the Routing and Scheduling of Street Sweepers,” Operations Research, vol. 26, no. 4, pp. 525-537, 1978.