We address an optimization problem that arises at seaports where containers are transported between stacking areas and small buffer areas of restricted capacity that are located within the reach of quay cranes. The containers are transported by straddle carriers that have to be routed such that given unloading and loading sequences of the containers at the quay cranes are respected. The objective is to minimize the turnaround times of the vessels. We analyze the problem’s computational complexity, present an integer program, and propose a heuristic framework that is based on decomposing the problem into its routing component and a component that handles the time variables and buffer capacities. The framework is analyzed in computational tests that are based on real-world data. Based on these tests, we analyze the question of whether or not it pays off to deviate from the approach of permanently assigning a fixed number of straddle carriers to each quay crane, which is the strategy that is currently implemented at the port.

Introduction

A container port is a complex system consisting of berths equipped with quay cranes, transport vehicles, stacking areas, stacker cranes, and road or rail connections to the hinterland. Each container port is a unique combination of these components and features an individual vehicle fleet. Large ports handle several million twenty-foot equivalent units (TEU) on an annual basis. Port authorities therefore strive for sophisticated planning approaches based on simulation or optimization techniques in order to stay competitive. Operations research challenges at seaports are mostly concerned with problem settings that directly or indirectly affect the flow of containers within the ports. Container ports that can serve several vessels simultaneously aim at high berth utilization rates, so that decision makers have to determine appropriate assignments of vessels to berths. Each berth is equipped with one or multiple quay cranes. These cranes are needed for the process of loading and unloading containers and have to be scheduled appropriately. Inbound containers, i.e., containers that arrive by vessels, must then be transported to large stacking (or storage) areas, where they are temporarily stored for later processing by train, truck or vessel. Outbound containers, i.e., containers that arrive by train or truck and that have to be loaded onto a vessel, have to be transported in the reverse direction. The corresponding transportation requests within the seaport can be executed by different types of vehicles. Automated guided vehicles (AGVs) and manually driven yard trucks (YTs) cannot lift or drop containers. They have to be loaded and unloaded at predefined handover positions by quay cranes at the vessels or by yard cranes (or gantry cranes) at the storage areas. Automated lifting vehicles (ALVs) are able to perform lifting and dropping operations. However, yard cranes remain necessary for stacking operations.