作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程

• 人工智能及识别技术 • 上一篇    下一篇

基于约束规划的岸桥与集卡集成调度

秦天保,彭嘉瑶,沙 梅   

  1. (上海海事大学交通运输学院,上海 200135)
  • 收稿日期:2013-03-11 出版日期:2014-05-15 发布日期:2014-05-14
  • 作者简介:秦天保(1971-),男,副教授、博士,主研方向:港口与航运系统智能优化;彭嘉瑶,硕士研究生;沙 梅,教授、博士。
  • 基金资助:
    国家自然科学基金资助项目(71172076);交通部应用基础研究基金资助项目(2011-329-810-450);上海市科委地方院校专项基金资助项目(11510501800);上海市教委科研创新基金资助项目(11YZ135);上海市重点学科建设基金资助项目(S30601)。

Integrated Quay Crane and Yard Truck Scheduling Based on Constraint Programming

QIN Tian-bao, PENG Jia-yao, SHA Mei   

  1. (College of Transport & Communications, Shanghai Maritime University, Shanghai 200135, China)
  • Received:2013-03-11 Online:2014-05-15 Published:2014-05-14

摘要: 针对进口集装箱卸船的岸桥与集卡集成调度问题,分别提出混合整数规划(MIP)模型和约束规划(CP)模型,目标是使得卸船完工时间最短,该问题是NP难题。通过OPL语言设计约束规划模型,利用其为调度问题提供的特殊构造,如区间变量、序列变量等进行建模,并采用“扩展操作任务”的概念来定义区间变量以提升求解效率。为评价解的质量,设计一个新的下界求解方法。使用不同规模的实例对约束规划模型和MIP模型进行测试,结果表明,在小规模实例中,CP模型求解性能略差于MIP模型,但对于中大规模实例,MIP模型无法在设定时限内找到解,而CP模型则能以较快的收敛速度得到高质量的解,目标距离下界的差距控制在2.19%~8.28%。

关键词: 岸桥调度, 集卡调度, 约束规划, 集装箱码头, 最优化, 启发式算法, 混合整数规划

Abstract: A Mixed Integer Programming(MIP) model and a Constraint Programming(CP) model to tackle the integrated quay crane and yard truck scheduling problem for inbound containers are proposed, which aims to minimize the makespan of unloading process. The CP model is developed with OPL modeling language and employs OPL’s special constructs designed for scheduling problems, e.g., interval variables sequence variable etc. To improve solving efficiency, a special concept called extended operation task is proposed which is used to define interval variables. Besides, a new lower bound is given to evaluate the quality of solutions. Computational experiments on varied scales of instances are carried out to test the CP model and the MIP model. The results indicate that the CP model does not outperform the MIP model for small instances. For medium and large instances, the MIP model can not be solved within time limit, whereas the CP model is effective for finding high-quality solutions and can efficiently solve large problems with fast convergence rate. On average, the gap between the objective values of the CP model and the lower bounds is 2.19%~8.28%.

Key words: quay crane scheduling, yard truck scheduling, Constraint Programming(CP), container terminal, optimization, heuristic algorithm, Mixed Integer Programming(MIP)

中图分类号: