应用蚂蚁演算法求解卡车与拖车途程问题.PDFVIP

論文檔案名稱請依下列方式編輯： 運輸網路 _0101_林宗漢_應用螞蟻演算法求解卡車與拖車途程問題 中華民國運輸學會 97 年 學術論文國際研討會 中 華 民 國 9 7 年 1 2月 應用螞蟻演算法求解卡車與拖車途程問題 An Ant Colony System for Solving the Truck and Trailer Routing Problem 林宗漢 Tsung-Han Lin1 喻奉天 Vincent F. Yu2 盧宗成 Chung-Cheng Lu3 摘要 本研究之目的在於利用蟻群系統(Ant Colony System, ACS)求解卡車 與拖車途程問題（Truck and Trailer Routing Problem, TTRP ）。TTRP是傳 統車輛途程問題（Vehicle Routing Problem, VRP ）之延伸，TTRP應用卡 車和拖車的組合來服務顧客，受限於實際環境的考量，某些顧客只能被 單一卡車服務 稱為卡車顧客( ) ，其他顧客則可以被單一卡車或整車( 亦即 卡車加掛拖車服務，因此被稱為整車顧客。由於這種特殊的服務方式，) TTRP的路徑有三種可能：卡車路徑、整車路徑和組合路徑。 ACS 是依據螞蟻在覓食，能夠尋找最短路徑之特性而發展出之萬用 啟發式演算法，已被成功地應用於求解許多困難的組合最佳化問題，包 括 VRP ，因此本研究以ACS 為基礎，發展出一種兩階段演算法以求解 TTRP 。在第一階段中，ACS被用來建構較佳之初始路徑；第二階段則是 利用 2-opt 、swap和 insert 三種啟發式演算法來改善這些初始 TTRP路徑。 本研究以過去文獻中之 TTRP題庫進行演算法之測試分析，並將所得之 研究結果與其他演算法比較。結果顯示 ACS可有效求解 TTRP 。尤其在 顧客數小於 150之測試題目，其結果更能顯示 ACS在求解 TTRP 上之競 爭力。 關鍵詞 ：車輛途程問題、卡車與拖車途程問題、螞蟻演算法 Abstract This study aims at applying ant colony system (ACS) to solving the truck and trailer  1國立高雄第一科技大學運籌管理系碩士 2國立臺灣科技大學工業管理系助理教授（聯絡地址： 106台北市基隆路四段 43號，電話： 02 ，E-mail:vincent@.tw ） 3國立高雄第一科技大學運籌管理系助理教授 1 論文檔案名稱請依下列方式編輯： 運輸網路 _0101_林宗漢_應用螞蟻演算法求解卡車與拖車途程問題 routing problem (TTRP), a variant of the well‐known vehicle routing problem (VRP). In TTRP,  a fleet  of trucks and trailers are used to service customers. Due to some practical constraints,  some customers, called truck customers, can only be serviced by a single truck. Other  customers that may be serviced by a single truck or a complete vehicle (i.e., a truck pulling a