Federico Michelotto (University of Bologna)
Invited by Daniele Catanzaro

will give a presentation on :

A parallel metaheuristic framework for the Capacitated Vehicle Routing Problem

Abstract : 

The Capacitated Vehicle Routing Problem (CVRP) is one of the most studied combinatorial optimization problems which can be described as follows. Given a set of customers, each of which with a known location and demand, and a fleet of homogeneous vehicles with fixed capacity, the goal of the CVRP is to find the minimum cost set of routes, so that each customer is served by exactly one vehicle and the capacity constraints for the vehicles are satisfied. Given the inherent computational difficulty and practical relevance of the problem, several successful heuristics and metaheuristics have been proposed for its solution. However, almost all methods proposed in the literature for solving the CVRP are sequential algorithms. Despite the impressive results achieved by recent metaheuristic methods on large-scale instances, the sequential nature of these algorithms becomes a fundamental limitation when the goal is to efficiently solve instances with thousands or more customers. Therefore, this work aims to propose an effective and paradigmatic parallel metaheuristic framework for large-scale instances of the CVRP. We show that it is possible to obtain equivalent solutions’ quality with an approximately linear speed-up with respect to one of the most efficient state-of-the-art metaheuristic for the CVRP.