Constrained Clustering for the Capacitated Vehicle Routing Problem (CC-CVRP)
Francesco Alesiani, Gülçin Ermiş, Konstantinos Gkiotsalitis
Abstract
eCommerce, postal and logistics' planners require to solve large-scale capacitated vehicle routing problems (CVRPs) on a daily basis. CVRP problems are NP-Hard and cannot be easily solved for large problem instances. Given their complexity, we propose a methodology to reduce the size of CVRP problems that can be later solved with state-of-the-art optimization solvers. Our method is an efficient version of clustering that considers the constraints of the original problem to transform it into a more tractable version. We call this approach Constrained Clustering Capacitated Vehicle Routing Solver (CC-CVRS) because it produces a soft-clustered vehicle routing problem with reduced decision variables. We demonstrate how this method reduces the computational complexity associated with the solution of the original CVRP and how the computed solution can be transformed back into the original space. Extensive numerical experiments show that our method allows to solve very large CVRP instances within seconds with optimality gaps of less than 16%. Therefore, our method has the following benefits: it can compute improved solutions with small optimality gaps in near real-time, and it can be used as a warm-up solver to compute an improved solution that can be used as an initial solution guess by an exact solver.