×

zbMATH — the first resource for mathematics

A branch-and-cut algorithm for the quay crane scheduling problem in a container terminal. (English) Zbl 1112.90033
Summary: The quay crane scheduling problem consists of determining a sequence of unloading and loading movements for cranes assigned to a vessel in order to minimize the vessel completion time as well as the crane idle times. Idle times originate from interferences between cranes since these roll on the same rails and a minimum safety distance must be maintained between them. The productivity of container terminals is often measured in terms of the time necessary to load and unload vessels by quay cranes, which are the most important and expensive equipment used in ports. We formulate the quay crane scheduling problem as a vehicle routing problem with side constraints, including precedence relationships between vertices. For small size instances our formulation can be solved by CPLEX. For larger ones we have developed a branch-and-cut algorithm incorporating several families of valid inequalities, which exploit the precedence constraints between vertices.

MSC:
90B35 Deterministic scheduling theory in operations research
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Software:
CPLEX
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Hamiltonian Path Problems in the On-line Optimization of Flexible Manufacturing Systems, PhD thesis, Konrad Zuse Zentrum für Informationstechnik Berlin, 1996.
[2] Ascheuer, Math Program 90 pp 475– (2001)
[3] Ascheuer, Comput Optim Appl 17 pp 61– (2000)
[4] Augerat, Eur J Oper Res 106 pp 546– (1999)
[5] Balas, Math Program 68 pp 241– (1995)
[6] Bianco, INFOR 32 pp 19– (1994)
[7] Christiansen, Transport Sci 38 pp 1– (2004)
[8] Cordeau, Oper Res (2005)
[9] Cordeau, 4OR Q J Belgian French Ital Oper Res Soc 1 pp 89– (2003)
[10] Daganzo, Transport Sci 24 pp 205– (1990)
[11] , ”Polyhedral theory,” The Traveling Salesman Problem, , , (Editors), Wiley, New York, 1985, pp. 251-305.
[12] Kim, Eur J Oper Res 156 pp 752– (2004)
[13] Laporte, Oper Res 51 pp 940– (2003)
[14] Lim, Nav Res Logis 51 pp 386– (2004)
[15] , Branch-and-cut algorithms for the capacitated VRP, The Vehicle Routing Problem, (Editors), SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 2002, pp. 53-84. · Zbl 1076.90550
[16] Peterkofsky, Transport Res 24B pp 159– (1990)
[17] Steenken, OR Spectr 26 pp 3– (2004)
[18] , The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 2002. · Zbl 0979.00026
[19] UNCTAD: Review of maritime transport, Technical report ( 2004), United Nations, New York and Geneva.
[20] Vis, Eur J Oper Res 147 pp 1– (2003)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.