Branch-and-Price Approach for Two-Dimensional Loading Constrained Vehicle Routing Problem with Simultaneous Pickup and Delivery

This study addresses a widespread practical simultaneous pickup and delivery problem, where pickup and delivery requests for transporting are non-stackable rectangular items. To solve this problem, a branch-and-price approach is proposed based on a set partitioning formulation. In the approach, a strong labeling algorithm with an efficient packing heuristic are proposed to deal with the exploration and the packing procedure in pricing problem. Extensive experiments based on the widely used benchmarks are conducted. The results demonstrate the efficiency and superiority of the proposed approach for solving the 2L-SPD. Moreover, comparison results infer that splitting customers with both pickup and delivery into pickup-only customers and delivery-only customers increases the computational burden under the branch-and-price approach.