A branch-and-price-based heuristic for the vehicle routing problem with two-dimensional loading constraints and time windows

Addressed in this study is a vehicle routing problem with two-dimensional loading constraints and time windows (2L-CVRPTW), aiming to minimize the transportation cost while satisfying the two-dimensional loading and routing constraints with time windows. To solve this problem, for the first time a mixed-integer linear programming model is formulated with considering practical last-in-first-out loading constraints, and a branch-and-price-based (BP-based) heuristic is proposed based on a set partitioning formulation. In the heuristic, a modified labeling algorithm is proposed for the complex pricing problem, which is a relaxation of the elementary shortest path problem with resource constraints and two-dimensional loading constraints. Therein, an effective Tabu-maximum open space packing heuristic is proposed to verify the feasibility of the two-dimensional packing problem of each route generated by the labeling algorithm. In addition, effective accelerating and branching strategies are introduced to improve the solving efficiency of the heuristic. To evaluate the effectiveness and the advantages of the proposed heuristic, extensive computational experiments are performed based on the generated instances. The computational results show that the proposed BP-based heuristic can effectively solve the 2L-CVRPTW, in which the optimal solutions can be achieved much faster than CPLEX in small-scale problems. Relationships between the transportation cost and the characteristics of the instances are analyzed. The stability of the algorithm and the effectiveness of the accelerating strategies are verified and discussed.