A two-stage tabu search algorithm with enhanced packing heuristics for the 3L-CVRP and M3L-CVRP

摘要

The Three-Dimensional Loading Capacitated Vehicle Routing Problem (3L-CVRP) addresses practical constraints frequently encountered in the freight transportation industry. In this problem, the task is to serve all customers using a homogeneous fleet of vehicles at minimum traveling cost. The constraints imposed by the three-dimensional shape of the goods, the unloading order, item fragility, and the stability of the loading plan of each vehicle are explicitly considered. We improved two well-known packing heuristics, namely the Deepest-Bottom-Left-Fill heuristic and the Maximum Touching Area heuristic, for the three-dimensional loading sub-problem and provided efficient implementations. Based on these two new heuristics, an effective tabu search algorithm is given to address the overall problem. Computational experiments on publicly available test instances show our new approach outperforms the current best algorithms for 20 out of 27 instances. Our approach is also superior to the existing algorithm on benchmark data for the closely related problem variant M3L-CVRP (which uses a slightly different unloading order constraint compared to 3L-CVRP).