Two natural heuristics for 3D packing with practical loading constraints

In this paper, we describe two heuristics for the Single Vehicle Loading Problem (SVLP), which can handle practical constraints that are frequently encountered in the freight transportation industry, such as the servicing order of clients; item fragility; and the stability of the goods. The two heuristics, Deepest-Bottom-Left-Fill and Maximum Touching Area, are 3D extensions of natural heuristics that have previously only been applied to 2D packing problems. We employ these heuristics as part of a two-phase tabu search algorithm for the Three-Dimensional Loading Capacitated Vehicle Routing Problem (3L-CVRP), where the task is to serve all customers using a homogeneous fleet of vehicles at minimum traveling cost. The resultant algorithm produces mostly superior solutions to existing approaches, and appears to scale better with problem size. © 2010 Springer-Verlag Berlin Heidelberg