Solving real-world sized container pre-marshalling problems with an iterative deepening branch-and-bound algorithm

Shunji Tanaka, Kevin Tierney

doi:10.1016/j.ejor.2017.05.046

Abstract Container terminals around the world regularly re-sort the containers they store according to their retrieval times in a process called pre-marshalling, thus ensuring containers are efficiently transferred through the terminal. State-of-the-art algorithms struggle to find optimal solutions for real-world sized pre-marshalling problems. To this end, we introduce an improved exact algorithm using an iterative deepening branch and bound search, including a novel lower bound computation, a new branching heuristic, new dominance rule and a new greedy partial solution completion heuristic. Our approach finds optimal solutions for 161 more instances than the state-of-the-art algorithm on two well known, difficult pre-marshalling datasets, and solves all instances in three other datasets in just several seconds. Furthermore, we find optimal solutions for a majority of real-world sized instances, and feasible solutions with very low relaxation gaps on those instances where no optimal could be found.

Solving real-world sized container pre-marshalling problems with an iterative deepening branch-and-bound algorithm

書誌事項

この論文をさがす

説明

収録刊行物

被引用文献 (1)*注記

参考文献 (36)*注記

関連プロジェクト

詳細情報詳細情報について

書き出し

問題の指摘

Solving real-world sized container pre-marshalling problems with an iterative deepening branch-and-bound algorithm

書誌事項

この論文をさがす

説明

収録刊行物

被引用文献 (1)*注記

参考文献 (36)*注記

関連プロジェクト

詳細情報 詳細情報について

書き出し

問題の指摘

詳細情報詳細情報について