A branch-and-cut algorithm for the vehicle routing problem with two-dimensional loading constraints

In this study, we develop a branch-and-cut algorithm for the vehicle routing problem with twodimensional loading constraints. A separation algorithm is proposed to simultaneously identify infeasible set inequalities and weak capacity inequalities for fractional solutions. Classic capacitated vehicle routing problem (CVRP) inequalities are adopted as well. A branch-and-cut (B&C) algorithm is built to solve the problem. Experimental results illustrate that the algorithm is competitive. In particular, we solve 6 instances to optimality for the first time. Extensive computational analysis is also conducted to reveal the impact of infeasible set inequalities, the branching strategy, and the packing algorithms on the B&C algorithm. (c) 2022 Elsevier B.V. All rights reserved.

Automated summary

In this study, a branch-and-cut algorithm is developed for the vehicle routing problem with two-dimensional loading constraints. The algorithm is shown to be competitive through experimental results, and extensive computational analysis is conducted to investigate the impact of different factors on the algorithm.