Multiship Crane Sequencing with Yard Congestion Constraints
Authors:
Open Access
- 1 February 2010
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Transportation Science
- Vol. 44 (1) , 98-115
Abstract
Crane sequencing in container terminals determines the order of ship discharging and loading jobs that quay cranes (QCs) perform, so that the duration of a vessel's stay is minimized. The ship's load profile, berthing time, number of available bays, and QCs are considered. More important, clearance and yard congestion constraints need to be included, which, respectively, ensure that a minimum distance between adjacent QCs is observed and yard storage blocks are not overly accessed at any point in time. In sequencing for a single ship, a mixed-integer programming (MIP) model is proposed, and a heuristic approach based on the model is developed that produces good solutions. The model is then reformulated as a generalized set covering problem and solved exactly by branch and price (B&P). For multiship sequencing, the yard congestion constraints are relaxed in the spirit of Lagrangian relaxation, so that the problem decomposes by vessel into smaller subproblems solved by B&P. An efficient primal heuristic is also designed. Computational experiments reveal that large-scale problems can be solved in a reasonable computational time.Keywords
This publication has 13 references indexed in Scilit:
- Selected Topics in Column GenerationOperations Research, 2005
- A decision support system for operations in a container terminalDecision Support Systems, 2005
- A crane scheduling method for port container terminalsEuropean Journal of Operational Research, 2004
- A multiple-crane-constrained scheduling problem in a container terminalEuropean Journal of Operational Research, 2003
- Interblock Crane Deployment in Container TerminalsTransportation Science, 2002
- An Optimal Routing Algorithm for a Transfer Crane in Port Container TerminalsTransportation Science, 1999
- Branch-and-Price: Column Generation for Solving Huge Integer ProgramsOperations Research, 1998
- A branch and bound solution method for the crane scheduling problemTransportation Research Part B: Methodological, 1990
- The crane scheduling problemTransportation Research Part B: Methodological, 1989
- The Traveling-Salesman Problem and Minimum Spanning TreesOperations Research, 1970