April 07, 2022, 11:40 AM - 12:00 PM
Francesco Cavaliere, University of Bologna
: 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.