Decomposition methods and rolling horizon approach for the yard crane scheduling problem

Decomposition methods and rolling horizon approach for the yard crane scheduling problem

Van Dijk, S.M.

Burger, M. (mentor)
Aardal, K.I. (mentor)

Electrical Engineering, Mathematics and Computer Science

Applied mathematics

Optimization

2015-05-08

Yard crane scheduling is one of the operational optimization problems that arise in a port container terminal. Multiple cranes have to store containers in the yard or retrieve containers from the yard. The scheduling of these cranes is complex and it is difficult to find an optimal schedule within limited computation time. In this thesis multiple mixed integer programming formulations are introduced that can be used to model the yard crane scheduling problem. The first formulation fixes zones for a certain planning window. Yard cranes are assigned an individual zone and these zones are non-overlapping. The second model uses a time discretization. We assume that yard cranes can handle 1 job in each time interval of 3 minutes. Working zones for the yard cranes can overlap, but not in the same or subsequent time intervals. Decomposition methods are used to reduce the problem complexity and reduce computation times. A logic-based Benders decomposition is used for the first model were the assignment of cranes to jobs is done separately from finding an optimal path for the yard cranes individually. Iterating between those problems can reduce computation times when the number of iterations is small. After decomposition, the size of these partial problems is much smaller than the size of the problem before decomposition. Some additional lower bound procedures are introduced to further speed up computation. A lower bound procedure can identify and exclude an assignment that will lead to a bad schedule in an early stage. When the problem instances are large enough, logic-based Benders decomposition showed a reduction in computation times. The problem is modeled in a rolling horizon fashion and time decomposition is introduced to again reduce computation times. Instead of trying to solve the problem for one long time period, this time period is split into two or more small time intervals. These intervals are solved separately where connection between them is solved by iterating between those individual time intervals. The rolling horizon reflects the practice in container terminals better since business goes on the entire day and operational decisions are made continuously, over a limited time horizon. By scheduling for a certain time period ahead, schedules can be made online without using all data available in the future. This keeps the computation times limited since scheduling a whole day at once would be too computationally expensive. The arrival times of jobs at the yard are not deterministic. Exact arrival times of trucks at the yard are hard to predict. Therefore some stochastic models are desirable. In this thesis we introduce uncertain arrival times of trucks at the gate of the terminal. Exact arrival times are only known a few minutes ahead while other arrival times follow an exponential distribution. We solve this model using expected values of the arrival times as well as by simulating possible scenarios.

Yard Crane
Mixed Integer Linear Programming

http://resolver.tudelft.nl/uuid:2f22057e-3676-4103-8f22-021a2a4e01ba

Student theses

master thesis

(c) 2015 Van Dijk, S.M.