Paper Info
Title
A two-stage tabu search algorithm with enhanced packing heuristics for the 3L-CVRP and M3L-CVRP
Abstract
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).
Year
DOI
Venue
2012
10.1016/j.cor.2011.11.001
Computers & OR
Keywords
DocType
Volume
Deepest-Bottom-Left-Fill heuristic,existing algorithm,two-stage tabu search algorithm,Maximum Touching Area heuristic,new heuristics,effective tabu search algorithm,new approach,enhanced packing heuristics,loading plan,current best algorithm,related problem variant M3L-CVRP,overall problem
Journal
39
Issue
ISSN
Citations 
9
0305-0548
6
PageRank 
References 
Authors
0.39
13
4
Name
Order
Citations
PageRank
Wenbin Zhu121415.34
Hu Qin220116.49
Andrew Lim315013.57
Lei Wang4150.85