BRANCH-CUT-AND-PRICE ALGORITHM FOR THE EXACT SOLUTION OF THE VEHICLE ROUTING PROBLEM WITH CAPACITY CONSTRAINTS
DOI:
https://doi.org/10.34185/1991-7848.itmm.2026.01.044Keywords:
CVRP, vehicle routing, branch-cut-and-price, column generation, set partitioning, combinatorial optimization, integer programming, linear relaxation, exact and heuristic methods, logisticsAbstract
The paper presents an implementation of a branch-cut-and-price algorithm for the exact solution of the Capacitated Vehicle Routing Problem (CVRP). It combines a set-partitioning formulation, a Clarke-Wright-based initial heuristic, the generation of negative reduced-cost routes, and rounded capacity inequalities. Within the column-generation procedure, the algorithm first attempts to find new routes by a faster heuristic search; under certain algorithm settings, this search uses a simplified check that a route does not revisit customers. If no new routes are found in this way, the algorithm performs an exact search for routes without repeated customer visits before terminating column generation. On standard CVRP instances with 16 to 60 vertices, including the depot, the implementation matched the known optimal values.
References
Archetti C., Coelho L.C., Speranza M.G., Vansteenwegen P. Beyond fifty years of vehicle routing: Insights into the history and the future. European Journal of Operational Research. 2026. Vol. 330, No. 2. P. 355-372. DOI: 10.1016/j.ejor.2025.06.014.
Costa L., Contardo C., Desaulniers G. Exact Branch-Price-and-Cut Algorithms for Vehicle Routing. Transportation Science. 2019. Vol. 53, No. 4. P. 946-985. DOI: 10.1287/trsc.2018.0878.
Feillet D., Dejax P., Gendreau M., Gueguen C. An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems. Networks. 2004. Vol. 44, No. 3. P. 216-229. DOI: 10.1002/net.20033.
Fukasawa R., Longo H., Lysgaard J., Poggi de Aragao M., Reis M., Uchoa E., Werneck R.F. Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem. Mathematical Programming. 2006. Vol. 106, No. 3. P. 491-511. DOI: 10.1007/s10107-005-0644-x.
Baldacci R., Christofides N., Mingozzi A. An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Mathematical Programming. 2008. Vol. 115, No. 2. P. 351-385. DOI: 10.1007/s10107-007-0178-5.
Pecin D., Pessoa A., Poggi M., Uchoa E. Improved branch-cut-and-price for capacitated vehicle routing. Mathematical Programming Computation. 2017. Vol. 9, No. 1. P. 61-100. DOI: 10.1007/s12532-016-0108-8.
All Instances – CVRPLIB. GALGOS – Algorithms, Optimization and Simulation Group. URL: https://galgos.inf.puc-rio.br/cvrplib/index.php/en/instances (date of access: 02.04.2026).
