A survey of berth allocation and quay crane scheduling problems in container terminals

Abstract

Due to the variety of technical equipments and terminal layouts, research has produced a multitude of optimization models for seaside operations planning in container terminals. To provide a support in modeling problem characteristics and in suggesting applicable algorithms this paper reviews the relevant literature. For this purpose new classification schemes for berth allocation problems and quay crane scheduling problems are developed. Particular focus is put on integrated solution approaches which receive increasing importance for the terminal management.

Introduction

In recent years, OR methods have received considerable importance for the operations management in container terminals (CTs). Comprehensive overviews on applications and optimization models in this field are given by Meersmans and Dekker, 2001, Vis and de Koster, 2003, Steenken et al., 2004, Vacca et al., 2007, Stahlbock and Voß, 2008. A significant amount of papers dealing with the application of OR methods addresses the planning of the seaside transshipment operations. Fig. 1 shows important relations of the strategic planning and the operations planning at the seaside area, the yard, and the landside area.

One issue of seaside operations planning is the assignment of quay space and service time to vessels that have to be unloaded and loaded at a terminal. This problem is commonly referred to as the berth allocation problem (BAP). The transshipment of containers between a vessel and the quay is generally performed by specialized cranes, which are mounted on rail tracks alongside the quay. The assignment of these quay cranes (QCs) to vessels and the determination of work plans for the cranes addresses two further problems, namely the quay crane assignment problem (QCAP) and the quay crane scheduling problem (QCSP). Solutions to these problems must respect the berth layout and the used equipment, whereas they impact the yard operations and the workforce planning, see Fig. 1.

Due to the variety of technical equipments and terminal layouts, research has produced a multitude of optimization models for the BAP, the QCAP, and the QCSP. Moreover, a trend towards an integrated solution of these problems is observed in the recent literature. The large number of available models and proposed solution methods prevents an easy choice of a suitable approach in a specific situation. To provide a support in modeling problem characteristics and in suggesting applicable algorithms this paper develops classification schemes for BAPs, QCSPs, and integrated approaches.

The paper is organized as follows. In Section 2 the focused operational planning problems are described in detail against the background of different terminal properties and objectives. A literature survey of BAP and QCAP formulations is presented in Section 3 which is derived from a new classification scheme for these problems. Accordingly, a classification scheme and a literature survey are presented for QCSP formulations in Section 4. Since future advances in the field are expected from integrated solution approaches, Section 5 provides a literature review of the state-of-the-art integration concepts. The paper is summarized in Section 6.