路径优化算法求解集装箱码头堆场翻箱问题

Paths Optimum Algorithm for the Container Relocation Problem in the Container Terminals

集装箱翻箱问题(CRP)可描述为在集装箱堆场现有堆垛状态和提箱序列确定情况下,以最少的翻箱数量提取出堆场箱区内所有集装箱;CRP是一个NP-hard问题。为此构建双层目标规划模型,提出嵌套翻箱规则的路径规划算法(POA),以期减少解空间大小,从而在更短的CPU运行时间内得到CRP的最优解。数值实验结果表明,POA在翻箱数量及运行时间上均优于多数算法,有效提高集装箱码头堆场作业效率,更适用于求解集装箱码头翻箱作业优化问题。

The container relocation problem （CRP） can be defined as a sequence which allows each container to be extracted with least number of relocations when a cluster of identical containers have been stacked in a storage area. CRP is an NP-hard problem. Firstly, a two-level goal programming model for CRP is presented that can help understand this problem. Secondly, on account of the complexity of CRP, heuristic rules are proposed to reduce hunting space by the way of dividing solution space. Thirdly, paths optimum algorithm based upon these heuristics is proposed to reduce unfeasible solutions and solve optimal solution for any instances in a shorter CPU runtime. Finally, numerical tests are used to compare results of POA and other algorithms, showing that POA is better in the areas of efficiency, robustness and accuracy. Furthermore,POA improves the operation efficiency of container terminals effectively,and it is suitable for container pick-up optimization.