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

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

0.00 Avg rating0 Votes
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: , , ,
Keywords: heuristics: tabu search, combinatorial optimization, programming: integer
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).

Reviews

Required fields are marked *. Your email address will not be published.