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

Solving the Vehicle Routing Problem with Time Windows Using Ant Algorithm

陳家和(Chia-Ho Chen) ； 丁慶榮(Ching-Jung Ting)

《運輸學刊》 17卷3期 (2005/09) Pp. 261-280

https://doi.org/10.6383/JCIT.200509.0261

摘要

時窗限制車輛途程問題(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 21 best-known solutions and is competitive with other meta-heuristic algorithms.

並列關鍵字

Vehicle routing problem with time windows ； Meta-heuristic ； Ant colony system ； Pheromone ； Local search

參考文獻

Berger, J.,Barkaoui, M.,Bräysy, O.(2001).A Parallel Hybrid Genetic Algorithm for the Vehicle Routing Problem with Time Windows.Canada:Working Paper, Defense Research Establishment Valcartier.

Bullnheimer, B.,Hartl, R. F.,Strauss, C.(1998).Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization.Kluwer, Boston, MA.

Bullnheimer, B.,Hartl, R. F.,Strauss, C.(1999).An Improved Ant System for the Vehicle Routing Problem.Annals of Operations Research.89,319-328.

Chiang, W. C.,Russell, R. A.(1997).A Reactive Tabu Search Metaheuristics for the Vehicle Routing Problem with Time Windows.INFORMS Journal on Computing.9,417-430.

Clarke, G.,Wright, J. W.(1964).Scheduling of Vehicles from a Central Depot to a Number of Delivery Points.Operations Research.12,568-581.