Solving the capacitated vehicle routing problem using the ALGELECT electrostatic algorithm

Abstract

The capacitated vehicle routing problem (CVRP) with a single depot is a classic routing problem with numerous real-world applications. This paper describes the design, modelling and computational aspects of ALGELECT (electrostatic algorithm), a new algorithm for the CVRP. After some general remarks about the origin of the algorithm and its parameters, a parameter tuning process is carried out in order to improve its efficiency. The algorithm is then explained in detail and its main characteristics are presented. Thus, ALGELECT develops good-quality solutions to the CVRP, in terms of the number of scheduled routes and the load ratio of the delivery vehicles. Finally, ALGELECT is used to find solutions for some Solomon's and Augerat's instances, which are then compared to solutions generated by other well-known methods.

Keywords:

• distribution
• heuristics
• logistics
• transport
• vehicle routing

Acknowledgements

We would like to express our gratitude for the support given by Vicente Inglada and the Spanish Government Ministry of Transport (Ministerio de Fomento) to this research. Similarly, we would like to thank two anonymous referees for their valuable comments, which have significantly improved this paper.