Exact methods for the split delivery vehicle routing problem with two-dimensional loading constraints

Abstract

The Split Delivery Vehicle Routing Problem with Two-dimensional Loading Constraints (2L-SDVRP) integrates vehicle routing, split delivery, and two-dimensional packing constraints. In the 2L-SDVRP, customers can be served by multiple vehicles, and their demands consist of different two-dimensional rectangular items that must be packed in the vehicles' bases. The problem involves determining the least-cost routes that satisfy all customer demands while ensuring the feasible packing of items in each vehicle. We present tailored branch-and-cut (BC) methods for solving the 2L-SDVRP. One of the methods is based on an effective, relaxed two-index vehicle flow formulation that is newly introduced in this paper. To evaluate the performance of the BC methods, computational experiments were conducted using both benchmark instances and new realistic instances inspired by cases from Brazilian logistics companies. The results indicate the superior performance of the method based on the two-index formulation, which obtained optimal solutions for 14 more instances than the other approach on the benchmark instances. This method also performed better on newly created instances, improving solutions by 5.6% on average.