A multi-round partial beam search approach for the single container loading problem with shipment priority

We consider shipping priority in the single container loading problem, where all boxes with high priority must be loaded into the container before those with low priority. Shipping priority is a very common consideration in real applications, but it has received very little attention from the research community. We propose a multi-round partial beam search method that explicitly considers shipping priority when evaluating the potential of partial solutions to solve this problem. Experiments on existing benchmarks suggest that our approach is more effective than current methods. The average utilization is improved by almost 1% while the running time is shorter than the state of the art method. Since existing benchmark data covers only weakly heterogeneous instances, we extend the benchmark data to strongly heterogeneous instances and also generate instances with various proportions of high priority boxes to cover a wider spectrum of applications. © 2013 Elsevier B.V. All rights reserved.