Abstract: To solve the Blocks Relocation Problem(BRP), by considering the container crane cost, the constraint relationship was defined and the problem's mathematics model was built with targets of minimum relocation number. Three search evaluation strategies including minimum basic relocation number, minimum crane costs and minimum relocation operation times were proposed, and filter based beam search algorithm was used to solve the problem. The comparative analysis indicated that the proposed heuristic algorithm was effectiveness, and could offer the BRP.

Key words: beam search, container yard, relocation, heuristic algorithms

摘要： 针对集装箱码头堆场翻箱问题，在以倒箱量最少为目标的基础上考虑集装箱场桥的移动代价，定义约束关系并建立了该问题的数学模型。提出最小基本倒箱量、最小场桥代价和最少倒箱次数三种搜索评价策略，并采用定向搜索算法进行求解。计算实例对比分析表明，所提出的启发式算法是有效的，能够为集装箱堆场翻箱问题提供决策依据。

关键词: 定向搜索, 集装箱堆场, 倒箱, 启发式算法