eCite Digital Repository
Combining mixed integer programming and constraint programming to solve the integrated scheduling problem of container handling operations of a single vessel
Citation
Qin, T and Du, Y and Chen, JH and Sha, M, Combining mixed integer programming and constraint programming to solve the integrated scheduling problem of container handling operations of a single vessel, European Journal of Operational Research, 285, (3) pp. 884-901. ISSN 0377-2217 (2020) [Refereed Article]
Copyright Statement
©2020 Elsevier B.V. All rights reserved.
Official URL: https://www.sciencedirect.com/science/article/pii/...
DOI: doi:10.1016/j.ejor.2020.02.021
Abstract
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.
Item Details
Item Type: | Refereed Article |
---|---|
Keywords: | OR in maritime industry, container terminal, container unloading/loading problem, mixed integer programming, constraint programming |
Research Division: | Commerce, Management, Tourism and Services |
Research Group: | Transportation, logistics and supply chains |
Research Field: | Maritime transportation and freight services |
Objective Division: | Transport |
Objective Group: | Water transport |
Objective Field: | Port infrastructure and management |
UTAS Author: | Du, Y (Dr Bill Du) |
ID Code: | 138823 |
Year Published: | 2020 |
Web of Science® Times Cited: | 14 |
Deposited By: | Maritime and Logistics Management |
Deposited On: | 2020-04-30 |
Last Modified: | 2020-07-24 |
Downloads: | 0 |
Repository Staff Only: item control page