The goal of this project is to develop new, advanced optimization approaches for the simultaneous scheduling of berth and quay crane resources at container ports. Since appropriate mathematical models of these resources lead to difficult-to-solve integer programming formulations, effective metaheuristic approaches will be applied to search for global optima. Fast scheduling heuristics developed under this project will be a critical tool needed to determine the operational impacts of damage to key port infrastructure. Furthermore, this decision technology can serve as a prototype for terminal operators, and can be used to assist port scheduling during the irregular operating periods following earthquake events.

In the first year, we have focused our research attention on the scheduling problem for the most critical resources in a container terminal, berth and quay cranes. We have developed simultaneous berth and quay crane scheduling models for static vessel arrival schedules for multiple-day planning horizons. Unlike most work found in the literature, we treat the two scheduling problems simultaneously because the vessel berth duration depends directly on the number of cranes serving the vessel over time. For small test problems, we are able to formulate and solve a mixed integer program optimization model for this problem using standard commercial-strength integer programming solvers. However, the problems solvable are of unrealistic size. We therefore have developed two alternative metaheuristic algorithms for determining approximately-optimal schedules. Both methods are nested tabu search heuristics. The first metaheuristic approach, denoted the one-phase heuristic, uses three nested searches. The outermost search makes changes to the vessel priority sequence, the middle search makes changes to the vessel berthing locations, while the innermost search makes changes to the crane allocation. Evaluating a local move from one solution to another at an outer layer requires running tabu searches at inner layers. The second metaheuristic, denoted the two-phase heuristic, uses a first phase with two nested searches on vessel priority and berth locations, but evaluates the changes with upper and lower bound approximations to the crane allocation subproblem. It then passes a small set (typically 100) of best solutions to a second phase with uses another tabu search to determine exact crane allocations and cost.

The developed metaheuristics for the berth and quay crane scheduling problem were tested on representative sample problems. We first generated small problems with a berthing area capable of at most two simultaneously vessel berthings, four quay cranes, and five arriving vessels. For these problems, the mixed integer programming formulation was solvable using commercial-strength integer programming solvers. Optimal solutions were found for all instances, with average compute times of 10 minutes but a maximum time of 2.5 hours. The two metaheuristics were also able to solve each of these problems optimally, but each instance was solved in less than one second of compute time. 

The metaheuristics also performed well on realistically-sized problem instances. We developed test sets with longer berthing areas capable of four simultaneous vessel berthings, 10 quay cranes, and 20-30 arriving vessels over a three-day planning horizon. Such problems are intractable to solve with the exact mixed-integer programming model, but can be solved approximately via the metaheuristics with run times ranging from 2 to 20 minutes. In general, the two-phase approach provided better solutions faster than the one-phase heuristic.

Return to Research Activities