摘要
针对进口集装箱卸船的岸桥与集卡集成调度问题,分别提出混合整数规划(MIP)模型和约束规划(CP)模型,目标是使得卸船完工时间最短,该问题是NP难题。通过OPL语言设计约束规划模型,利用其为调度问题提供的特殊构造,如区间变量、序列变量等进行建模,并采用“扩展操作任务”的概念来定义区间变量以提升求解效率。为评价解的质量,设计一个新的下界求解方法。使用不同规模的实例对约束规划模型和MIP模型进行测试,结果表明,在小规模实例中,CP模型求解性能略差于MIP模型,但对于中大规模实例,MIP模型无法在设定时限内找到解,而CP模型则能以较快的收敛速度得到高质量的解,目标距离下界的差距控制在2.19%~8.28%。
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%.
出处
《计算机工程》
CAS
CSCD
2014年第5期196-202,共7页
Computer Engineering
基金
国家自然科学基金资助项目(71172076)
交通部应用基础研究基金资助项目(2011-329-810-450)
上海市科委地方院校专项基金资助项目(11510501800)
上海市教委科研创新基金资助项目(11YZ135)
上海市重点学科建设基金资助项目(S30601)
关键词
岸桥调度
集卡调度
约束规划
集装箱码头
最优化
启发式算法
混合整数规划
quay crane scheduling
yard truck scheduling
Constraint Programming(CP)
container terminal
optimization
heuristicalgorithm
Mixed Integer Programming(MIP)