A general purpose algorithm for a class of vehicle routing problems: A benchmark analysis on literature instances

The aim of this work is to analyse the computational performances of a general-purpose heuristic capable of solving a large class of Vehicle Routing Problems. The general Ruin and Recreate (R&R) framework of the algorithm is discussed, with particular attention on some of the removal and insertion operators used in the implementation. The benchmark analysis is then performed using standard benchmark instances of three different routing problems. Before analyzing the algorithm, a definition of the problem is provided together with some mathematical formulations. Exact methods are briefly discussed, whereas an exhaustive presentation of the most famous (meta)heuristic approaches is given. The obtained results show that the algorithm returns good solutions for almost all the different problem variants with up to 500 customers.