AN IMPROVED ANT COLONY SYSTEM ALGORITHM FOR THE VEHICLE ROUTING PROBLEM

Abstract

ABSTRACT 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.