A branch-and-cut algorithm for the quay crane scheduling problem in a container terminal

A branch-and-cut algorithm for the quay crane scheduling problem in a container terminal

0.00 Avg rating0 Votes
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: , , ,
Keywords: transportation: water, combinatorial analysis
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.