Article ID: | iaor20072866 |
Country: | United States |
Volume: | 53 |
Issue: | 1 |
Start Page Number: | 45 |
End Page Number: | 59 |
Publication Date: | Feb 2006 |
Journal: | Naval Research Logistics |
Authors: | Laporte Gilbert, Gaudioso Manlio, Cordeau Jean-Franois, Moccia Luigi |
Keywords: | transportation: water, combinatorial analysis |
The quay crane scheduling problem consists of determining a sequence of unloading and loading movements for cranes assigned to vessels 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.