STACK PRE-MARSHALLING PROBLEM: A HEURISTIC-GUIDED BRANCH-AND-BOUND ALGORITHM - Zhang, Ruiyou; Jiang, Zhong-Zhong; Yun, Wonyoung (International Journal of Industrial Engineering: Theory, Applications and Practice, 2015)
The stack pre-marshalling (SPM) problem is a complex combinatorial optimization problem which arises mainly within the rapidly growing field of container logistics. This paper proposes a heuristic-guided branch-and-bound (HGB&B) algorithm which can effectively be used to solve the SPM problem. The HGB&B algorithm has a guiding heuristic feature, which is used to search only “valuable” branches. Valueless branchescannot give the optimum solution and hence, are removed prior to the calculation of bounds, which greatly improves the efficiency of algorithm. Additionally, two heuristics have been developed to generate initial upper bounds of the number of moves. Experiments indicate that the time taken to solve the algorithm is acceptable if the product of the number and maximum height of stacks is within about 35. The HGB&B algorithm is faster than existing optimization algorithms, and more efficient than a number of other heuristics. Therefore, it is broadly applicable and valuable in most real-life scenarios, including container logistics, reducing the time taken to find optimal solutions to complex stacking problems.