Applying the Ant System to the Vehicle Routing Problem

In this paper we use a recently proposed mataheuristic, the Ant System, to solve the Vehicle Routing Problem in its basic form, i.e., with capacity and distance restrictions, one central depot and identical vehicles. A "hybrid" Ant System algorithm is first presented and then improved using problem-specific information (savings, capacity utilization). Experiments on various aspects of the algorithm and computational results for fourteen benchmark problems are reported and compared to those of other metaheuristic approaches such as Tabu Search, Simulated Annealing and Neural Networks.