On the abstraction method for the container relocation problem

The container relocation problem or the blocks relocation problem is a classic combinatorial optimisation problem that occurs in day-to-day operations for facilities that use block stacking systems. A typical place where this problem arises is a container terminal where containers can be stacked vertically in order to utilise the scarce resource of yard surface, thus at times resulting in the unproductive reshuffling moves for containers stacked above the target container for retrieval. Due to the problem class being NP-hard, a number of studies on this topic propose heuristic approaches to solve this problem. There are a few exact methods (search-based algorithms or mathematical programming) proposed for this problem but the feasible problem size of such methods is quite restricted, limiting their practical significance. In this paper, we propose a new insight into reducing the search space of this problem by the abstraction method. Our main contribution to the existing literature is two-fold: the reduction in the search space by the abstraction method and the bidirectional search using the pattern database. Our computational results confirm that our approach enables instances of a near-practical size to be solved optimally within a reasonable computation time. (C) 2015 Elsevier Ltd. All rights reserved.