An Improved Approach for Vehicle Routing Problem with Three-Dimensional Loading Constraints Based on Genetic Algorithm and Residual Space Optimized Strategy

To duly and correctly deliver parcels, both the capacity and the delivery route of a delivery vehicle need to be considered. Thus, the delivery process of a delivery vehicle can be characterized as a capacitated vehicle routing problem with three-dimensional loading constraints (3L-CVRP), which is an NP-hard problem. To solve the problem, a mathematical model is established in this paper to minimize the total delivery distance and maximize the loading rate, simultaneously. Additionally, a hybrid algorithm that combines a three-dimensional (3D) packing algorithm based on the residual space optimized (RSO) strategy and an improved genetic algorithm (IGA) is proposed. Initially, the proposed hybrid algorithm employs a modified Clarke–Wright savings algorithm to generate a feasible set of route solutions. Furthermore, building upon the traditional genetic algorithm, an elite retention strategy is introduced, and an enhanced order crossover method is utilized to improve the stability of the hybrid algorithm and its global search capability for optimal solutions. Finally, during each iteration of the algorithm, the RSO algorithm is integrated to verify the feasibility of 3D packing scheme. Two comparative experiments are conducted on 22 modified benchmark instances and actual logistics data of a university against two other algorithms, demonstrating that the proposed RSO-IGA algorithm achieves superior solutions in delivery efficiency.