Original Article

A methodology to assess vessel berthing and speed optimization policies J . F e r n a n d o A l v a r e z * , To r e L o n g v a a n d E r n a S . E n g e b r e t h s e n Det Norske Veritas, Høvik 1322, Norway. E-mails: [email protected]; [email protected]; [email protected] *Corresponding author.

A b s t r a c t Standard ocean shipping contracts stipulate that a chartered vessel must sail at ‘utmost despatch’, with no consideration for the availability of berths at the destination port. The berthing policies used at many ports, which admit vessels on a first-come, firstserved basis, provide an additional incentive for the master to sail at full speed. These legacy contracts and berthing policies constitute a major driver of harbour congestion and marine fuel consumption, with adverse economic, safety, and environmental consequences. We propose a methodology to evaluate the potential benefits of new berthing policies and ocean shipping contracts. Given the importance of stochasticity on the performance of maritime transport systems, and the need to represent the efficient allocation of terminal resources, we have chosen a hybrid simulation-optimization approach. Our discrete event simulation model represents vessels and their principal economic and physical characteristics, the spatial layout of the terminal, performance of the land-side equipment, contractual agreements and associated penalties, and berthing policies. The proposed optimization model – a substantial extension of the traditional berth assignment problem – represents the logic of the terminal planner. The simulation program solves multiple instances of the optimization model successively in order to represent the progression of planning activities at the terminal. Maritime Economics & Logistics (2010) 12, 327–346. doi:10.1057/mel.2010.11

Keywords: berth allocation; vessel speed optimization; discrete event simulation; mixed integer programming

Introduction Standard ocean shipping contracts require a chartered vessel to proceed at ‘utmost despatch’ to its destination port, even if it is almost certain that the r 2010 Macmillan Publishers Ltd. 1479-2931 Maritime Economics & Logistics Vol. 12, 4, 327–346 www.palgrave-journals.com/mel/

Alvarez et al

vessel will have to dwell at anchor for several days before being admitted to a berth. The berthing policies at many major ports, which admit vessels on a first-come, first-served (FCFS) basis, represent an additional incentive for the master to sail at full speed. The widespread utilization of these legacy contracts and berthing policies constitute a major, and arguably unreasonable, driver of marine fuel consumption and harbour congestion. Given that the rate of fuel consumption of a vessel is approximately proportional to the cube of the vessel’s speed (Alderton, 2005), a more ingenious speed and berthing regime could result in substantial cost savings and a significant reduction of greenhouse gas emissions. This motivates us to consider alternative vessel berthing policies and contractual mechanisms that would allow the maritime transport industry as a whole to operate in a more environmentally responsible and economical manner. Some of the largest actors in maritime shipping have expressed strong support for such alternative contractual and coordination mechanisms. For instance, the virtual arrival initiative – a simple mechanism for reducing vessel speed and distributing the economic benefits among vessel owners and charterers – is backed by INTERTANKO and OCIMF (2010), two prominent maritime industry associations. Another example is that of the port of Newcastle, which has recently implemented a new berth allocation system to replace the traditional FCFS discipline (Corbett, 2009). The contribution of this article consists of a methodology to evaluate the benefits that can be derived from innovative berthing policies and ocean shipping contracts. Given the importance of stochasticity on the performance of maritime transport systems, as well as the need to represent the scheduling and allocation decisions made by the terminal staff, we propose a discrete event simulation model, with an embedded mixed-integer optimization routine, as the appropriate framework to assess new policies and contracts. Our simulation model represents the travel of vessels from their origin port to the focal port, as well as their interaction with the terminal planner. The logic of the terminal planner is modelled using a mixed integer programming (MIP) model that finds feasible assignments of berths and land-side equipment (LSE) to each vessel. Our MIP formulation is a substantial extension of the traditional berth assignment problem (see for example Moccia, 2004; Cordeau et al, 2005), as we include many additional considerations that are important in a practical setting. For instance, our model includes the fuel consumption of the vessels as a function of their speed, the compatibility between LSE and different merchandise types, the spatial configuration of the terminal, and the transfer of demurrage and despatch payments amongst stakeholders. Our article begins with a review of recent research into the berth allocation problem and vessel-terminal coordination. Next, we discuss the operation of the 328 r 2010 Macmillan Publishers Ltd. 1479-2931 Maritime Economics & Logistics Vol. 12, 4, 327–346

Methodology to assess vessel berthing and speed optimization policies

proposed simulation and optimization models. We then describe a brief case study, where we explore the insights that may be derived from employing the proposed methodology. The final section presents our conclusions and directions for future research.

Literature Review Previous research on modelling of port operations has been comprehensively presented by Vis and de Koster (2003); Steenken et al (2004); and Stahlbock and Vob (2007). Dragovic et al (2006) provide a review of previous research with a focus on vessel-berth interaction and planning. Cordeau et al (2005) propose various models and tabu search heuristics for the discrete and continuous berth allocation problem to minimize the vessel service time. Monaco and Sammarra (2007) extend the berth allocation problem model of Imai et al (2001) by proposing a new solution method based on Lagrangean relaxation. The authors distinguish between the static and dynamic problem cases. In the static case, all vessels are in the focal harbour at the start of the planning horizon. In the dynamic case, vessels continue to arrive throughout the planning horizon. In this sense, the optimization model we use to represent the planner’s logic is dynamic, as it takes into account vessels that are scheduled to arrive several hours after the start of the modelling horizon. Imai et al (2008) address a variation of the berth allocation problem at multi-user terminals, where vessels can be assigned to third-party facilities. An additional cost is incurred by the focal terminal for utilization of the external facilities. Therefore, the objective of the problem is to minimize the total service time of vessels at the external terminal. A genetic algorithm is developed and a wide variety of numerical experiments show that the heuristic performs well. Lee et al (2008) study the problem of quay crane allocation and scheduling at container terminals. Their aim is to minimize the makespan of a single vessel by sequencing the handling of its holds, while preventing interference between multiple quay cranes. A MIP formulation and a genetic algorithm are proposed. Computational results indicate that the proposed genetic algorithm is efficient in solving the quay crane scheduling problem. Queuing theory has been used to examine many aspects of the performance of ports and terminals, including berth occupancy, harbour congestion, vessel dwell times and LSE utilization rates. Sabria and Daganzo (1989) focus on modelling the random arrival process and try to derive approximate analytical expressions for waiting times in queuing systems with scheduled arrivals. Daganzo (1990) studies a queuing model for a vessel terminal serving liner and r 2010 Macmillan Publishers Ltd. 1479-2931 Maritime Economics & Logistics Vol. 12, 4, 327–346 329

Alvarez et al

tramp traffic. The liner traffic is scheduled and is given higher priority than tramp traffic, which arrives randomly. Analytical expressions are derived to estimate the throughput rates of tramp traffic. These expressions also provide an estimate of the benefits that would accrue from expanding the port facilities. Asperen et al (2003) assess the impact of different vessel arrival processes on the efficiency of the loading and unloading systems at a chemicals terminal. The authors compare three arrival processes for modelling vessel arrivals and their effect on berth utilization and required tank capacity. The arrival processes include stock-controlled (arrivals scheduled to maintain the base stock levels at storage tanks), equidistant and uncontrolled (following a Poisson distribution). Their simulation runs show that the stock-controlled arrival process is the most efficient. This remains true regardless of the utilization of service priority rules. Hartmann (2004) proposes an algorithm for generating modelling scenarios for the simulation and optimization of container terminal operations. A scenario consists of arrivals of deep-sea vessels, feeder vessels, trains and trucks, as well as the associated vessel stowage plans. Strandenes and Wolfstetter (2005) propose auctions for the allocation of berth slots and times. In the proposed auction – described as a revelation mechanism – the bidders are asked to report their profits from being served at each feasible time slot. The auctioneer selects the allocation that maximizes the combined welfare of all bidders, which is represented by the sum of all bids. Bidders are required to pay a service price for the slot allocated to them, and receive a selling price if they already own a slot and supply it to the auction. Dragovic et al (2005) examine the use of vessel classes to assign LSE and berthing priorities to incoming vessels. The vessel size and quay crane requirement for each call are drawn from empirical distributions. Vessels are given a berthing priority according to their size. Vessels with low priority, or within the same priority class, are admitted based on a FCFS discipline. The results show that assigning higher priority to smaller vessels can lead to an improvement of the main operational parameters of the terminal. Dragovic et al (2006) propose an analytical queuing model and compare it to simulation results of Dragovic et al (2005). Dahal et al (2003) model the performance of bulk terminals using a simulation tool with an embedded optimization component. The goal of their study is to determine the operational strategies and LSE deployment that minimize the total operating costs of the terminal. The total operating cost includes the demurrage costs as well as costs for equipment operation. The optimization component, which is implemented using a genetic algorithm, generates a number of trial solutions, which are then passed to the simulation layer for cost and feasibility evaluation. A significant improvement of the operational and 330 r 2010 Macmillan Publishers Ltd. 1479-2931 Maritime Economics & Logistics Vol. 12, 4, 327–346

Methodology to assess vessel berthing and speed optimization policies

economic performance of the simulated terminals results from the application of the embedded optimization solver. Golias et al (2009) present the first berth allocation model that considers the environmental impact of vessel speed. In view of the combinatorial complexity of this model, a genetic algorithm is proposed.

Mathematical Model Our goal is to evaluate the potential economic and environmental benefits of new berthing policies and charterparty contracts. The proposed framework consists of a discrete-event simulation model with an embedded optimization routine to represent the terminal planner’s planning process. We describe these two components in the following subsections. Simulation model We have implemented our simulation as object-oriented C þþ code, with the intention that the model may be easily configured to describe a wide variety of terminal layouts, vessel calling schedules and berthing policies. The simulation model starts by setting up the physical characteristics of the focal port. This includes the spatial layout of the terminals and their berths, the availability of LSE at each berth, and the material handling capabilities of each LSE unit. Next, the model generates a list of vessel calls to be simulated. Our current implementation allows for the generation of the vessel call data from historical data or based on empirical probability distributions. To simplify our discussion, we assume that all vessels are unloading merchandise. The description of each vessel call includes the following: K

K

The physical and operational properties of the vessel: deadweight tonnage (dwt), main engine power, draft, length, speed range and fuel consumption curve. The contractual agreements associated to the call. The vessel is given a laytime and a cancellation time, respectively the earliest and latest time at which the vessel may commence unloading operations. Together, these two terms constitute the laycan for a vessel call. A cancellation penalty must be paid by the owner to the charterer if the vessel is not available for terminal operations before the cancellation time. The vessel must complete its unloading operations within a specified number of hours – the layhours. Demurrage is paid by the charterer to the owner when the terminal operations last longer than the layhours. Despatch is paid by the owner to the r 2010 Macmillan Publishers Ltd. 1479-2931 Maritime Economics & Logistics Vol. 12, 4, 327–346 331

Alvarez et al

K

K

charterer if the vessel is processed in fewer than the specified layhours. We refer the reader to Alderton (2005) for a more detailed discussion of these contractual terms. Initial sailing pattern, including distance from the focal port, actual and planned speed. Vessel load condition, including merchandise type and amount.

The simulation model inserts one initialization event for each vessel in the model, corresponding to the departure of vessels from their ports of origin. Then, the program simulates the progression of the event types that are listed below. As each event is executed, it may schedule other events to occur at some point in the future. For instance, when the vessel starts its unloading operation, the model schedules the termination of the operation at a time that is computed based on the load of the vessel, the number of LSE units assigned to the vessel and the LSE’s capabilities. The arrows in Figure 1 show how the occurrence of each event type may trigger the occurrence of other events. K

K

K

K

K

DEP. Vessel departs from remote port. The vessel will then proceed towards the focal port at full speed. COM. Vessel communicates with the planner of the focal port. Depending on the policy being modelled, the planner may dictate a speed to the vessel master. If a speed is dictated, we assume that the vessel master will follow this recommendation for the remainder of the voyage. In our current implementation, communication with the vessel is initiated once the vessel is within a specified distance (for example 500 miles) of the focal port. ARR. Vessel arrives at focal harbour. The vessel will remain idle until it is instructed to proceed to a berth. START. Vessel starts work. The vessel is berthed, and the LSE that has been allocated to it commences operations immediately. INC. Increase LSE allocation. One or more LSE units (which were perhaps previously assigned to another vessel) begin work on a given vessel.

Figure 1: Event scheduling in the simulation model. 332 r 2010 Macmillan Publishers Ltd. 1479-2931 Maritime Economics & Logistics Vol. 12, 4, 327–346

Methodology to assess vessel berthing and speed optimization policies

K K

EXIT. Vessel concludes land-side operations. The vessel exits the system. PLAN. This event represents the optimization exercise conducted by the terminal planner. Using the best information available at the time, the terminal planner decides on the allocation of berths and equipment to each vessel. Depending on the policy being evaluated, the planner will also determine the optimal speed for each vessel. As a result of the planning activity, the planner gives a ‘ticket number’ to each vessel, which will dictate the berthing priority of the vessel. Depending on the policy being modelled, the priority of a vessel may change at any time before commencing work. We emphasize that the planning event is called multiple times throughout the simulation as new information is revealed to the planner. For instance, the planner will generate an initial plan based on a vessel’s estimated arrival time, which is computed at a COM event. The planner will revise the plan when the actual arrival time is revealed, corresponding to the ARR event.

The simulation terminates when all vessels have exited the system. Detailed statistics regarding travel times, dwell times, service times, fuel consumption and equipment utilization rates are recorded throughout the simulation. Optimization model We now present the berth, LSE and speed optimization problem (BESOP), starting with a detailed description of our notation. The following sets are used in our formulation. Sets T V UNREG V STEAM V DWELL V WIP V B C G c,b

All periods in the planning horizon of the current optimization instance. Vessels that have departed from a remote port, but have not communicated with the terminal. Vessels that have registered with the terminal and are steaming towards the focal harbour. Vessels that have arrived in the focal harbour and are waiting to berth. Vessels that have berthed at the focal port and are being handled by LSE. All vessels in the model. V ¼ V UNREG [ V STEAM [ V DWELL [V WIP All berths in the focal terminal. All LSE units at the focal port. LSE overtaking restriction sets. This allows us to represent groups of LSE that use a single set of rails to travel along the quay, and cannot overtake each other. For instance, if G c,b ¼ {c 0 , b0 } LSE c

r 2010 Macmillan Publishers Ltd. 1479-2931 Maritime Economics & Logistics Vol. 12, 4, 327–346 333

Alvarez et al

P

v

Lb Xb X~ ~ W

cannot be located at berth b when LSE c 0 is at berth b0. Berth-LSE combinations that are compatible with vessel v (based on, for instance, draft limitations, merchandise type carried by the vessel and so on). PvDB  C. Berths that are not aligned with berth b. If b0 ALb, a vessel cannot simultaneously use berths b and b0. Berthline continuity sets. If (a, c)AXb, a vessel cannot dock at berths a and c if it is not also occupying berth b. Initial assignment of berths to vessels for the current optimization ~ problem. XDB V Initial assignment of LSE to vessels for the current optimization ~ problem. WDC V

The following parameters describe the properties of the vessels, the spatial layout of the terminal, the properties of the LSE in the terminal, and the contractual terms of the port calls. Parameters e oc rcv t0f t0 tmax ot st lb lv lv sv

sv sv kvs dv

Price per ton of bunker fuel Hourly operational cost for LSE c Hourly throughput of LSE c for vessel v (determined by the type of merchandise on the vessel) Current simulated time – start of the current optimization planning horizon. Possibly a fractional value t0 ¼ It0fm Last period in the planning horizon of the current optimization instance Length of time period t Start time of time period t Length of berth b Vessel load, number of cargo units to be handled at focal port Length of vessel v Fixed speed of vessel v. The group of vessels that is considered to have a fixed speed will depend on the policy that is being used in the simulation layer. The speed of other vessels is represented using the decision variables U sv (described below) Maximum speed that can be achieved by vessel v Minimum speed sustainable by vessel v Fuel consumption (tons per hour) of vessel v when steaming at speed s Current distance of vessel v from the focal port

334 r 2010 Macmillan Publishers Ltd. 1479-2931 Maritime Economics & Logistics Vol. 12, 4, 327–346

Methodology to assess vessel berthing and speed optimization policies

fv gv hv iv jv kv nv dv1 ; v2 M

Demurrage rate for vessel v Despatch rate for vessel v Cancellation penalty for vessel v Cancellation time for vessel v Lay time for vessel v Lay hours for vessel v Number of holds in vessel v Binary indicator, 1 if vessel v1 has priority over v2 A large integer

We emphasize the importance of parameters ot, which allow us to define time periods of different lengths. If we attempt to represent the entire optimization planning horizon using, for example, hourly intervals, the number of binary variables in the problem instances grows beyond the capabilities of existing MIP solvers. In addition, it seems unwise to employ much precision when addressing decisions that will occur in the distant future. Rather, given the high level of uncertainty that characterizes vessel and port operations, we propose a model where the temporal resolution becomes gradually coarser as we refer to decisions that are further into the future. We now present the decision variables that are used in our formulation. Binary decision variables Wtvc Xtbv Ytbc Ktbvc Stv Ftv U sv Zv

Indicates whether LSE c will be assigned to vessel v during period t Indicates whether vessel v will be anchored at berth b during period t Indicates whether LSE c will operate in berth b during period t Indicates whether LSE c will be assigned to vessel v when it is anchored at berth b during period t Indicates whether vessel v has started land-side operations by period t Indicates whether vessel v has concluded land-side operations by period t Indicates whether vessel v will travel at speed s Indicates whether vessel v exceeds the cancellation time

Continuous, non-negative decision variables Ov Av Dv Ev

Fuel consumption of vessel v over the current planning horizon Time of arrival of vessel v at the focal harbour Duration of operations on vessel v beyond the agreed upon layhours kv Earliness of the conclusion of operations on vessel v with respect to the layhours kv r 2010 Macmillan Publishers Ltd. 1479-2931 Maritime Economics & Logistics Vol. 12, 4, 327–346 335

Alvarez et al

The constraints in our model link variables Xtbv, Ytbc, Wtvc and variables Ktbvc. vc While it is possible to eliminate variables Ybc t and Wt from the formulation, we prefer to retain them, as their use facilitates the presentation and understanding of our model. [BESOP] minimize XXX

ot  oc  Wtvc

ð1Þ

t2T c2C v2V

X

þ

e  Ov

ð2Þ

v2V UNREG

þ

X

f v  Dv 

v2V

X

g v  Ev þ

v2V

X

hv  Z v

ð3Þ

v2V

Expression (1) represents the operational expenditures from LSE operations over the optimization planning horizon. Expression (2) computes the fuel cost incurred by the vessels that will be assigned a speed in the current planning exercise (fuel consumption for the other vessels is constant, so we omit it from the objective function). Expression (3) computes the demurrage and cancellation penalties, as well as the despatch credits, that may be incurred by the vessels. Subject to: Xtav þ Xtcv pXtbv þ 1 v 2 V 0

Xtbv þ Xtb v p1 v 2 V 0 0

Ytbc þ Ytb c p1 b 2 B

t2T t2T

c2C

b 2 Bv b2B

ða; cÞ 2 Xb 0

b 2 Lb

ðb 0 ; c 0 Þ 2 Gc;b

t2T

ð4Þ ð5Þ ð6Þ

Constraints (4), (5) and (6) represent the geometry of the berths and their accessibility to the LSE units. Constraints (4) state that a vessel cannot use more than one out of three aligned berths if it is not using the one in the middle. Constraints (5) prevent a vessel from docking at berths that are not aligned. Constraints (6) impede LSE units that move on a single set of rails to overtake one another. X

lb  Xtbv Xlv  ðSvt  Ftv Þ v 2 V

t2T

b2B

336 r 2010 Macmillan Publishers Ltd. 1479-2931 Maritime Economics & Logistics Vol. 12, 4, 327–346

ð7Þ

Methodology to assess vessel berthing and speed optimization policies

X

ðt0 þ ot0  t0f Þ  rcv  Wtvc0 þ

tmax X

rcv  ot  Wtvc Xlv

v2V

ð8Þ

t¼t0 þ1

c2C

X

Wtvc pnv

v2V

t2T

ð9Þ

c2C

Constraints (7) require the entire length of the vessel to be accommodated in the terminal whenever the vessel is being served. Constraints (8) require a sufficient assignment of work time and LSE to unload the merchandise in each vessel. Constraints (9) limit the number of LSE units that can be assigned to work simultaneously on a vessel according to the number of holds in the vessel. X

Xtbv p1

b2B

t2T

ð10Þ

Ytbc p1 c 2 C

t2T

ð11Þ

Wtvc p1

t2T

ð12Þ

v2V

X b2B

X

c2C

v2V

Constraints (10) allow at most one vessel to be docked at a given berth during each time period. Constraints (11) stipulate that an LSE unit can only be present at one berth during a time period. Constraints (12) state that each LSE unit can be assigned to a single vessel during a time period. Ktbvc pYtbc þ Xtbv þ Wtvc Ytbc þ Xtbv þ Wtvc p2 þ Ktbvc X

ðb; cÞ 2 Pv

v2V v2V

ðb; cÞ 2 Pv

t2T t2T

ð13Þ ð14Þ

Ktbvc ¼ Wtvc

v2V

c2C

t2T

ð15Þ

Ktbvc ¼ Ytbc

b2B

c2C

t2T

ð16Þ

b2B

X v2V

Constraints (13), (14), (15) and (16) ensure that the decision variables Ktbvc are consistent with our definition of the variables Xtbv, Ytbc and Wtvc. t X

X ðc; bÞ2P

v

t 0 ¼t

v Ktbvc 0 pM  St

v2V

t2T

ð17Þ

0

r 2010 Macmillan Publishers Ltd. 1479-2931 Maritime Economics & Logistics Vol. 12, 4, 327–346 337

Alvarez et al

X ðc; bÞ2P tmax X

X v

ðc; bÞ2P

ðc; bÞ2P

v

v

t 0 ¼t

v Ktbvc 0 XSt

v2V

t2T

ð18Þ

0

v Ktbvc 0 pM  ð1  Ft Þ

v2V

t2T

ð19Þ

t 0 ¼t tmax X

X

t X

v v Ktbvc v2V 0 Xð1  Ft  Z Þ

t2T

ð20Þ

t 0 ¼t

X

Svt  Ftv p

ðc; bÞ2P

Ktbvc

v2V

t2T

ð21Þ

v

Constraints (17) and (18) implement the definition of variables Stv, so that Stv ¼ 1 if and only if vessel v has been worked on during time periods up to and including t. Constraints (19) and (20) implement the converse definition for variables Ftv, so that Ftv ¼ 1 if and only if vessel v will be worked on during time periods following and including t. Note that by including Z v in constraint (20), we allow all Ftv to remain at 0 when a vessel is cancelled. Constraints (21) additionally prohibit a lapse in activity while a vessel is berthed.

X

Xtb0i vi ¼ 1 ðbi ; vi Þ 2 X~

ð22Þ

Wtv0i ci ¼ 1

~ ðci ; vi Þ 2 W

ð23Þ

Xtbi v pFtvi

ðbi ; vi Þ 2 X~

t2T

ð24Þ

Wtvci pFtvi

~ ðci ; vi Þ 2 W

t2T

ð25Þ

v2V:v6¼vi

X v2V:v6¼vi

Constraints (22), (23), (24) and (25) enforce the initial allocation of resources to vessels. Constraints (22) and (23) require the vessels to utilize the resources that were allotted to them for this period in previous iterations of the planning exercise. Constraints (24) and (25) prevent other vessels from using those resources until the vessel that was originally using them has concluded its service. Svt 1 þ Z v1 XSvt 02  Z v2

v1 ; v2 2 V

t; t 0 2 T : tXt 0

dv1 ;v2 ¼ 1 Pv1 \ Pv2 ¼ 6 +

ð26Þ

Constraints (26) enforce the priorities established by the active berthing policy. This constraint does not apply when two vessels do not compete for resources. bv Svt  Ftv  1pXtbv  Xtþ1

v2V

b2B

t; t þ 1 2 T

338 r 2010 Macmillan Publishers Ltd. 1479-2931 Maritime Economics & Logistics Vol. 12, 4, 327–346

ð27Þ

Methodology to assess vessel berthing and speed optimization policies

bv Xtbv  Xtþ1 p1  Svt þ Ftv

v2V

b2B

t; t þ 1 2 T

ð28Þ

Constraints (27) and (28) prevent a vessel from moving to a new berth once it has moored. st  Svt XAv  M  ð1  Svt Þ

v 2 V UNREG \ V STEAM

t2T

ð29Þ

v

v

A ¼ t0f þ

s X

ðU sv  dv =sÞ v 2 V UNREG

ð30Þ

s¼sv

Av ¼ t0f þ dv =sv

v 2 V STEAM

ð31Þ

v

s X

U sv ¼ 1

v 2 V UNREG

ð32Þ

ðU sv  kvs =sÞ v 2 V UNREG

ð33Þ

s¼sv v

v

v

O ¼d 

s X s¼sv

Constraints (29) require that all vessels arrive in the focal harbour before they can start work. Constraints (30) define the time of arrival for all previously unregistered vessels. Constraints (31) define the time of arrival for all vessels that are currently steaming towards the focal harbour, and that have already registered with the planner. We only show this constraint for consistency, as the arrival time for this group of vessels is fixed for the purposes of the optimization model. Constraints (32) ensure that the unregistered vessels are assigned a feasible speed. Constraints (33) compute the fuel consumption of unregistered vessels. jv  ðSvt  Ftv Þpst  ð1  Z v Þ v 2 V iv X

Svt X1  Z v

t2T

v2V

ð34Þ ð35Þ

t¼t0 tmax X

ot  ðSvt  Ftv Þ þ E v pDv þ kv

v2V

ð36Þ

t¼t0

E v pM  ð1  Z v Þ v 2 V Svt pð1  Zv Þ v 2 V

t2T

ð37Þ ð38Þ

When a vessel call is cancelled, constraints (34) and (35) have no effect. Otherwise, constraints (34) require that operations begin after the specified laytime, j v. Similarly, constraints (35) require that the vessel commences land-side r 2010 Macmillan Publishers Ltd. 1479-2931 Maritime Economics & Logistics Vol. 12, 4, 327–346 339

Alvarez et al

operations before the cancellation time, iv. If the vessel concludes operations early, constraints (36) will result in E v being set to the difference between the layhours and the number of hours spent during operations on vessel v. Conversely, if the operations on a vessel are delayed, the value of Dv will be set to the excess required time. Note that constraints (36) work well with expression (3) in the objective function only when the demurrage penalties are higher than the despatch credits (as is generally the case). Constraints (37) specify that no despatch credit can be obtained when the vessel call has been cancelled. Constraints (38) provide a formal definition of the call cancellation variables Zv – when the call is cancelled, the vessel will not start any land-side operations. Although problem BESOP is correctly stated above, our implementation includes a large number of additional valid inequalities (Bertsimas and Weismantel, 2005). These constraints are redundant for all feasible integer solutions, but eliminate a large number of fractional solutions. In our implementation, we also replace any instance of the parameter M by the smallest possible integer that has the same effect. These additional measures reduce the solution times for problem BESOP by an order of magnitude. Finally, we note that all decision variables and summations are defined exclusively over feasible combinations of vessels, LSE and berths. We have avoided this additional notation to improve the legibility of the present work.

Case Study Description The aim of our case study is to compare three berthing priority policies: FCFS, standardized estimated arrival time (SETA, Røsæg, 2009), and global optimization of speed berth, and equipment allocations (GOSBEA). We simulate terminal operations under all three policies, and compare the results in terms of: K

K K K

K K

total fuel consumption and fuel cost for all vessels in the simulation. We consider only the fuel consumed between the most recent port of departure and the focal port; average land-side service time for all vessels; average dwell time in the harbour for all vessels; cancellations. We tally the number of vessels that cannot start unloading operations ahead of their contractual cancellation time; balance of demurrage penalties and despatch credits for all vessels; total cost to the vessel operators, which is computed as the balance of fuel expenses, despatch credits and demurrage fees.

340 r 2010 Macmillan Publishers Ltd. 1479-2931 Maritime Economics & Logistics Vol. 12, 4, 327–346

Methodology to assess vessel berthing and speed optimization policies

Figure 2: Schematic representation of three policies.

Furthermore, we compare the three policies under two different market scenarios, resembling the positive market circumstances of 2008, and the depressed circumstances observed in 2009. We do this because demurrage, despatch and cancellation fees, which together constitute a major portion of the cost components considered by the terminal planner (see expression 3), are driven by the opportunity cost of the vessels, which is in turn dictated by market conditions. We now provide a precise description of the rules that are applied under each of the three policies under examination. Figure 2 shows the point at which the berthing priority and sailing speed are established under each of the policies. Note that the decisions of the terminal planner under any of the three policies can be modelled using formulation BESOP, provided we set the correct values for parameters dv1 ;v2 and sets VUNREG and VSTEAM. Under the FCFS policy, vessels are admitted to a berth in the order in which they arrive at the harbour. The priority criterion only applies to vessels that compete for the same berths or LSE units. The terminal planner attempts to minimize the sum of terminal operating expenses, cancellation fees, and the balance of demurrage fees and despatch credits. The planner is free to allocate LSE units to the vessels as he deems necessary. However, we require that, once an LSE unit has been assigned to a vessel, the LSE cannot be assigned to another vessel until work on the first vessel has concluded. The planner does not generate any speed recommendations in this policy. In order to model the planner’s decisions under FCFS with formulation BESOP, we set VUNREG ¼ VSTEAM ¼ +, and dv1 ;v2 ¼ 1 if v1 arrives at the harbour before v2. r 2010 Macmillan Publishers Ltd. 1479-2931 Maritime Economics & Logistics Vol. 12, 4, 327–346 341

Alvarez et al

Under policy SETA, vessels are admitted to the berths according to their estimated time of arrival, which we set to the laydays commencement date. Otherwise, the conditions listed under FCFS apply. In order to model the planner’s decisions under SETA, we set VUNREG ¼ VSTEAM ¼ +, and dv1 ;v2 ¼ 1 if jv1 ojv2 in formulation BESOP. Under policy GOSBEA, vessels are provided a recommended speed when they are 500 nautical miles from the focal port (or at the moment of departure from the origin port, if this port is within 500 miles of the focal port). The speed of each vessel is optimized only once. Thereafter, the speed of the vessel is assumed to be fixed to the recommended value. The priority of the vessel is set to its estimated arrival time, under the assumption that it sails at the recommended speed. Every time a vessel v registers with the planner, we solve problem BESOP, and set VUNREG ¼ {v}. We set dv1 ;v2 only for vessels that have previously registered with the planner, as the ETA of other vessels is unknown. Table 1 summarizes the main properties of the vessels in our simulations, which include Handysize, Handymax, Panamax and small to large Capesize bulkers. We have adapted the deadweight tonnage (dwt) distribution from Dalsøren et al (2009). We estimate the power, length, draft and speed ranges for each category of vessels using Lloyds Register Fairplay (2009) and Mjelde et al (2009). The minimum vessel speed is given by a random variable with uniform distribution between 10 and 14 knots. The maximum speed is set to 4 knots above the minimum speed. Fuel consumption is determined using the cube law and estimated coefficients provided by Alderton (2005). We set bunker fuel

Table 1: Summary of vessel and contract properties HandySize Frequency (%) dwt (000 t) MinSpeed (kn) MaxSpeed (kn) Holds Power (KWh) Length (m) Draft (m) kv, 14 ¼ Fuel cons. at 14kn (t/day) kv, s ¼ Fuel cons. at s (t/day) Load (t) Distance from focal port (nmi) 2009 Charter rate ($/day) 2008 Charter rate ($/day) Demurrage ($/day) Despatch ($/day) Cancellation ($/day) Laytime (hour)

40 U(10, 40) U(10, 14) MinSpeed þ 4 4

Charter rate 0.5  Charter rate 100  Charter rate 72

Handymax

Panamax

26 23 U(40, 60) U(60, 100) U(10, 14) U(10, 14) MinSpeed þ 4 MinSpeed þ 4 5 6 3486  log (dwt)29150 53  log (dwt) 375 8.9 þ dwt  6  105 19.5 þ dwt  0.00034 kv,14  s3/143 U(0.8 dwt,dwt) U(400, 2400) 0.1629 *dwt þ 5431 0.58 * dwt þ 12765

72

96

Capesize 11 U(100, 200) U(10, 14) MinSpeed þ 4 8

120

342 r 2010 Macmillan Publishers Ltd. 1479-2931 Maritime Economics & Logistics Vol. 12, 4, 327–346

Methodology to assess vessel berthing and speed optimization policies

Figure 3: Schematic representation of the terminal.

price at US$500 per ton (Bunkerworld, 2010). We derive an approximation for the charter rate of a vessel in the years 2008 and 2009 as a function of dwt, based on reports from Clarksons (2010). The demurrage rate is set to the charter rate, the despatch rate is set to half the demurrage rate and cancellation penalties are set to 100 times the demurrage rate. Vessels are assigned laydays commencement times at the focal port following a Poisson distribution with mean vessel interarrival time of 8 hours. Vessels depart from ports that are located between 400 and 2400 nautical miles from the focal port, setting their initial speed to reach the focal port exactly at laydays commencement. The actual time required to complete the voyage is modified by adding a random delay (in hours) that is uniformly distributed in (8  d/500, 16  d/500), where d is the distance (in nautical miles) to be sailed. The terminal in the case study has six berths, divided in two sections, with depth limitations as indicated in Figure 3. The terminal has six LSE units, with the capacity to unload between 1000 and 6000 tons of merchandise per hour. Figure 3 also indicates the range of motion of each LSE unit. Case study results We ran a total of 120 replications, 20 for each of the three policies and for the market conditions of 2008 and 2009. Each replication represents 20 vessel calls, or roughly 1 week of port activities under our assumptions. We formulated problem BESOP in AMPL 11 (Fourer et al, 2003) and used Gurobi 2.0 (Gurobi Optimization, 2009) as the MIP solver. We used a workstation with a quad-core Xeon processor at 2.8 MHz. r 2010 Macmillan Publishers Ltd. 1479-2931 Maritime Economics & Logistics Vol. 12, 4, 327–346 343

Alvarez et al

Table 2: Selected performance indicators for three berthing policies 2008 market conditions

Total fuel consumption (tons) Average service time (hours) Average dwell time (hours) Total cancellations Total despatch ($000) Total demurrage ($000) Total fuel costs ($000) Total benefits to operators ($000)

2009 market conditions

FCFS

SETA

GOSBEA

FCFS

SETA

GOSBEA

1669 6.73 4.25 3 1425 0 834 591

1669 6.49 3.94 1 1592 0 834 758

1570 6.55 3.16 0 1675 0 784 891

1669 6.65 4.32 3 451 0 834 383

1669 6.52 3.96 1 503 0 834 331

1570 6.49 3.24 0 530 0 782 252

We list the main results of our experiments in Table 2. For dwell time and vessel service time, we provide average values, taken over all vessels that completed service and over all replications. We list the average over 20 replications of the total fuel consumption of all vessels, as well as the total demurrage and despatch incurred. We list the total number of cancelled vessel calls over all replications. Finally, we provide a balance of monetary benefits to vessel operators, which consists of despatch credits, less fuel expenditures and demurrage fees. We exclude cancellation fees from this tally. The results indicate that policy GOSBEA is clearly superior to both FCFS and SETA, while SETA is superior to FCFS. Using policy GOSBEA, the simulated planner can reduce fuel consumption by about 6 per cent, while reducing the number of cancellations, and accruing higher despatch credits to the vessel operators. The average dwell time in the harbour decreases by more than 1 hour per vessel relative to FCFS, and more than half hour per vessel compared to SETA. The average vessel service time is not significantly altered by different berthing policies.

Conclusions We have presented a model for evaluating berthing priority and speed optimization policies in a marine terminal. Our model utilizes discrete event simulation to represent the stochastic nature of vessel arrivals at a port. We employ an optimization model to represent the decisions of a terminal planner who allocates berth space and LSE to each vessel. We use the proposed model to evaluate the performance of three berthing priority policies: FCFS, SETA and GOSBEA. We conclude that policy GOSBEA is superior to policies SETA and FCFS. Furthermore, policy SETA is superior to FCFS. Significant reductions in overall 344 r 2010 Macmillan Publishers Ltd. 1479-2931 Maritime Economics & Logistics Vol. 12, 4, 327–346

Methodology to assess vessel berthing and speed optimization policies

fuel consumption, dwell times, cancellations and contractual penalties can result from the utilization of the GOSBEA policy. In particular, we note that it is possible to reduce overall fuel consumption (and therefore carbon emissions) while simultaneously obtaining net reductions in port congestion and contractual penalties to vessel operators. Although GOSBEA is clearly beneficial when all parties are considered jointly, we can anticipate that not every individual vessel operator would benefit from the scheme at every port call. For instance, the planner may request a vessel to sail faster than initially planned, even when the vessel is not at risk of missing its laycan. In such cases, the vessel operator may not be willing to expend additional fuel for the benefit of others. Such cases may well represent the biggest obstacle to the implementation of the GOSBEA policy. We believe that additional contractual mechanisms must be implemented in order to motivate all participants to comply with the directions of the planner, even when those directions may occasionally be against their immediate interests. The precise specification of such game-theoretical mechanisms constitutes an interesting direction for further research.

Editor’s Note The paper was the recipient of the Palgrave-Macmillan Prize for best paper in Maritime Logistics at the Lisbon IAME conference, July 2010.

Acknowledgement We gratefully acknowledge financial support from the Norwegian Research Council, Project 192930. We thank Magnus Eide and Trond Nilssen of Det Norske Veritas for initial conversations on the simulation model, as well as their help in assembling the data used in the case study.

References Alderton, P. (2005) Reeds Sea Transport Operations and Economics, 5th edn. London: Thomas Reed Publications. Asperen, E. van, Dekker, R., Polman, M.T.H. and Swaan Arons, H. de (2003) Modeling ship arrivals in ports. In: S. Chick, P.J. Sa`nchez, D. Ferrin and D.J. Morrice (eds.), Proceedings of the 2003 Winter Simulation Conference. 7–10 December, New Orleans, LA, pp. 1737–1744. Bertsimas, D. and Weismantel, R. (2005) Optimization over Integers. Charlestown, MA: Dynamic Ideas. Bunkerworld. (2010), http://www.bunkerworld.com/prices/, accessed 15 January 2010. Clarksons. (2010) Dry Bulk Trade Outlook, January 2010. London: Clarkson Research Services Limited. r 2010 Macmillan Publishers Ltd. 1479-2931 Maritime Economics & Logistics Vol. 12, 4, 327–346 345

Alvarez et al

Corbett, A. (2009) Safety push to cut traffic at Newcastle. Tradewinds, 16 October. Cordeau, J., Laporte, G., Legato, P. and Moccia, L. (2005) Models and tabu search heuristics for the berth allocation problem. Transportation Science 39(4): 526–538. Daganzo, C.F. (1990) The productivity of multipurpose seaport terminals. Transportation Science 24(3): 205–216. Dahal, K., Galloway, S., Burt, G. and McDonald, J. (2003) Port system simulation facility with an optimization capability. International Journal of Computational Intelligence and Applications 3(4): 395–410. Dalsøren, S., Eide, M., Endresen, Ø., Mjelde, A., Gravir, G. and Isaksen, I. (2009) Update on emissions and environmental impacts from the international fleet of ships. The contribution from major ship types and ports. Atmospheric Chemistry and Physics 9: 2171–2194. Dragovic, B., Park, N. and Radmilovi, C.Z. (2006) Ship-berth link performance evaluation: Simulation and analytical approaches. Maritime Policy & Management 33(3): 281–299. Dragovic, B., Park, N., Radmilovi, C.Z. and Maras, V. (2005) Simulation modelling of ship berth link with priority service. Maritime Economics & Logistics 7: 316–335. Fourer, R., Gay, D. and Kernighan, B. (2003) AMPL, A Modeling Language for Mathematical Programming, 2nd edn. Toronto: Thomson. Golias, M.M., Saharidis, G.K., Boile, M., Theofanis, S. and Ierapetritou, M.G. (2009) The berth allocation problem: Optimizing vessel arrival time. Maritime Economics & Logistics 11(4): 358–377. Gurobi Optimization. (2009) Gurobi Optimizer Reference Manual, 2nd edn, http://www.gurobi .com/html/doc/refman/, accessed 22 December 2009. Hartmann, S. (2004) Generating scenarios from simulation and optimization of container terminal logistics. OR Spectrum 26(2): 171–192. Imai, A., Nishimura, E. and Papadimitriou, S. (2001) The dynamic berth allocation problem for a container port. Transportation Research Part B 35(4): 401–417. Imai, A., Nishimura, E. and Papadimitriou, S. (2008) Berthing ships at a multi-user container terminal with a limited quay capacity. Transportation Research Part E 44: 136–151. INTERTANKO and OCIMF. (2010) Virtual Arrival – A Best Practice Guide. London: INTERTANKO and OCIMF. Lee, D.-H., Wang, H.Q. and Miao, L. (2008) Quay crane scheduling with non-interference constraints in port container terminals. Transportation Research Part E 44: 124–135. Lloyds Register Fairplay. (2009) World fleet database (all civilian ocean-going ships above 299 gt), http://www.lrfairplay.com/, accessed 30 October 2009. Mjelde, A., Fjell, C., Eriksen, S.M. and Frevaag, J. (2009) Tiltaksanalyse -krav om landstrøm for skip i norske havner. (in Norwegian). Det Norske Veritas, Oslo. Technical Report 1063. Moccia, L. (2004) New optimization models and algorithms for the management of maritime container terminals. PhD thesis, Universita degli studi della Calabria. Monaco, M. and Sammarra, M. (2007) The berth allocation problem: A strong formulation solved by a lagrangean approach. Transportation Science 41(2): 265–280. Røsæg, E. (2009) A system for queuing in ports. In: A. Pozdnakova (ed.) Scandinavian Institute of Maritime Law Yearbook 2008. Norway: Sjørettsfondet. Sabria, F. and Daganzo, C. (1989) Approximate expressions for queuing systems with scheduled arrivals and established service order. Transportation Science 23: 159–165. Stahlbock, R. and Vob, S. (2007) Operations research at container terminals – A literature update. OR Spectrum 30(1): 1–52. Steenken, D., Vob, S. and Stahlbock, R. (2004) Container terminal operation and operations research – A classification and literature review. OR Spectrum 26: 3–49. Strandenes, S. and Wolfstetter, E. (2005) Efficient (re-)scheduling: An auction approach. Economics Letters 89: 187–192. Vis, I. and de Koster, R. (2003) Transhipment of containers at a container terminal: An overview. European Journal of Operations Research 147: 1–16. 346 r 2010 Macmillan Publishers Ltd. 1479-2931 Maritime Economics & Logistics Vol. 12, 4, 327–346