The split delivery vehicle routing problem with time windows and three-dimensional loading constraints

This paper presents complex variants of the vehicle routing problem: the Vehicle Routing Problem with Time Windows and Three-Dimensional Loading Constraints (3L-VRPTW) and the Split Delivery Vehicle Routing Problem with Time Windows and Three-Dimensional Loading Constraints (3L-SDVRPTW). The difference between the two problems is whether a customer can be visited in two or more tours. Under the conditions of satisfying customer demands and loading constraints, the 3L-VRPTW model and the 3L-SDVRPTW model are constructed with the aim of minimizing transportation costs. To efficiently solve the above problems, a two-layer method is proposed in this study, including a routing stage and a packing stage. The Adaptive Large Neighborhood Search algorithm based on the Metropolis criterion is used to obtain the vehicle routing. The genetic algorithm is used to solve the packing stage, ensuring that the goods are packed in a way that minimizes pre-movements. The proposed algorithms are tested on different instances, verifying their effectiveness. Additionally, numerical experiments are conducted using instances with different customer distributions. The results show that when customers are located in multiple small areas, split delivery it distribution can significantly reduce penalty costs and be more economical.