月旦知識庫
 
  1. 熱門:
 
首頁 臺灣期刊   法律   公行政治   醫事相關   財經   社會學   教育   其他 大陸期刊   核心   重要期刊 DOI文章
運輸學刊 本站僅提供期刊文獻檢索。
  【月旦知識庫】是否收錄該篇全文,敬請【登入】查詢為準。
最新【購點活動】


篇名
應用蟻群系統求解卡車與拖車途程問題
並列篇名
An Ant Colony System for Solving the Truck and Trailer Routing Problem
作者 喻奉天林宗漢盧宗成
中文摘要
本研究之目的在於利用蟻群系統(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題庫進行演算法之測試分析,並將結果與文獻中其他演算法所得之結果比較。結果顯示ACS可有效求解TTRP,尤其在顧客數少於150之測試題目,其結果更能顯示ACS在求解TTRP上之競爭力。
英文摘要
This study aims at applying ant colony system (ACS) to solve the truck and trailer routing problem (TTRP), a variant of the classic vehicle routing problem (VRP). In TTRP, a fleet of trucks and trailers is used to serve customers. Due to some practical constraints, some customers, called truck customers, can only be served by a single truck. Other customers that may be serviced by a single truck or a complete vehicle (i.e., a truck pulling a trailer) are vehicle customers. As a result, there are three types of routes in a TTRP solution, namely pure truck route, pure vehicle route, and complete vehicle route. Ant colony system is a meta-heuristic approach inspired by the phenomenon that ants can find the shortest path between a food source and their nest. Since ACS had been successfully applied to many hard combinatorial optimization problems, including the vehicle routing problem, this research develops a two-stage solution algorithm based on ACS to solve the TTRP. The nearest neighbor heuristic is used in the first stage to construct a good initial solution. The solution is then improved by using ACS and a series of route improvement heuristics, including 2-opt, swap, and insertion, in the second stage. The proposed ACS-based algorithm is implemented and tested on the benchmark TTRP problems given in the literature. We compare the results obtained by the proposed ACS-based algorithm and those obtained by other heuristics reported in the literature. The results demonstrate that the ACS-based algorithm is applicable and effective in solving the TTRP. In particular, for problem instances with less than 150 customers, the proposed heuristic is competitive with existing solution approaches.
起訖頁 199-218
關鍵詞 車輛途程問題卡車與拖車途程問題蟻群系統Vehicle routing problemTruck and trailer routing problemAnt colony system
刊名 運輸學刊  
期數 201106 (23:2期)
出版單位 中華民國運輸學會
該期刊-上一篇 大型事件疏散路網設計模型之研究
該期刊-下一篇 國人對低成本航空選擇意向之分析
 

新書閱讀



最新影音


優惠活動




讀者服務專線:+886-2-23756688 傳真:+886-2-23318496
地址:臺北市館前路28 號 7 樓 客服信箱
Copyright © 元照出版 All rights reserved. 版權所有,禁止轉貼節錄