Multiship Crane Sequencing with Yard Congestion Constraints
Multiship Crane Sequencing with Yard Congestion Constraints
复制标题
DOI：
10.1287/trsc.1090.0296
复制
发表时间：
2009-12
期刊：
影响因子：
--
通讯作者：
Shawn Choo;D. Klabjan;D. Simchi-Levi
中科院分区：
文献类型：
--
作者：
Shawn Choo;D. Klabjan;D. Simchi-Levi
集装箱码头的起重机排序决定了码头起重机(QC)执行的卸船和装载工作的顺序，从而将船舶停留的时间降至最低。考虑了船舶的负荷分布、靠泊时间、可用舱位数和质量控制。更重要的是，需要包括净空和堆场拥堵限制，这分别确保遵守相邻QC之间的最小距离，并且在任何时间点都不会过度访问堆场存储区块。针对单船排序问题，提出了一种混合整数规划(MIP)模型，并基于该模型提出了一种启发式算法，得到了较好的解。然后将该模型转化为一个广义集合覆盖问题，并通过分支和价格(B&P)进行精确求解。对于多船排序，在拉格朗日松弛的精神下放松了堆场拥堵约束，从而将问题分解成B&P求解的更小的子问题，并设计了一种有效的原始启发式算法。计算实验表明，可以在合理的计算时间内解决大规模问题。
Crane sequencing in container terminals determines the order of ship discharging and loading jobs that quay cranes (QCs) perform, so that the duration of a vessel's stay is minimized. The ship's load profile, berthing time, number of available bays, and QCs are considered. More important, clearance and yard congestion constraints need to be included, which, respectively, ensure that a minimum distance between adjacent QCs is observed and yard storage blocks are not overly accessed at any point in time. In sequencing for a single ship, a mixed-integer programming (MIP) model is proposed, and a heuristic approach based on the model is developed that produces good solutions. The model is then reformulated as a generalized set covering problem and solved exactly by branch and price (B&P). For multiship sequencing, the yard congestion constraints are relaxed in the spirit of Lagrangian relaxation, so that the problem decomposes by vessel into smaller subproblems solved by B&P. An efficient primal heuristic is also designed. Computational experiments reveal that large-scale problems can be solved in a reasonable computational time.