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

羅敏華(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)

參考文獻

徐明輝，多部車一般車輛途程解算法之研究，私立元智大學，碩士論文，1997。

陳坤賓，模擬退算法應用於車輛途程問題之研究，私立元智大學，碩士論文，1998。

廖亮富，含時間窗限制多部車車輛途程問題解算之研究，私立元智大學，碩士論文，1998。

敖君瑋，禁制搜尋法於軟性時窗限制之車輛問題研究，私立元智大學，碩士論文，1999。

H. Kawamura, M. Yamamoto, T. Mitamura, K. Suzuki, and A. Ohuchi, “Cooperative Search on Pheromone Communication for Vehicle Routing Problems,” IEEE Transactions on Fundamentals, E81-A, pp. 1089-1096, 1998.