A two-stage tabu search algorithm with enhanced packing heuristics for the 3L-CVRP and M3L-CVRP |
| |
Authors: | Wenbin Zhu Andrew LimLei Wang |
| |
Affiliation: | a Department of Management Sciences, City University of Hong Kong, Tat Chee Ave, Kowloon Tong, Hong Kong b Department of Computer Science and Engineering, Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong c Department of Computer Science, School of Information Science and Technology, Zhongshan (Sun Yat-Sen) University, Guangzhou, Guangdong 510275, PR China d School of Management, Huazhong University of Science and Technology, No. 1037, Luoyu Road, Wuhan, China |
| |
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). |
| |
Keywords: | Vehicle routing problem 3D packing Deepest-Bottom-Left-Fill Maximum Touching Area Tabu search |
本文献已被 ScienceDirect 等数据库收录! |
|