Francesco Cavaliere, University of Bologna

Abstract

: In our work, an effective refining heuristic algorithm for large-scale instances of Vehicle Routing Problems has been developed. The technique consists in a local search step entangled with restricted Set Partitioning problem optimization. Helsgaun’s LKH-3 algorithm has been used for the local search phase, with a number of acceleration techniques to improve its performance. The restricted Set Partitioning formulation is solved by means of a novel Set Partitioning heuristic inspired by the technique proposed by Caprara et al for the Set Covering problem. The resulting algorithm has been able to improve many best-known solutions for both CVRP and VRPTW instances used in the DIMACS 12th Implementation Challenge.

[Challenge Paper]   [Video]