Implementation and study of a branch-cut-and-price algorithm for the Capacitated Vehicle Routing Problem

Abstract

The Capacitated Vehicle Routing Problem is a classical optimization problem arising in transportation logistics. Modern research addresses it with both heuristic and exact approaches. Among exact methods, the most effective ones are based on a set-partitioning formulation, column generation, cutting planes, and branching. Important components of such schemes are the exact solution of the route-generation subproblem as an Elementary Shortest Path Problem with Resource Constraints (ESPPRC) and the use of rounded capacity inequalities to strengthen the linear relaxation. At the same time, building an implementation in which these components interact consistently remains a technically demanding task.

The aim of the study is to apply a branch-cut-and-price algorithm for the exact solution of the Capacitated Vehicle Routing Problem, to explain how its main components are coordinated, and to validate the implementation on standard benchmark instances.

In the proposed implementation, each feasible route is treated as a variable of a set-partitioning model. An initial transportation plan is constructed by a Clarke-Wright-based heuristic. The algorithm then proceeds within the branch-cut-and-price framework: a restricted master problem is solved and new negative reduced-cost routes are generated. To accelerate computations, the implementation first applies a heuristic search; if it finds no improving columns, the algorithm switches to an exact certifying stage. The route-generation subproblem is formulated as an ESPPRC and solved by dynamic programming with label extension. Rounded capacity inequalities are used to improve the linear relaxation, and branching is performed on arcs. Computational experiments were carried out on eleven standard instances with 16 to 60 vertices, including the depot. Each instance was solved in ten sequential runs, and the article reports the average runtime. In every reported case, the implementation matched the known optimal values.

The study shows that the proposed implementation of branch-cut-and-price operates correctly on the considered set of standard instances and reproduces the known optimal solutions. The reported results confirm the practical applicability of this computational organization for small and medium-sized instances. Further work should focus on adapting the implementation to larger instances and improving the most time-consuming components of the method.