A population based simulated annealing algorithm for capacitated vehicle routing problem

Abstract

The Vehicle Routing Problem (VRP) is one of the most discussed and researched topics nowadays. The VRPis briefly defined as the problem of identifying the best route to reduce distribution costs and improve the quality ofservice provided to customers. The Capacitated VRP (CVRP) is one of the most commonly researched among the VRPtypes. Therefore, the CVRP was studied in this paper and a new population based simulated annealing algorithm wasproposed. In the algorithm, three different route development operators were used, which are exchange, insertion andreversion operators. It was tested on 63 well-known benchmark instances in the literature. The results showed that theoptimum routes could be determined for the 23 instances.