CAJ | 학술논문

针对进口集装箱卸船的岸桥与集卡集成调度问题，分别提出混合整数规划(MIP)模型和约束规划(CP)模型，目标是使得卸船完工时间最短，该问题是NP难题。通过OPL语言设计约束规划模型，利用其为调度问题提供的特殊构造，如区间变量、序列变量等进行建模，并采用“扩展操作任务”的概念来定义区间变量以提升求解效率。为评价解的质量，设计一个新的下界求解方法。使用不同规模的实例对约束规划模型和MIP模型进行测试，结果表明，在小规模实例中，CP模型求解性能略差于MIP模型，但对于中大规模实例，MIP模型无法在设定时限内找到解，而CP模型则能以较快的收敛速度得到高质量的解，目标距离下界的差距控制在2.19%~8.28%。
침대진구집장상사선적안교여집잡집성조도문제，분별제출혼합정수규화(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%.