An Improved Ant Colony System Algorithm for the Vehicle Routing Problem

應用改良式群蟻系統演算法於車輛途程問題之研究

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

《工業工程學刊》 23卷2期 (2006/03) Pp. 115-126

https://doi.org/10.29977/JCIIE.200603.0003

摘要

車輛途程問題(Vehicle Routing Problem; VRP)是近五十年來，一個非常著名的組合最佳化問題，過去已有許多學者針對VRP進行求解與探討。很多萬用啓發式演算法(Meta-heuristic)已被應用於求解VRP，如模擬退火法(Simulated Annealing; SA)、基因遺傳演算法(Genetic Algorithms; GA)、禁忌搜尋法(Tabu Search; TS)與螞蟻演算法(Ant Algorithm)等。其中，螞蟻演算法為90年代根據螞蟻族群搜尋食物的現象，所發展而成的萬用啓發式演算法。現今，已有越來越多的學者針對螞蟻演算法進行改良與修正，並應用於許多組合最佳化問題。因此，本研究提出一改良式的群蟻系統演算法(Ant Improved colony System, IACS)，其採用新的途程建構準則、費洛蒙(Pheromone)更新方式與多種區域搜尋法(Local Search)，以改善傳統螞蟻演算法求解VRP之品質。本研究求解14題VRP之標竿測試例題，並將求解結果與SA、GA、TS及其它已發表之螞蟻演算法進行比較。比較結果顯示，IACS之求解品質優於其它已發表之螞蟻演算法，且不遜於其它比較之萬用啓發式演算法。

關鍵字

車輛途程問題 ； 萬用啓發式演算法 ； 群蟻系統演算法

並列摘要

The vehicle routing problem (VRP), a well-known combinatorial optimization problem, holds a central place in logistics management. Many meta-heuristic approaches like Simulated Annealing (SA), Genetic Algorithms (GA), Tabu Search (TS), and Ant Colony Optimization (ACO) have been proposed to solve VRP. Ant Algorithm is a distributed meta-heuristic approach that has been applied to various combinatorial optimization problems, including traveling salesman problem, quadratic assignment problem. In this research, we proposed an improved ant colony system (IACS) algorithm that possesses a new state transition rule, a new pheromone updating rule and diverse local search approaches. The computational results on 14 VRP benchmark problems show that our IACS yields better solutions than those of other ant algorithms in the literature and is competitive with other meta-heuristic approaches in terms of solution quality.

並列關鍵字

vehicle routing problem ； meta-heuristic ； ant colony system

參考文獻

Alfa, A. S.,S. S. Heragu,M. Chen(1991).A 3-opt based simulated annealing algorithm for vehicle routing problems.Computers & Industrial Engineering.21,635-639.

Baker, B. M.,M. A. Ayechew(2003).A genetic algorithm for the vehicle routing problem.Computers & Operations Research.30,787-800.

Bullnheimer, B.,R. F. Hartl,C. Strauss,S. Voss,S. Martello,I.H. Osman,C. Roucairol(1998).Applying the ant system to the vehicle routing problem.Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization.109-120.

Bullnheimer, B.,R. F. Hartl,C. Strauss(1999).An improved ant system for the vehicle routing problem.Annals of Operations Research.89,319-328.

Bullnheimer, B.,R. F. Hartl,C. Strauss(1999).A New Rank Based Version of the Ant System - A Computational Study.Central European Journal of Operations Research.7,25-38.