Enriching the Berth Allocation Problem

R. Van Schaeren, W. Dullaert, B. Raa

Since the 80s, the annual growth rate of seaborne trade has been 3.7 percent on average (Grossmann et al., 2007). Container growth rates, however, have been significantly higher. According to leading maritime analyst Drewry Shipping Consultants (2007, 2008), the number of full teu’s shipped on worldwide trade routes more than doubled from 69.6 million teu in 2000 to 141.2 million teu in 2007, representing an average annual growth rate of no less than 10.6%. This growth rate is expected to continue in the short-term future: by the year 2012 Drewry forecasts a worldwide container traffic of 223.7 million full teu’s, i.e. an increase of nearly 60% compared to the 2007 figure. Additional container handling is generated by the hub-and-spoke strategy, in which larger ports (hubs) serve as ports of call and smaller ports (spokes) offer additional cargo via feeder lines. Figures on total throughput handled by the world’s ports are therefore more suited to illustrate the increasing demand for container handling capacity. For 2007, the total volume handled at the world’s ports is estimated at 493.2 million teu (including empties and transshipment), a figure expected to increase with some 57% up to 773.7 teu in 2012 (Drewry Shipping Consultants, 2007, 2008). As argued in Vernimmen et al. (2007), many shipping lines have anticipated on the increased demand for container transport by ordering additional and larger vessels. According to AXS-Alphaliner (2008), the total cellular containership fleet at 01/01/2008 consisted of 4320 vessels for a combined capacity of 10.92 million teu slots. Based on the shipping lines’ order books as at 01/04/2008, these figures are expected to increase to 5813 vessels and 17.69 million teu, respectively, by 01/01/2012. Hence, the total slot capacity provided by the world cellular fleet will increase by more than 60% in four years time, or nearly 13% per year. In contrast, many planned investments in additional container terminal infrastructure in Northern European ports (such as Le Havre, Antwerp, Rotterdam, Wilhelmshaven, Flushing and ports in the UK) have been delayed for several years or even cancelled altogether. If all these proposed projects would have been realized in accordance with their original time schedule, an extra capacity of no less than 11.4 million teu (nearly one third of the capacity available in 2004) would have been available in North European ports in 2005 (Vernimmen et al., 2007). Increasing container handling capacity by expansion projects appears to be difficult for environmental, financial, technical and legal reasons. In many cases there is even no land available to build additional infrastructure. Optimizing the processes of existing infrastructure is therefore often a better – if not only – way to increase the handling capacity. The productivity of a container terminal is determined by the interaction of a number of processes. Based on the academic literature devoted to them, the best-known processes are probably berth planning (which allocates vessels at the available quays) and quay crane planning (which assigns the available cranes to the vessels alongside the quays). Other important, but less studied processes are yard planning (for allocating all the containers handled by the terminal on a yard), vessel planning (positioning of the containers on board of vessels) and labor planning (assigning people to all the jobs to be carried out). This paper will focus on the berth planning and quay crane planning processes, the most studied container terminal processes from the academic literature. Section 2 presents a focused literature review on the Berth Allocation Problem (BAP) and the Crane Allocation Problem (CAP). In Section 3, we propose an extended model for the combined BAP and CAP, accommodating some of the shortcomings of the existing models identified in Section 2. This model is validated in Section 4 using real-life data. Section 5 concludes and offers directions for further research.

« Terug