THE BERTH ALLOCATION PROBLEM: OPTIMIZING VESSEL ARRIVAL TIMES
Abstract: The Berth Scheduling Problem (BSP) deals with the assignment of vessels to berths in a marine terminal, with the objective to maximize the ocean carriers’ satisfaction (minimize delays) and/or minimize the terminal operator’s costs. In the existing literature, two main assumptions are made regarding the status of a vessel: a) either all the vessels to be served are already in the port before the planning period starts, or b) they are scheduled to arrive after the planning period starts. The latter case assumes an expected time of arrival for each vessel which is a function of the departure time of the vessel from the previous port, the average operating speed, and the distance between the two ports. Recent increases in fuel prices have forced ocean carriers to reduce current operating speeds, while stressing to the terminal operators the need to maintain the integrity of their schedule. In addition, several collaborative efforts between the industry and government agencies have been proposed aiming to reduce emissions from marine vessels and port operations. In light of these issues, this paper presents a berth scheduling policy to minimize vessel delayed departures and indirectly reduce the fuel consumption and emissions produced by the vessels while in idle mode. Vessel arrival times are considered as a variable and are optimized to accommodate the objectives of the proposed policy while providing ocean carriers with an optimized vessel speed. Example problems using real world data show that the proposed policy reduces the amount of emissions produced by vessels at the port in idle mode, optimizes fuel consumption and waiting time at the port by reducing vessel operating speeds to optimal levels and minimizes the effects of late arrivals to the ocean carriers’ schedule.
Keywords: Planning and scheduling, Resource allocation, Container Terminals, Berth Scheduling, Emissions, Optimization
INTRODUCTION
Congestion in container terminals, fierce terminal competition, the ever increasing role of the time factor in liner shipping (Noteboom, 2006) and the pressure by liner shipping operators for increased effectiveness and punctuality of services (berthing and vessel loading/unloading operations) exacerbate the need for improved container terminal seaside operations. The objective of terminal operators is to find vessel to berth assignments (also known as the berth scheduling problem) to reduce vessel turnaround time, increase port throughput, and keep customer satisfaction at a desired level. The later typically depends on contractual agreements through which terminal operators may provide differentiated services to customers with high container volumes or large number of vessels calling at the port.
Cost is the most important parameter for the ocean carriers and is a key parameter when berth schedules are defined. Startlingly, ocean carriers have calculated that fuel now accounts for more than 60% of operating costs and have taken almost unprecedented immediate measures to slow ships to economic speeds of 20knts from 25knts. Moreover, the ocean carriers are stressing the increased schedule integrity and the ensuing benefits to the environment (Wacket, 2007). It is of little surprise, therefore, that CEOs and senior executives, such as Adolf Adrion (Hapag-Lloyd), Koji Miyahara (NYK Line), Eivind Kolding (Maersk Line) and Akimitsu Ashida (Mitsui OSK Lines), have slowed down their ships on several routes, seek for short wait time and handling times at the terminals, setting fuel as one of their single biggest challenges in 2008. (Fossey, 2008).
In addition to the ocean carrier profit concerns, rapid growth in container freight volumes increases the need to work on emission reduction and mitigation strategies[i]. In certain regions, large container terminals have been singled out as the largest source of air pollution (e.g. Port of Los Angeles and Long Beach[ii]). The diesel engines that power almost all port activities, including container vessels, are concentrated sources of diesel emissions, and they are often located near large urban centers affected by pollution from other diesel-powered vehicles. Although, trucks have been identified as the major source of emissions at container terminals, container vessels have their own contribution (Lazic, 2004) and it has been estimated that vessel hotelling[iii] emissions can make up a major portion of total port emissions (ICI, 2005). Several collaborative efforts between the industry and government agencies demonstrating emission reduction options for marine vessels and port operations have been proposed that mainly focus in the use of alternative fueling sources for the vessels while at port. The interested reader is referred to the website of the Clean Ports USA for a number of relevant publications[iv].
In the berth scheduling problem (BSP), vessels arrive over time at a port and the terminal operator assigns them to berths for unloading and loading of containers based on several factors and considerations (Theofanis et al., 2009). Three broad classification schemes of the BSP may be specified: a) the discrete vs. continuous berthing space, b) the static vs. dynamic vessel arrivals, and c) the static vs. dynamic vessel handling time. The discrete problem (Hansen et al., 2008; Imai et al., 1997; Imai et al., 2001; Imai et al., 2003, Imai et al., 2007) considers the quay as a finite set of berths. In the continuous problem (Guan and Cheung, 2004; Imai et al., 2005; Kim and Moon, 2003; Moorthy and Teo, 2006; Park and Kim, 2003) vessels can berth anywhere along the quay. In the static arrival problem all the vessels to be served are already in the port, while in the dynamic arrival problem, adopted by the majority of the literature, not all the vessels to be scheduled for berthing have arrived at the time scheduling begins, although estimated arrival times are known in advance and are used in the models. Finally, in the static handling time problem (Hansen et al., 2008; Imai et al., 1997) the vessel handling time is considered to be known, whereas in the dynamic (Park and Kim, 2003; Imai et al., 2008) it is a variable. For a detailed review and critical analysis of the current literature on berth scheduling we refer to (Theofanis et al., 2009). Defining the best berth scheduling policy for each port operator depends on several factors, including the type and function of the port (common use or dedicated facility, transshipment hub etc), size, location, nearby competition, types of contractual agreements with the ocean carriers. All these factors have different effects to the desired objective, which could be the customer level of service (e.g. delayed departure) and/or the environmental effects of the vessel while at the port (e.g. emissions). Several berth scheduling policies and related factors have been captured by academic research, however, to date, environmental considerations have not been included in BSP formulations.
In light of these issues this paper presents a berth scheduling policy, a model, and a resolution algorithm for the discrete berthing space and dynamic vessel arrival, where vessel arrival times are optimized. This is achieved by assuming that vessel arrival times are variable with upper and lower bounds. The objective of the proposed policy is to reduce vessel fuel consumption and the amount of emissions produced by the vessels while in the port, by minimizing the vessel waiting time; an emissions mitigation operational strategy proposed by the Office of Natural and Human Environment, U.S. Federal Highway Administration in 2005 (ICI, 2005). Reducing the total in port wait time and allowing the arrival time to vary could lead to very low levels of service for the port (i.e. jeopardize the integrity of the ocean carriers’ schedule). To account for this issue the policy’s objective also includes the minimization of the vessels’ delayed departures, which are estimated based on requested departure times set by the ocean carriers. The proposed berth scheduling strategy has a positive effect not only on the environmental aspects of the problem but is also beneficial to the ocean carriers, as described in more detail in the next section. To our knowledge this is the first berth scheduling study to appear in the literature that optimizes vessel arrival times and considers the environmental aspect of seaside operations at a container terminal. Example problems using real world data are presented to critically discuss the berth scheduling policy benefits against the constant vessel arrival time formulation.
The rest of the paper is structured as follows: The next section presents the model formulation while the third section presents the solution approach. A number of numerical results are presented in the fourth section and the last section concludes the paper.
PROBLEM DESCRIPTION
Container vessels at marine terminals arrive over time and terminal operators seek to assign them to berths to be served and depart as soon as possible. As discussed in the introductory section container vessel operators have two important objectives: a) minimize fuel consumption and b) keep the integrity of their schedule (e.g. minimize delayed departures). Until today berth scheduling studies assumed the arrival time of a vessel to have a fixed and known value. This value was obtained from the ocean carrier and was estimated based on the vessels’ departure time from the previous port, the average operating vessel speed, and the distance between the two ports (i.e. port of origin and destination). As previously discussed ocean carriers have been adjusting their operating speed to more fuel efficient levels. To capture their ability to do so, in this paper we introduce vessel arrival time as a variable and assume that the ocean carrier will provide the terminal operator with a range for the vessel arrival time. The terminal operator will schedule for all the vessels using these ranges, optimizing for the vessels’ arrival time. In this paper we assume that the upper bound of the arrival time is equal to the estimated arrival time with an operating vessel speed of 25 knots, which has been the practice so far, and the lower bound equal to the estimated arrival time with an operating vessel speed of 15 knots.
Vessel arrival times are optimized to achieve two objectives: a) minimize the total waiting time of all the vessels, thus reducing vessel fuel consumption and vessel emissions while in idle mode, and b) minimize the delayed departures of the vessels. To accommodate an environmentally friendly berth scheduling policy, vessel waiting time is weighted using a coefficient that corresponds to the emissions produced hourly by the vessel in idle mode.
Adopting a strategy where vessel arrival time is defined as a variable instead of a constant and the vessel waiting time is weighted to capture the environmental effects of the vessel while at the port, is a beneficial approach for all the users of the system (i.e. public, marine terminal operators, ocean carriers). This win-win situation can decrease the pollution produced by container vessels and at the same time provides fuel efficiency and schedule integrity for the ocean carriers. The approach described herein guarantees that the final solution at worst will be equal to or better than the solution obtained using a constant arrival time. As the difference between the upper and lower bound of the variable arrival time increases, the possibility of obtaining a better solution using the variable arrival time increases. We should point out that existing berth scheduling models cannot be modified to take variable times into account without affecting the structure of the problem. The introduction of the arrival time as a variable would lead to a non-linear space in terms of the objective function and/or the constraints thus complicating the model formulation and resolution approach.
Formulation of the problem
In the developed model presented herein we assume that the wharf is divided into a number of berths and each berth can service one vessel at a time regardless of the vessel’s size. We also assume that the handling time of the vessel is commensurate to its handling volume and dependent on the berth assigned and once a vessel has moored, it will remain in its location until all the required containers processing is done. Finally the model assumes that vessels could arrive at a variable arrival time which is between an upper and lower bound which includes the scheduled arrival time of the vessel.
To formulate the problem we define the following notation:
Setsi B / Set of berths, i=(1,……,I)
j V / Set of vessels, j=(1,….,J)
k K / Set of service orders, k=(1,….,J-I+1)
Parameters
Si / Time when berth becomes idle for the first time in the planning horizon
HTij / Handling time of vessel j at berth i
/ Earliest arrival time of vessel j(Arrival time lower bound)
/ Latest arrival time of vessel j(Arrival time upper bound)
DTRj / Departure time request of vessel j
wj / Amount of emissions produced hourly by vessel j in idle mode
M / Large positive number
Decision variables
/ Idle time of berth i between start of service of vessel j as the kth vessel, and the departure of its immediate predecessor
/ 1 if vessel j is served at berth i as the kth vessel, and zero otherwise
/ Waiting time of vessel j served at berth i as the kth vessel
Aj / Arrival time of vessel j
DDijk / Departure delay of vessel j served at berth i as the kth vessel
The problem can then be formulated as follows:
(1)
Subject to:
(2)
(3)
(4)