應用蟻群系統求解卡車與拖車途程問題

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.