An investigation of IDA* algorithms for the container relocation problem. (English) Zbl 1295.90003

Zhang, Huidong; Guo, Songshan; Zhu, Wenbin; Lim, Andrew; Cheang, Brenda

García-Pedrajas, Nicolás (ed.) et al., Trends in applied intelligent systems. 23rd international conference on industrial engineering and other applications of applied intelligent systems, IEA/AIE 2010, Cordoba, Spain, June 1–4, 2010. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-13021-2/pbk). Lecture Notes in Computer Science 6096. Lecture Notes in Artificial Intelligence, 31-40 (2010).

Summary: 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.
For the entire collection see [Zbl 05841215].

MSC:

90B06	Transportation, logistics and supply chain management
90C59	Approximation methods and heuristics in mathematical programming

Keywords:

container relocation problem; IDA*; heuristics