本研究之目的在於利用蟻群系統 (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.