Article ID: | iaor20121283 |
Volume: | 39 |
Issue: | 9 |
Start Page Number: | 2178 |
End Page Number: | 2195 |
Publication Date: | Sep 2012 |
Journal: | Computers and Operations Research |
Authors: | Lim Andrew, Zhu Wenbin, Wang Lei, Qin Hu |
Keywords: | heuristics: tabu search, combinatorial optimization, programming: integer |
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).