Iterative Deepening A* Algorithms for the Container Relocation Problem

The container relocation problem, where containers that are stored in bays are retrieved in a fixed sequence, is a crucial port operation. Existing approaches using branch and bound algorithms are only able to optimally solve small cases in a practical time frame. In this paper, we investigate iterative deepening A* algorithms (rather than branch and bound) using new lower bound measures and heuristics, and show that this approach is able to solve much larger instances of the problem in a time frame that is suitable for practical application. We also examine a more difficult variant of the problem that has been largely ignored in existing literature. Note to Practitioners-Container retrieval is an important operation in a container port. When a ship arrives, containers stored in the port yard are first retrieved by yard crane, loaded onto auto-guided vehicles, transported to quay cranes, and loaded onto the ship by quay crane. Due to various operational constraints, e. g., maintenance of vessel balance and safety issues, the containers in a storage bay are retrieved one by one in a fixed sequence. When the next container to be retrieved is not at the top of its stack, all other containers above it must then be first relocated onto other stacks within the bay. The relocation of a container is a time-consuming operation that essentially dominates all other aspects of the problem, and therefore it is important that the retrieval plan minimizes the number of such relocations. This study proposes a method to generate a near-optimal retrieval plan for yard cranes. This often arises as a subproblem when devising an overall plan for port operations that maximizes throughput, which involves the coordination of multiple pieces of machinery. Our approach produces significantly better results than all existing approaches.