An ant colony system (ACS) with a hybrid local search to solve vehicle routing problems

Abstract

This research applied an Ant Colony System algorithm with a hybrid local search to solve vehicle routing problems (VRP) from a single depot when the customer requirements are known. VRP is an NP-hard optimization problem and has been successfully optimised using heuristics. A fleet of vehicles of a specific capacity are used to serve a number of customers at minimum cost, without violating the constraints of vehicle capacity. There are meta-heuristic approaches to solve these problems, such as Simulated Annealing, Genetic Algorithm, Tabu Search and the Ant Colony System algorithms. In this case, a hybrid local search was used (Cross-Exchange, Or-Opt and 2-Opt algorithm) with an Ant Colony System algorithm. The experimental design was tested on seven different problems from an online data set in the OR-Library. In five different problems, customers and the depot were randomly distributed in an approximately central location. The customers were grouped into clusters. The results were evaluated in terms of optimal routes using optimal distances. The experimental results are compared with those obtained from meta-heuristics and they show that the proposed method outperformed six meta-heuristics that have been presented in the literature.