Luca Accorsi, University of Bologna

Abstract

This paper describes FSP4D, an effective approach for the solution of Capacitated Vehicle Routing Problem instances primarily designed for the 12th DIMACS implementation challenge. FSP4D employs an iterative part in which a fast optimization based on the iterated local search paradigm is combined with a simulated annealing diversification strategy. During this part, routes are collected into a pool. A set partitioning heuristic is then used to identify high-quality combinations of these routes. The iterative optimization and the set partitioning resolution are repeated several times following a repetitive schema. Experimental results show that the proposed approach is able to obtain small average primal integral values for most of the benchmark instances tested.

[Challenge Paper]   [Video]