English

运筹学学报 ›› 2020, Vol. 24 ›› Issue (3): 67-76.doi: 10.15960/j.cnki.issn.1007-6093.2020.03.005

• • 上一篇    下一篇

集装箱码头桥机调度问题基于完工时间下界的算法

陆书翔1,2, 吕长虹1,*, 秦涛3   

  1. 1. 华东师范大学数学科学学院, 上海市核心数学与实践重点实验室, 上海 200241;
    2. 同济大学经济与管理学院, 上海 200092;
    3. 上海海勃物流软件有限公司, 上海 200080
  • 收稿日期:2018-07-25 发布日期:2020-09-05
  • 通讯作者: 吕长虹 E-mail:chlu@math.ecnu.edu.cn
  • 基金资助:
    上海市科学技术委员会（Nos.18dz2271000，19jc1420100），国家自然科学基金（No.11871222）

An algorithm based on makespan lower bound for quay crane schedule problem in container terminals

LU Shuxiang1,2, Lü Changhong1,*, QIN Tao3   

  1. 1. School of Mathematical Sciences, Shanghai Key Laboratory of Pure Mathematics and Mathematical Practice, East China Normal University, Shanghai 200241, China;
    2. School of Economics and Management, Tongji University, Shanghai 200092, China;
    3. Shanghai Harbor e-Logistics software Company Limited, Shanghai 200080, China
  • Received:2018-07-25 Published:2020-09-05

PDF

528

摘要： 关注单船桥机调度问题，指出了单船桥机的闲置会影响码头整体的运作效率。以单个集装箱为任务单位，考虑桥机移动时间、安全距离等约束，建立了最小化桥机完工时间和闲置时间的多目标规划模型。基于完工时间下界的两种不同情况：以重点贝位工作量确定和以平均工作量确定，分别设计了基于邻域搜索的启发式算法和基于贪心策略的“分割贝位”算法，并且证明了在以平均工作量确定下界的情况中该算法不会导致桥机闲置。不同规模、不同下界类型的算例表明：提出的模型与算法得到的桥机调度计划更适合实际生产作业，能够有效地逼近完工时间下界，算法运行速度较现有的研究有显著的提高。

关键词: 桥机调度, 多目标规划, 启发式算法

Abstract: This paper focuses on the quay crane scheduling on one vessel, and suggests that the idle of crane will affect the efficiency of the whole container terminal. We consider a single container as task unit and constrains such as quay crane's moving time and safe margin and establish a multi-objective programming model to minimize the vessel completion time and crane idle time. Noticing the lower bound of completion time, the problem will be divided into two situations:determined by the workload of key bays and determined by average workload. Respectively, we proposed the heuristic algorithm based on neighborhood search and "bay segmentation" algorithm based on the greedy strategy, and proved that in the case where the lower bound is determined by the average workload, our algorithm will not lead to idle of any cranes. The results of numerical experiments with different scales and lower bounds show that the quay crane schedule obtained by our model and algorithm are more suitable for actual production operation, and can effectively approach the lower bound of the completion time. The algorithm has a significant improvement in the speed of the algorithm with the existing research.

Key words: quay crane scheduling, multi-objective programming, heuristic algorithm

中图分类号: