A Branch-and-Price-and-Cut Algorithm for the Vehicle Routing Problem with Two-Dimensional Loading Constraints
针对带二维装载约束的车辆路径问题，提出分支定价切割算法，通过新数据结构和优势规则处理装载约束，首次最优求解14个算例，将可解的大件实例规模扩大近一倍。
The vehicle routing problem with two-dimensional loading constraints (2L-CVRP) is a practical variant of the classic capacitated vehicle routing problem. A number of algorithms have been developed for the problem, but it is very difficult for the existing exact methods to optimally solve instances featuring with large rectangular items. To address this issue, a branch-and-price-and-cut (BPC) algorithm is proposed in this study. A novel data structure and a new dominance rule are developed to build an exact pricing algorithm that takes the loading constraints into account. Several valid inequalities are used to strengthen the linear relaxation. Extensive computational experiments were conducted on the benchmark instances of the 2L-CVRP, showing that the BPC algorithm outperforms all the existing exact methods for the problem in terms of the solution quality. Fourteen instances are solved to optimality for the first time. In particular, the size of solvable instances with large items is nearly doubled. Moreover, managerial insights about the impact of respecting the last-in-first-out constraint are also obtained.