應用螞蟻演算法於時窗限制車輛途程問題之研究

Solving the Vehicle Routing Problem with Time Windows Using Ant Algorithm

時窗限制車輛途程問題（Vehicle Routing Problem with Time Windows,VRPTW）在實務上已有廣泛的應用，並有許多學者進行求解與探討。在過去研究中，最常採用的求解演算法為模擬退火法（Simulated Annealing,SA）、基因演算法（Genetic Algorithms,GAs）與禁忌搜尋法（Tabu Search,TS）等巨集啟發式演算法。螞蟻演算法（Ant Algorithm）為根據螞蟻族群搜尋食物的現象，所發展而成的巨集啟發式演算法；許多學者針對螞蟻演算法進行改良與修正，並應用於許多組合最佳化問題。因此，本研究發展一改良式群蟻系統（Improved Ant Colony System,IACS）演算法，採用新的途程建構準則、費洛蒙更新方式與區域搜尋法，並應用於求解VRPTW。最後，求解Solomon的VRPTW測試例題並進行參數分析，且比較改良式群蟻系統與其他演算法之績效。根據結果發現，IACS更新了21題文獻最佳解，且所求得的總途程距離較其他演算法少。

The Vehicle Routing Problem with Time Windows (VRPTW) has been applied extensively in practice. Many researchers have discussed and solved the VRPTW with meta-heuristic approaches, such as the Simulated Annealing, Genetic Algorithms and Tabu Search, to find the (near-) optimal solutions within reasonable time. Ant algorithm is a newer meta-heuristic algorithm that was developed based on ant's behaviors for food searching. Many researchers have revised the ant algorithm and applied it successfully to many combinatorial problems. The objective of this research is to improve the ant colony system and apply it to the VRPTW. We introduced the framework of an improved ant colony system (IACS) including a new route construction rule, a new pheromone update rule and local search approaches. We tested the IACS with 56 Solomon VRPTW problems and compared the performance against those of other meta-heuristic approaches. Based on the computational results, IACS updates