Theoretical analysis and practical algorithms for operational problems in container terminals

In recent years we have seen the breakdown of many trade barriers and the globalization of trade. These developments have increased the importance of logistics and transportation, and in particular the importance of marine transportation systems to the global economy. These systems include a network of ports and terminals that allow the transshipment of containers to and from ships. Since most of these terminals are now working at, almost, full capacity, the most important objective for a terminal is to decrease ship turnaround time at the port.; In this dissertation, we consider a container terminal discharging and loading containers to and from ships. Each discharged container has a number of potential locations in the yard area where it can be stored. Containers are moved between the ship area and the yard using a fleet of vehicles, each of which can carry one container at a time. These vehicles travel on a network of lanes in the terminal. We focus on terminal operational problems including dispatching and routing of vehicles and locating discharged containers, so as to minimize the ship turnaround time. Our objective is to determine the underlying structure of optimal strategies and use this insight to construct effective algorithms.; Specifically, in the vehicle dispatching problem, the objective is to determine the impact of vehicle dispatching policies on the ship makespan. In this case, we consider both discharging and loading operations and develop optimal or near-optimal vehicle dispatching policies for different cases.; In the vehicle-scheduling-location problem, we consider a more general model that requires finding a storage location for each discharged container as well as a vehicle dispatching policy. We show that this problem is NP-hard. This implies that it is unlikely that we will ever find a polynomial time algorithm that solves this problem to optimality. Thus, we develop a heuristic based on formulating the problem as an Assignment Problem, and analyze the performance of this heuristic using asymptotic and absolute worst-case performance analyses and empirical analysis.; Finally, in the vehicle routing problem, the objective is to identify routes for the vehicles taking into account the congestion in the network and so as to minimize ship turnaround time. We propose a heuristic based on formulating the problem as a Shortest Path Problem and analyze its effectiveness using asymptotic worst-case analysis and empirical analysis.