Logic-based Benders decomposition for the three-dimensional loading capacitated vehicle routing problem with time windows

This paper addresses the integration of the vehicle routing and three-dimensional packing problems, commonly referred to as the Three-Dimensional Loading Capacitated Vehicle Routing Problem (3L-CVRP). Combining these two classical problems is of significant practical relevance, as the efficiency of load allocation directly impacts the effectiveness of delivery routes. Among the various possible variants, this study focuses on the 3L-CVRP with time windows and considers all feasible orientations of the boxes within the containers. Two mathematical formulations are presented, one with and another without an explicit vehicle index in the routing decision variables. Preprocessing techniques are applied to reduce model complexity and enhance computational efficiency. To solve larger instances, a logic-based Benders decomposition method is also proposed. The performance of the mathematical models and decomposition strategies is assessed through computational experiments using multiple benchmark datasets. The results show the competitiveness of the proposed approaches, which found optimal solutions in 46 out of 124 experiments, 13 of which represent the first proven optimal solutions reported in the literature. Moreover, the proposed methods obtained 33 new best-known solutions on classical and widely studied benchmark sets.