集装箱码头岸桥调度优化模型及算法

为弥补集装箱码头岸桥调度问题的传统优化方法仅适用单船舶情况的不足,以总费用(所有岸桥使用费用和船舶停靠费用)最小为优化目标,考虑岸桥不可穿越性和安全距离约束条件,建立了了面向多艘船舶的集装箱码头岸桥统一调度和卸船任务分配问题的混合整数规划优化模型.使用任务网络图方法,搜索影响卸船任务最终完成时间的关键任务及其相应的限制任务路径,设计了基于限制任务路径进行邻域搜索的双层模拟退火算法求解模型.12个不同规模的算例结果表明:与分支定界法和遗传算法相比,本文算法节省时间6.32%~18.36%,近似最优解的质量更高,而且最优解目标值之间的差距仅为0.38%~2.20%;考虑岸桥之间的安全距离约束导致系统运营成本增加3.41%~11.21%. 

Optimization Model and Algorithm for Quay Crane Scheduling in Container Terminals

In order to remedy the defect of the traditional optimization methods for the quay crane scheduling in container terminal which could only deal with single ship, a mixed-integer programming optimization model for quay crane scheduling and job assignment for multiple ships was proposed. The objective of the model is to minimize the total cost, including the use cost of the quay cranes and the berthing cost of the ships in the terminal, with the non-crossing and safety distance constraints of cranes. Then, a bi-level simulated annealing algorithm with neighborhood search based on the restricted path was developed to solve the model, in which the job network graph is used to find the critical job and its restricted path that influence the end time of the ship unloading jobs. The results of 12 numerical experiments with different scales show that compared with the branch and bound (B&B) algorithm and the genetic algorithm (GA), the proposed algorithm could reduce the computational time by 6.32% to 18.36%, and obtain the approximate optimal solution of higher quality, the gaps between objective function values of which are only 0.38% to 2.20%In addition, considering the safety distance constraint between cranes into the model cause the total operation cost to increase by 3.41% to 11.21%.