University of Tasmania
Browse

File(s) under permanent embargo

Combining mixed integer programming and constraint programming to solve the integrated scheduling problem of container handling operations of a single vessel

journal contribution
posted on 2023-05-20, 14:02 authored by Qin, T, Yuquan Du, Chen, JH, Sha, M
In the container terminals of seaports, the container handling system consists of a variety of container handling machines such as quay cranes, internal yard trucks, and yard cranes. This study applies a holistic approach to the integrated scheduling of these machines for the container handling operations of a single vessel. We formulate this special hybrid flow shop scheduling problem through both mixed integer programming (MIP) and constraint programming (CP) techniques. Then we develop an easily-implemented approach that combines the strengths of MIP and CP. First, the MIP model, which only considers quay crane scheduling, is solved by an MIP solver, and a quay crane allocation plan is retrieved from the MIP solution. Then, this quay crane allocation plan is fed to the CP model, warm-starting the branch-and-prune algorithm built in a CP optimizer. Our numerical experiments reveal that this hybrid MIP/CP approach can solve the large-sized instances with up to 1000 containers, 6 quay cranes, 36 yard trucks, and 15 yard cranes to optimality with a gap of less than 3.31%, within a solution time of 2 minutes. If we increase the solution time to 5 minutes, this hybrid approach solves larger instances with up to 1400 containers to optimality with a gap of less than 1.41%. The state-of-the-art dedicated algorithms reported in the literature (which address an easier version of the same problem by ignoring non-crossing constraints and safety margins between quay cranes) are only able to find solutions for real-life instances with up to 500 containers within the solution time of 2930 or 5221 seconds, leaving a 4% or an unknown optimality gap. Thus, this study improves the solution of this integrated scheduling problem in terms of the instance size, solution efficiency, and solution optimality.

History

Publication title

European Journal of Operational Research

Volume

285

Pagination

884-901

ISSN

0377-2217

Department/School

Australian Maritime College

Publisher

Elsevier Science Bv

Place of publication

Po Box 211, Amsterdam, Netherlands, 1000 Ae

Rights statement

©2020 Elsevier B.V. All rights reserved.

Repository Status

  • Restricted

Socio-economic Objectives

Port infrastructure and management

Usage metrics

    University Of Tasmania

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC