Exact and Heuristic Algorithms for Capacitated Vehicle Routing Problems with Quadratic Costs Structure

In this article we introduce the quadratic capacitated vehicle routing problem (QCVRP) motivated by two applications in engineering and logistics: the capacitated vehicle routing problem with angle penalties (angle-CVRP) and the capacitated vehicle routing problem with reload costs (CVRP-RC). We introduce a three-index vehicle-flow formulation of the problem, which is strengthened with valid inequalities, and we derive a branch-and-cut algorithm capable of providing tight lower bounds and solving small- to medium-size instances in short to moderate computing times. Furthermore, we present a hybrid metaheuristic capable of providing high quality solutions in short computing times. The two algorithms are tested on several instances from the CVRP literature modified to mimic the two problems that motivate our study.