Abstract
Purpose
The paper aims to propose a new mathematical model for allocation and scheduling of vessels at multiple marine container terminals of the same port, considering the access channel depth variations by time of day.
Design/methodology/approach
This paper proposes a new mathematical model for allocation and scheduling of vessels at multiple marine container terminals of the same port, considering the access channel depth variations by time of day. The access channel serves as a gate for vessels entering or leaving the port. During low-depth tidal periods the vessels with deep drafts have to wait until the depth of the access channel reaches the required depth.
Findings
A number of numerical experiments are performed using the operational data collected from Port of Bandar Abbas (Iran). Results demonstrate that the suggested methodology is able to improve the existing port operations and significantly decrease delayed vessel departures.
Originality/value
The contribution of this study to the state of the art is a novel mathematical model for allocation and scheduling of vessels at multiple terminals of the same port, taking into consideration channel depth variations by time of day. To the best of the authors’ knowledge, this is the first continuous berth scheduling linear model that addresses the tidal effects on berth scheduling (both in terms of vessel arrival and departure at/from the berth) at multiple marine container terminals.
Keywords
Citation
Dadashi, A., Dulebenets, M.A., Golias, M.M. and Sheikholeslami, A. (2017), "A novel continuous berth scheduling model at multiple marine container terminals with tidal considerations", Maritime Business Review, Vol. 2 No. 2, pp. 142-157. https://doi.org/10.1108/MABR-02-2017-0010
Publisher
:Emerald Publishing Limited
Copyright © 2017, Pacific Star Group Education Foundation
Nomenclature
Sets
- V = {1, 2, . . . , n}
= set of vessels
- Q = {0, 1, 2, . . . p}
= set of terminals
- T = {1, 2, . . . , u}
= set of time periods
Decision variables
- yi, i ∈ V
= berthing time of vessel i ∈ V
- xi, i ∈ V
= berthing position of vessel i ∈ V
- ri, i ∈ V
= departure time of vessel i ∈ V
- αij, i ∈ V, j ∈ V
= 1 if vessel i ∈ V departs before berthing time of vessel j ∈ V (= 0 otherwise)
- βij, i ∈ V, j ∈ V
= 1 if vessel i ∈ V is located on left side of vessel j ∈ V on the wharf axis, i.e. xi + li ≤ xj (=0 otherwise)
- δik, i ∈ V, k ∈ Q
= 1 if vessel i ∈ V is berthed at terminal k ∈ Q (=0 otherwise)
- sit, i ∈ V,t ∈ T
= 1 if vessel i ∈ V is moored at time t ∈ T (=0 otherwise)
- eit, i ∈ V,t ∈ T
= 1 if vessel i ∈ V departs at time t ∈ T (=0 otherwise)
Parameters
- ai, i ∈ V
= estimated arrival time of vessel i ∈ V
- Ri, i ∈ V
= requested departure time of vessel i ∈ V
- hi, i ∈ V
= estimated handling time of vessel i ∈ V
- li, i ∈ V
= length of vessel i ∈ V, including a safety distance between adjacent vessels
- Lk,k ∈ Q
= the coordinate of ending edge of terminal k ∈ Q
- di, i ∈ V
= draft of vessel i ∈ V
- Dk, k ∈ Q
= wharf depth of terminal k ∈ Q
- bit, i ∈ V,t ∈ T
= 1 if draft of vessel i ∈ V is less than the depth of access channel at time t ∈ T (=0 otherwise)
- Wi, i ∈ V
= priority weight for vessel i ∈ V
- M
= a sufficiently large positive number
1. Introduction
Maritime transport is a backbone of the international trade and a key engine driving globalization. Around 80 per cent of global trade by volume and over 70 per cent by value is carried by oceangoing vessels and is handled by ports worldwide (UNCTAD, 2015). Marine container terminals play a crucial role in the movement of freight and are a very important component of maritime transport. In the meantime, marine container terminals are the “weakest link” of the supply chain (along with other intermodal terminals and their surrounding network) due to potential delays, cargo loss and damage. As the container terminal business is capital intensive, terminal managers strive to improve utilization of the existing resources with operational changes rather than capital investment (Dulebenets, 2015). Such resources include berths, container storage yard and cargo handling equipment (e.g. quay cranes, yard cranes, internal transport vehicles, etc.). Among these resources, the optimal utilization of the berth space lies in the kernel position, as it affects quay crane scheduling, yard storage planning, internal transport vehicle routing and the vessel turnaround time. The latter is considered as one of the most important performance measures of a marine container terminal (Golias et al., 2009a; Du et al., 2011; Dulebenets, 2015).
The berth scheduling problem (BSP) aims to determine the assignment of vessels to berths, start service time for each vessel and the order of vessels at each berth. The published to date BSP papers can be classified based on three attributes: spatial attribute; vessel arrival attribute; and vessel handling time attribute. Based on the spatial attribute, BSP problems can be categorized into three groups: discrete; continuous; and hybrid. In case of a discrete berthing layout, the wharf is divided in certain number of berths, and only one vessel can be served at each berth at the time (Imai et al., 2001, 2003, 2007; Monaco and Sammarra, 2007; Hansen et al., 2008). As for continuous berthing layout, the wharf is limited only by its length and not partitioned in berths, and several vessels can be served as long as their overall length does not exceed the wharf’s length (Kim and Moon, 2003; Guan and Cheung, 2004; Imai et al., 2005; Moorthy and Teo, 2006; Meisel and Bierwirth, 2009). In case of a hybrid berthing layout, the wharf is divided in a certain number of berths, but larger vessels can occupy more than one berth, whereas several smaller vessels can be served at one berth (Bierwirth and Meisel, 2010, 2015). Based on the vessel arrival attribute, BSPs can be categorized in three groups: static vessel arrivals; dynamic vessel arrivals; and controlled vessel arrivals. In case of static vessel arrivals, all vessels have already arrived at the port, and the schedule should be constructed based on specific objective(s). As for dynamic vessel arrivals, approximate arrival times of vessels are known for a certain time horizon. In case of controlled vessel arrivals, the vessel arrival time is a variable and defined by the terminal operator within certain time windows usually based on contractual agreements (Golias et al., 2009b).
Based on the vessel handling time attribute, BSPs can be differentiated in two categories: fixed vessel handling time; and variable vessel handling time. In case of a fixed vessel handling time, the marine container terminal operator offers a constant vessel handling time over a given planning horizon, which depends on the quantity of quay crane used, quay crane productivity, storage yard capacity, etc. (Imai et al., 2001; Hansen et al., 2008). As for BSPs with variable vessel handling time, the handling time is usually assigned as a function of the quay cranes that will operate on the vessel and the distance from the vessel berthing position to a location in the storage yard, where the containers will be placed (Park and Kim, 2003). The majority of the BSP studies published to date considered discrete berthing layout, dynamic vessels arrivals and variable vessel handling times (Bierwirth and Meisel, 2010, 2015). Technical restrictions such as berthing draft, channel depth, inter-vessel and end-berth clearance distance are further assumptions that have been adopted only in a few studies dealing with the BSP, bringing the problem formulation closer to the real-world operations.
The contribution of this study to the state of the art is a novel mathematical model for allocation and scheduling of vessels at multiple terminals of the same port, taking into consideration the channel depth variations by time of day. To the best of the authors’ knowledge, this is the first continuous berth scheduling linear model that addresses the tidal effects on berth scheduling (both in terms of vessel arrival and departure at/from the berth) at multiple marine container terminals. The rest of the paper is organized as follows. The next section presents an overview of the relevant BSP literature. Section 3 provides the problem description, whereas Section 4 presents a mixed integer mathematical model. Section 5 discusses the problem’s complexity and the solution approach adopted. Section 6 presents a number of numerical experiments conducted to evaluate performance of the suggested methodology, whereas the last section provides conclusions and future research avenues.
2. Overview of the relevant literature
Berth allocation and scheduling received an increasing attention from the research community over the past two decades. For reviews of the general literature on marine container terminal operations, we refer to Steenken et al. (2004), Stahlbock and Voß (2008), whereas for review of the seaside operations, we refer to Bierwirth and Meisel (2010, 2015) and Carlo et al. (2015). The literature review presented herein focuses on the BSP papers, considering the water depth requirements for berthing of vessels and the channel depth variation. Overview of the collected studies is presented next.
Nishimura et al. (2001) presented a mathematical model for the BSP, aiming to minimize the total vessel service time. It was assumed that the draft of a vessel, assigned to a given berth, should not exceed summation of the water depth at that berth and the safety vertical distance. A genetic algorithm was developed to solve the problem. Numerical experiments were performed using the operational data from the Port of Kobe. It was found that the proposed methodology was able to improve efficiency of the port operations. Cheong and Tan (2008) studied a multi-objective BSP, aiming to minimize the total vessel service time and minimize the total delayed vessel departures. The mathematical formulation captured the safety vertical distance for berthing and the vessel draft. A multi-objective multi-colony ant algorithm was developed to solve the problem. Results indicated that the vessel order pheromone matrix and the earliest deadline first visibility heuristic were the most efficient for solving the BSP. Cheong et al. (2010) formulated a multi-objective BSP, taking into consideration the draft of vessels and the depth of each berth. The first objective aimed to minimize the makespan, whereas the second one minimized the total vessel waiting time. A multi-objective evolutionary algorithm was developed to solve the problem. Computational experiments were conducted using the data from the BSP literature. It was found that local search, solution decoding schemes and optimal berth insertion significantly affected performance of the developed algorithm.
Han et al. (2010) studied a simultaneous BSP and quay crane scheduling problem, considering uncertainty in vessel arrival and handling times and vessel draft restrictions during berthing. A genetic algorithm was developed to solve the problem. Numerical examples demonstrated that the proposed methodology could assist marine container terminal operations with design of robust berth schedules. Barros et al. (2011) developed a simulated annealing heuristic algorithm for the BSP in tidal bulk ports with stock level constraints. It was assumed that during low-depth tidal periods vessels were not able to navigate. Priority of service was given to vessels with the most critical mineral stock level. The objective minimized the total cost. Computational experiments were performed using the operational data, collected from Brazilian bulk ports and demonstrated efficiency of the suggested methodology. Guldogan et al. (2012) studied the BSP with stochastic arrival and handling times, considering water depth at each berth and vessel drafts. The objective aimed to minimize the total weighted vessel waiting time. Two heuristic algorithms were designed to solve the problem: genetic algorithm and bee colony algorithm. Numerical experiments demonstrated efficiency of both algorithms.
Xu et al. (2012) formulated a BSP, considering limitations in vessel to berth assignment by the water depth and tidal conditions. The study assumed the existence of two periods: low-water period and high-water period. The objective minimized the total vessel service time. A set of heuristic algorithms were proposed to solve the problem. Computational experiments indicated that benefits from the proposed methodology would be higher during the periods with a significant tidal effect. Elwany et al. (2013) proposed a simulated annealing heuristic for an integrated BSP and quay crane allocation problem. The objective aimed to minimize the total cost. The mathematical model considered the vessel draft as an additional spatial constraint in berth allocation. Numerical experiments indicated that the objective function values, provided by the developed solution algorithm, were close to the lower bound. Sheikholeslami et al. (2014) presented a mathematical formulation for the BSP at a marine container terminal with tidal constraints in the channel access. Vessels with deep drafts were not able to navigate during low-depth tidal periods. A genetic algorithm with a pattern search heuristic was developed to solve the problem.
Umang et al. (2013) proposed two exact methods and a heuristic algorithm for a hybrid BSP in bulk ports, considering the draft of vessels as an additional spatial constraint. The objective minimized the total vessel service time. Computational experiments demonstrated efficiency of the proposed methodology. Robenek et al. (2014) applied a branch-and-price algorithm to solve the integrated BSP and yard assignment problem in bulk ports. The mathematical model accounted for the depth of each berth and the draft of vessels. The objective aimed to minimize the total vessel service time. Numerical experiments indicated that the developed algorithm could solve instances with up to 40 vessels in a reasonable computational time.
Lalla-Ruiz et al. (2016) extended the mathematical model, proposed by Xu et al. (2012), and presented a discrete dynamic set-partitioning-based model for the BSP under time-dependent limitations, considering the water depth and tidal constraints. Unlike the model, developed by Xu et al. (2012), which could be applied for a two-period planning horizon (i.e. low tide period and high tide period), the proposed model accounted for a multi-period planning horizon. CPLEX was used to solve the problem. Numerical experiments demonstrated that the suggested model outperformed the model, formulated by Xu et al. (2012), in terms of both solution quality and computational time. A reasonable computational time was recorded even for large size problem instances. Qin et al. (2016) presented integer programming (IP) and constraint programming (CP) models for the BSP with a time-varying water depth at a tidal river port. The objective of the proposed mathematical model aimed to minimize the total weighted vessel service time. Both IP and CP models were solved using CPLEX. Computational experiments indicated that CP was found to be superior for the following cases:
the feasible domain was small;
the restriction on the objective toward decision variable was loose; and
size of the IP model was too large.
The literature review suggests that consideration of additional spatial constraints in berth scheduling receives an increasing attention from the community. However, the majority of studies focused on water depth requirements for berthing of vessels. Only a few papers modeled a variation in depth of the access channel. This study extends the BSP models that consider tidal effects (Barros et al., 2011; Xu et al., 2012; Sheikholeslami et al., 2014; Lalla-Ruiz et al., 2016; Qin et al., 2016) and presents a novel mathematical formulation for the BSP at multiple terminals with variation in depth of the access channel by time of day.
3. Problem description
In this paper, we consider a port, which has a set of marine container terminals. Note that all terminals at the port are operated by the same entity (e.g. port authority, private firm). Such port ownership model is used at some ports in Europe and Asia (e.g. Port of Piraeus – Greece, owned by the port authority, and terminals are operated by COSCO Pacific Limited; Port of Bandar Abbas – Iran, owned by the port authority, and terminals are operated by a private company). Each terminal of the port has a continuous berthing layout, and the number of vessels that can be served is limited by the total length of a given wharf. Furthermore, each marine container terminal has a different depth (constant along its wharf). In this paper, we also assume that:
vessel arrival and handling times are known with certainty;
there are no vessels at the berths in the beginning of the planning horizon; and
there are specific safety distances between vessels, served at the same terminal.
Similar to Imai et al. (2003) and Golias et al. (2009a), we assume that vessels belong to one of three preferential groups (low, medium, high) based on contractual agreements with the port operator. Each group is characterized by different penalties for delayed departures. Each vessel has a requested departure time, and the goal of the port operator is to schedule vessels at the available terminals so that the total weighted delayed departure time is minimized. The planning horizon is divided into time periods to account for variations in the access channel depth (i.e. each time period corresponds to a different channel depth). Next, we present a mixed integer mathematical formulation for a continuous BSP at multiple terminals with channel depth variations by time of day that will be referred to as CBSP.
4. Model formulation
This section of the paper presents a mixed integer formulation for the CBSP mathematical model. The mathematical formulation proposed herein extends the model developed by Kim and Moon (2003). Kim and Moon (2003) presented a continuous dynamic mathematical formulation for the BSP at a marine container terminal. The objective aimed to minimize the total vessel service cost, associated with deviation from the desired berthing position and delayed vessel departures. The problem was solved using the simulated annealing algorithm. However, the mathematical model, proposed by Kim and Moon (2003), can be applied only to a single marine container terminal with a continuous layout. Furthermore, it does not account for the water depth requirements along the terminal wharf and the channel depth variations by time of day. The latter important operational aspects are captured in the mathematical model formulated in this paper. Moreover, a heuristic algorithm, developed by Kim and Moon (2003), does not guarantee optimality of berth schedules, whereas this paper applies an exact optimization algorithm (CPLEX) to solve the proposed mathematical model within a reasonable computational time (details are discussed in Section 5 of the paper). Note that multiple terminals in this study were modeled by combining the available berthing space of each terminal into a single wharf (Figure 1).
The mathematical model can then be formulated as follows:
CBSP:
Subject to:
In CBSP, the objective function (1) minimizes the total weighted delayed vessel departures. Constraints sets (2) and (3) ensure that the depth of the access channel is adequate for a vessel to navigate (either enter or exit the port). Constraints sets (4) and (5) ensure that vessels cannot enter or depart more than once. Constraints sets (6) and (7) calculate the berthing and departure times of each vessel. Constraints set (8) ensures that each vessel is served at one terminal. Constraints sets (9) and (10) ensure that the full length of the vessel is accommodated at the assigned terminal. Constraints set (11) guarantees that the draft of each vessel is less than the depth of the wharf at the assigned terminal. Constraints set (12) estimates the departure time of vessels. Unlike many BSP formulations found in the literature, where the departure time of a vessel is a summation of its arrival, waiting, and handling times, in our model, vessels with deep drafts cannot depart immediately (after handling operations are completed), as they may have to wait for a sufficient depth of the access channel. Constraints sets (3), (5), (7) and (12) guarantee that the latter condition is met. Constraints set (13) ensures that a vessel cannot be berthed before its arrival. Constraints sets (14) through (16) ensure that there is no an overlap between vessels in the time-space dimension. Constraints sets (17) and (18) define the range of decision variables and parameters. The next section discusses complexity of the proposed mathematical formulation and the solution approach selected to solve the problem.
5. Problem’s complexity and solution approach
BSP can be reduced to the machine scheduling problem, which is known to be NP-hard (Pinedo, 2008; Bierwirth and Meisel, 2010, 2015; Dulebenets, 2015). Many of the BSP studies, conducted in the past, use either heuristic or metaheuristic algorithms to obtain good quality solutions within a reasonable computational time (Nishimura et al., 2001; Cheong and Tan, 2008; Hansen et al., 2008; Golias et al., 2009a, b; Cheong et al., 2010; Meisel and Bierwirth, 2009; Bierwirth and Meisel, 2010, 2015; Dulebenets, 2015). The mathematical model proposed in this paper (CBSP) introduces additional constraints sets to ensure that the depth of the access channel is sufficient for the vessels to either enter or exit the port. Additional constraints sets allow reducing feasible solution space of the problem. Preliminary computational experiments, conducted for large size problem instances, indicated that CBSP could be solved using CPLEX of general algebraic modeling system to the global optimality within acceptable computational time (details will be discussed in the numerical experiments section).
6. Numerical experiments
This section presents a number of numerical experiments that were conducted to evaluate efficiency of the developed mathematical model.
6.1 Input data
The input data for numerical experiments were generated using the operational data, obtained from the container terminals of the Port of Bandar Abbas (Iran), which is located on the Northern Coast of the Persian Gulf. The Port of Bandar Abbas is the largest and most important Iranian port with throughput of 2.45 million TEUs in 2015 (IHS, 2016). The port has two terminals with wharf lengths of 940 and 850 m and wharf depths of 12 and 16 m, respectively. The operational data were available for the time period between 2005 through 2012 for approximately 7,800 vessels, including the following information:
vessel name;
liner shipping company;
vessel length;
expected arrival;
anchorage time;
berthing time;
start and end time of handling operations; and
departure time.
Note that due to the access channel depth variations, the departure time provided does not always coincide with the finish time of a vessel service (i.e. a vessel may stay at the berth until the channel depth is sufficient to exit safely).
The data were also available for the vessel mooring location (terminal and location along the quay) and vessel load (TEUs handled). Channel depths by time of day were obtained for the same time period (2005 through 2012). A total of 27 problem instances were extracted from the available operational data set for numerical experiments in this study; 27 problem instances represent berth schedules of one week and were divided into three groups of low (L), medium (M) and high (H) demand. Table I presents the demand levels for each one of the 27 problem instances. For example, the first problem instance with low demand (denoted as L1) has 13 vessels requesting service with 26,351 TEUs to be (un)loaded (from all the vessels) and the vessel average interarrival time of 10.5 h. The medium and high demand cases for the first instance (denoted as M1 and H1, respectively) have 21 and 30 vessels requesting service, a demand of 47,607 and 46,950 TEUs, and the vessel average interarrival times of 7.25 and 5.5 h, respectively. The duration of a time period used for the numerical experiments was set equal to 15 min (i.e. a total of 672 time periods) to adequately capture both the access channel depth variations and vessel service times. Based on the available data, no significant channel depth variations were observed during shorter than 15-min time periods. However, setting a time period duration lower than 15 min would increase the total number of time periods required to model the same planning horizon, which in turn will increase the number of variables in the CBSP mathematical model and may negatively affect the computational time. For a discussion on the selection of time units/time periods in the discrete time representation scheduling and its effect on complexity and optimality gap of the solution, we refer to Saharidis et al. (2012).
6.2 Methodology evaluation
The first set of numerical experiments focused on the evaluation of the proposed berth scheduling policy based on a comparative analysis with the current operations at the Port of Bandar Abbas, where vessels are served based on a first come first served policy. All weights for the three customer groups were set equal to one, as the current operations at the port do not differentiate between vessels or liner shipping companies. Vessel schedules were obtained for all 27 problem instances by solving CBSP using CPLEX, and the average reduction in delayed departure times per vessel (i.e. the difference in delayed departures from the existing vessel schedules and CBSP vessel schedules) is presented in Figure 2. For example, for the first three problem instances (L1, M1, H1), the average reduction of delayed departures per vessel (as compared to the current berth scheduling policy) are equal to 4, 2 and 20 h, respectively. These results show that CBSP reduces the average delayed departures for all problem instances (low, medium and high demand) with the average reduction per vessel equal to 7, 9 and 11 h (for the low, medium and high demand cases, respectively). Furthermore, the computational time of the adopted solution approach (CPLEX) did not exceed 17 min even for large size problem instances, which can be considered as acceptable.
In addition, a regression analysis was performed to determine if there are any trends in reduction of the average vessel delayed departures from the proposed berth scheduling policy. The total volume (in TEUs) and vessel interarrival time (in hours) were selected to be predictors (i.e. independent variables), whereas the average reduction in delayed departures per vessel (in hours) was assigned as a response variable (i.e. dependent variable). Results from the conducted regression analysis are presented in Figure 3. We observe that the average reduction in delayed departures per vessel increases with the total volume and vessel arrival frequency (i.e. decreasing vessel interarrival time). The latter finding indicates that CBSP can significantly improve vessel scheduling and reduce delayed vessel departures especially during high demand periods. Relatively low coefficients of determination (R2) of the regression models can be explained by the following reasons:
The average reduction in delayed departures per vessel is not solely dependent either on the total volume or the vessel interarrival time (i.e. there are some other predictors that have to be considered in the regression models such as vessel size, storage yard utilization, average quay crane productivity, etc.).
The relationship between the response variable and predictors may be non-linear.
The future research may focus on development of a more accurate regression model that will precisely estimate the average reduction in delayed departures per vessel from using the CBSP mathematical model at the Port of Bandar Abbas.
6.3 Weight sensitivity analysis
The second set of numerical experiments aimed to evaluate the effect of introducing weights for each group of vessels on the objective function value and vessel scheduling. The complexity and accuracy of a weighted aggregate function depends on the proper selection of weights, used to depict the decision maker’s preferences. In practice, it can be very difficult to accurately select these weights, even for someone familiar with the problem domain (Coello Coello, 2000). In the problem studied herein, using individual weights for each vessel would result in a vessel schedule highly sensitive to the weight selection. Furthermore, the latter would require a significant effort by the port operator to identify the weight values that would result in a berth schedule that meets specific objectives. To address this issue and reduce the search space, we assume that each vessel belongs to one of the three preferential groups with high, medium and low service priority, respectively. This assumption is in line with terminal operator practices at terminals (mainly multi-user terminals) with medium to high demand, where vessel scheduling is based on customer differentiation and contractual agreements (Golias et al., 2009a).
Vessels were randomly (not based on their length or volume) assigned to one of the three groups for each one of the 27 problem instances. Then, weight combinations were generated to represent the full feasible space of the decision maker’s weight selection (i.e. weight of the high priority group of vessels should be greater than the weight of medium priority group of vessels, and weight of the medium priority group of vessels should be greater than the weight of the low priority group of vessels). A total of four sets of weights were developed and are shown in Table II. With these sets of weights berth schedules were obtained using CBSP (solved with CPLEX), and results of the total delayed departures for each vessel group are shown in Table II. Table II also includes (for comparison purposes) the total delay breakdown by vessel group for the case, when all weights are equal to one.
Adopting a customer differentiation approach (i.e. using weights in the objective function to differentiate between vessel groups) provides significant differences in the solution space and objective function values of the different priority groups mainly for medium-/high-demand instances. Low-demand instances do not show a substantial variation in response to different weight selections. These results should be expected as customer/price differentiation policies should provide different results when demand to capacity ratios increase. Note that the proposed formulation can be solved efficiently within a relatively small computation time (less than 17 min), so the port operator will be able to easily produce the berth schedules for all the five sets of weights and select the one that best satisfies contractual agreements (usually based on departure time and handling rates).
6.4 Access channel depth sensitivity analysis
The third set of numerical experiments evaluated the effect of increasing the access channel depth (i.e. dredging) on the vessel delayed departures. The current depth of the access channel at the Port of Bandar Abbas is 11.5 m. The sensitivity analysis was performed by solving the CBSP mathematical model for each one of the 27 problem instances by increasing the depth of access channel from 11.5 to 13.5 m with an increment of 0.5 m. Variations in the access channel depth by time of day due to tidal effect were assumed not to be affected with dredging (i.e. additional dredging did not influence variations in depth of the access channel). All weights for the three customer groups were set equal to one. The average reduction in delayed departures per vessel due to dredging is presented in Table III. For example, changing the access channel depth from 11.5 to 12.0 m for instance L1 will result in the average reduction of delayed departures per vessel by 8 h. We observe that the average delayed departures per vessel were reduced by 58.9, 83.1 and 110.3 h per meter of dredging for instances with low, medium and high demand, respectively. Hence, dredging can be an efficient alternative in reduction of vessel delayed departures at ports with a shallow access channel and significant tidal effect, especially during high demand periods. Furthermore, the proposed mathematical model may serve as an effective planning tool for marine container terminal operators and assist with assessing the effect of dredging on service of vessels.
7. Conclusions and future research
This paper proposed a novel mathematical model for the BSP at multiple marine container terminals of the same port, considering the depth variation of the access channel. The berth scheduling policy was formulated as a mixed integer mathematical program. Vessels were categorized into three preferential groups to account for various contractual agreements between liner shipping companies and the port operator. The objective function aimed to minimize the total weighted vessel delayed departures. Three sets of numerical experiments were performed to evaluate the efficiency of the proposed berth scheduling policy (by comparing to the existing berthing policy used at the Port of Bandar Abbas in Iran), assess the effect of introducing vessel weights and evaluate how dredging may affect marine container terminal operations. Results from numerical experiments indicate that both tidal effects and vessel priorities may cause significant changes in berth schedules, especially under medium/high demand. Furthermore, in case of a shallow access channel and/or significant tidal effect, the port operator may consider dredging of the access channel to allow vessels better navigation and reduce delayed vessel departures. The future research may focus on the following:
introduce a variable arrival time component to the existing mathematical formulation and reduce vessel waiting and handling times;
use a multi-objective formulation to account for different customer/price differentiation policies;
extend the proposed model formulation to capture vessel handling and arrival time uncertainty; and
consider additional dredging costs in the objective function.
Figures
Numerical data
| Problem instance | Low (L), Medium (M), High (H) demand | ||
|---|---|---|---|
| No. of vessels | Demand (TEUs) | Vessel average interarrival time (hrs) | |
| L1, M1, H1 | (13, 21, 30) | (26,351, 47,607, 46,950) | (10.5, 7.25, 5.5) |
| L2, M2, H2 | (14, 23, 30) | (42,182, 54,395, 53,250) | (12.5, 7.5, 5.3) |
| L3, M3, H3 | (15, 23, 31) | (37,875, 58,903, 42,873) | (12.75, 7.25, 5.3) |
| L4, M4, H4 | (16, 24, 31) | (35,536, 37,320, 79,329) | (8.75, 6, 4.8) |
| L5, M5, H5 | (17, 27, 33) | (37,587, 46,953, 53,790) | (7, 5.25, 5.3) |
| L6, M6, H6 | (18, 27, 35) | (47,502, 62,424, 61,705) | (8, 7.25, 5) |
| L7, M7, H7 | (18, 28, 35) | (56,682, 39,732, 52,115) | (9.5, 5.5, 5.3) |
| L8, M8, H8 | (19, 28, 36) | (39,349, 44,632, 55,980) | (9.25, 5.75, 4.5) |
| L9, M9, H9 | (20, 29, 39) | (37,200, 54,839, 52,806) | (6.25, 5.5, 4.5) |
Vessel group delay (hours) by weight combination
| Weight combination | Group | All | Group | All | Group | All | ||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 1 | 2 | 3 | 1 | 2 | 3 | ||||
| (w1, w2, w3) | Instance L1 | Instance M1 | Instance H1 | |||||||||
| (0.1, 0.2, 0.7) | 12 | 79 | 38 | 129 | 96 | 15 | 83 | 194 | 35 | 435 | 118 | 588 |
| (0.1, 0.3, 0.6) | 12 | 79 | 38 | 129 | 96 | 15 | 83 | 194 | 42 | 325 | 154 | 521 |
| (0.1, 0.4, 0.5) | 12 | 79 | 38 | 129 | 96 | 15 | 83 | 194 | 28 | 242 | 219 | 489 |
| (0.2, 0.3, 0.5) | 12 | 79 | 38 | 129 | 96 | 15 | 83 | 194 | 28 | 185 | 229 | 442 |
| (1.0, 1.0, 1.0) | 12 | 79 | 38 | 129 | 96 | 15 | 83 | 194 | 35 | 233 | 217 | 485 |
| (w1, w2, w3) | Instance L2 | Instance M2 | Instance H2 | |||||||||
| (0.1, 0.2, 0.7) | 9 | 31 | 64 | 104 | 28 | 201 | 70 | 299 | 97 | 182 | 117 | 396 |
| (0.1, 0.3, 0.6) | 9 | 31 | 64 | 104 | 28 | 201 | 70 | 299 | 97 | 127 | 138 | 362 |
| (0.1, 0.4, 0.5) | 9 | 31 | 64 | 104 | 28 | 106 | 118 | 252 | 97 | 127 | 138 | 362 |
| (0.2, 0.3, 0.5) | 9 | 31 | 64 | 104 | 28 | 106 | 118 | 252 | 63 | 148 | 138 | 349 |
| (1.0, 1.0, 1.0) | 9 | 31 | 64 | 104 | 28 | 106 | 118 | 252 | 63 | 124 | 159 | 346 |
| (w1, w2, w3) | Instance L3 | Instance M3 | Instance H3 | |||||||||
| (0.1, 0.2, 0.7) | 27 | 140 | 44 | 211 | 35 | 198 | 115 | 348 | 165 | 131 | 42 | 338 |
| (0.1, 0.3, 0.6) | 27 | 116 | 49 | 192 | 35 | 126 | 147 | 308 | 116 | 137 | 110 | 363 |
| (0.1, 0.4, 0.5) | 27 | 105 | 68 | 201 | 35 | 57 | 187 | 279 | 116 | 74 | 151 | 341 |
| (0.2, 0.3, 0.5) | 27 | 116 | 49 | 192 | 35 | 57 | 187 | 279 | 92 | 117 | 129 | 338 |
| (1.0, 1.0, 1.0) | 39 | 50 | 47 | 136 | 35 | 57 | 187 | 279 | 92 | 43 | 186 | 321 |
| (w1, w2, w3) | Instance L4 | Instance M4 | Instance H4 | |||||||||
| (0.1, 0.2, 0.7) | 83 | 11 | 28 | 121 | 43 | 52 | 30 | 124 | 130 | 399 | 308 | 837 |
| (0.1, 0.3, 0.6) | 83 | 11 | 28 | 121 | 73 | 52 | 27 | 151 | 115 | 197 | 373 | 685 |
| (0.1, 0.4, 0.5) | 83 | 11 | 28 | 121 | 68 | 52 | 30 | 149 | 105 | 188 | 396 | 689 |
| (0.2, 0.3, 0.5) | 83 | 11 | 28 | 121 | 43 | 52 | 30 | 124 | 48 | 222 | 409 | 679 |
| (1.0, 1.0, 1.0) | 83 | 11 | 28 | 121 | 43 | 52 | 30 | 124 | 31 | 81 | 526 | 638 |
| (w1, w2, w3) | Instance L5 | Instance M5 | Instance H5 | |||||||||
| (0.1, 0.2, 0.7) | 21 | 154 | 39 | 215 | 30 | 80 | 71 | 182 | 146 | 86 | 73 | 304 |
| (0.1, 0.3, 0.6) | 19 | 56 | 73 | 148 | 30 | 80 | 71 | 182 | 153 | 68 | 73 | 295 |
| (0.1, 0.4, 0.5) | 23 | 56 | 73 | 152 | 30 | 80 | 71 | 182 | 153 | 67 | 73 | 293 |
| (0.2, 0.3, 0.5) | 19 | 56 | 73 | 148 | 30 | 80 | 71 | 182 | 106 | 91 | 73 | 269 |
| (1.0, 1.0, 1.0) | 19 | 56 | 73 | 148 | 41 | 31 | 92 | 165 | 106 | 114 | 37 | 257 |
| (w1, w2, w3) | Instance L6 | Instance M6 | Instance H6 | |||||||||
| (0.1, 0.2, 0.7) | 22 | 300 | 160 | 481 | 40 | 62 | 143 | 246 | 35 | 356 | 155 | 546 |
| (0.1, 0.3, 0.6) | 22 | 11 | 258 | 291 | 40 | 63 | 144 | 247 | 35 | 166 | 220 | 421 |
| (0.1, 0.4, 0.5) | 22 | 11 | 258 | 291 | 40 | 62 | 143 | 245 | 35 | 143 | 251 | 429 |
| (0.2, 0.3, 0.5) | 22 | 11 | 258 | 291 | 40 | 62 | 157 | 260 | 26 | 161 | 220 | 407 |
| (1.0, 1.0, 1.0) | 22 | 11 | 258 | 291 | 40 | 62 | 159 | 262 | 26 | 65 | 326 | 417 |
| (w1, w2, w3) | Instance L7 | Instance M7 | Instance H7 | |||||||||
| (0.1, 0.2, 0.7) | 10 | 252 | 230 | 491 | 30 | 40 | 93 | 163 | 73 | 67 | 66 | 207 |
| (0.1, 0.3, 0.6) | 10 | 136 | 278 | 423 | 43 | 28 | 94 | 164 | 97 | 57 | 66 | 221 |
| (0.1, 0.4, 0.5) | 10 | 65 | 313 | 388 | 43 | 28 | 91 | 162 | 97 | 36 | 79 | 212 |
| (0.2, 0.3, 0.5) | 10 | 65 | 313 | 388 | 30 | 28 | 93 | 151 | 43 | 37 | 90 | 171 |
| (1.0, 1.0, 1.0) | 10 | 77 | 327 | 414 | 30 | 28 | 93 | 151 | 43 | 37 | 91 | 171 |
| (w1, w2, w3) | Instance L8 | Instance M8 | Instance H8 | |||||||||
| (0.1, 0.2, 0.7) | 25 | 76 | 11 | 112 | 32 | 186 | 20 | 237 | 40 | 349 | 164 | 553 |
| (0.1, 0.3, 0.6) | 25 | 76 | 11 | 112 | 32 | 176 | 24 | 232 | 68 | 201 | 206 | 475 |
| (0.1, 0.4, 0.5) | 25 | 76 | 11 | 112 | 32 | 109 | 72 | 213 | 46 | 164 | 230 | 439 |
| (0.2, 0.3, 0.5) | 25 | 76 | 11 | 112 | 32 | 176 | 24 | 232 | 56 | 201 | 206 | 462 |
| (1.0, 1.0, 1.0) | 25 | 76 | 11 | 112 | 32 | 109 | 72 | 213 | 40 | 121 | 272 | 433 |
| (w1, w2, w3) | Instance L9 | Instance M9 | Instance H9 | |||||||||
| (0.1, 0.2, 0.7) | 44 | 13 | 50 | 108 | 31 | 54 | 108 | 193 | 47 | 303 | 182 | 532 |
| (0.1, 0.3, 0.6) | 44 | 13 | 50 | 108 | 32 | 35 | 111 | 177 | 74 | 227 | 236 | 537 |
| (0.1, 0.4, 0.5) | 44 | 13 | 50 | 108 | 31 | 35 | 108 | 174 | 52 | 183 | 259 | 494 |
| (0.2, 0.3, 0.5) | 44 | 13 | 50 | 108 | 31 | 49 | 108 | 188 | 64 | 225 | 233 | 522 |
| (1.0, 1.0, 1.0) | 44 | 13 | 50 | 108 | 40 | 35 | 108 | 183 | 47 | 140 | 307 | 494 |
Average reduction of delayed departures per vessel from dredging
| Instance | Change in the access channel depth (m-m) | Average reduction in delay per vessel (hrs/m) | |||
|---|---|---|---|---|---|
| 11.5-12.0 | 11.5-12.5 | 11.5-13.0 | 11.5-13.5 | ||
| L1 | 8 | 32 | 49 | 66 | 28.4 |
| L2 | 31 | 44 | 57 | 57 | 43.1 |
| L3 | 43 | 76 | 78 | 82 | 63.8 |
| L4 | 38 | 44 | 50 | 55 | 45.2 |
| L5 | 60 | 86 | 91 | 95 | 78.5 |
| L6 | 63 | 110 | 118 | 128 | 94.7 |
| L7 | 67 | 100 | 120 | 152 | 97.5 |
| L8 | 30 | 44 | 55 | 59 | 42.5 |
| L9 | 24 | 40 | 48 | 52 | 36.5 |
| Average overall – low demand | 58.9 | ||||
| M1 | 45 | 53 | 54 | 57 | 51.9 |
| M2 | 93 | 102 | 102 | 102 | 101.8 |
| M3 | 98 | 137 | 141 | 146 | 125.0 |
| M4 | 66 | 82 | 90 | 90 | 79.8 |
| M5 | 28 | 37 | 92 | 96 | 50.6 |
| M6 | 70 | 93 | 104 | 121 | 90.7 |
| M7 | 53 | 73 | 90 | 129 | 75.9 |
| M8 | 47 | 104 | 115 | 170 | 89.9 |
| M9 | 65 | 80 | 101 | 103 | 82.2 |
| Average overall – medium demand | 83.1 | ||||
| H1 | 93 | 148 | 189 | 217 | 142.1 |
| H2 | 46 | 65 | 98 | 111 | 69.5 |
| H3 | 95 | 143 | 160 | 178 | 132.2 |
| H4 | 49 | 68 | 103 | 117 | 73.3 |
| H5 | 96 | 155 | 161 | 168 | 134.6 |
| H6 | 114 | 148 | 176 | 187 | 146.7 |
| H7 | 36 | 65 | 88 | 97 | 61.0 |
| H8 | 86 | 133 | 191 | 204 | 133.6 |
| H9 | 78 | 98 | 124 | 124 | 99.7 |
| Average overall – high demand | 110.3 | ||||
References
Barros, V.H., Costa, T.S., Oliveira, A. and Lorena, L.A. (2011), “Model and heuristic for berth allocation in tidal bulk ports with stock level constraints”, Computers & Industrial Engineering, Vol. 60 No. 4, pp. 606-613.
Bierwirth, C. and Meisel, F. (2010), “A survey of berth allocation and quay crane scheduling problems in container terminals”, European Journal of Operational Research, Vol. 202 No. 3, pp. 615-627.
Bierwirth, C. and Meisel, F. (2015), “A follow-up survey of berth allocation and quay crane scheduling problems in container terminals”, European Journal of Operational Research, Vol. 244 No. 3, pp. 675-689.
Carlo, H.J., Vis, I.F. and Roodbergen, K.J. (2015), “Seaside operations in container terminals: literature overview, trends, and research directions”, Flexible Services and Manufacturing Journal, Vol. 27 Nos 2/3, pp. 224-262.
Cheong, C.Y. and Tan, K.C. (2008), “A multi-objective multi-colony ant algorithm for solving the berth allocation problem”, Studies in Computational Intelligence, Vol. 116, pp. 333-350.
Cheong, C.Y., Tan, K.C., Liu, D.K. and Lin, C.J. (2010), “Multi-objective and prioritized berth allocation in container ports”, Annals of Operations Research, Vol. 180 No. 1, pp. 63-103.
Coello, C.A.C. (2000), “Treating constraints as objectives for single-objective evolutionary optimization”, Engineering Optimization, Vol. 32 No. 3, pp. 275-308.
Du, Y., Chen, Q., Quan, X., Long, L. and Fung, R.Y. (2011), “Berth allocation considering fuel consumption and vessel emissions”, Transportation Research Part E, Vol. 47 No. 6, pp. 1021-1037.
Dulebenets, M.A. (2015), “Models and solution algorithms for improving operations in marine transportation”, Dissertation, The University of Memphis.
Elwany, M.H., Ali, I. and Abouelseoud, Y. (2013), “A heuristics-based solution to the continuous berth allocation and crane assignment problem”, Alexandria Engineering Journal, Vol. 52 No. 4, pp. 671-677.
Golias, M.M., Boilé, M. and Theofanis, S. (2009a), “Berth scheduling by customer service differentiation: a multi-objective approach”, Transportation Research Part E, Vol. 45 No. 6, pp. 878-889.
Golias, M.M., Saharidis, G.K., Boile, M., Theofanis, S. and Ierapetritou, M.G. (2009b), “The berth allocation problem: optimizing vessel arrival time”, Maritime Economics & Logistics, Vol. 11 No. 4, pp. 358-377.
Guan, Y. and Cheung, R.K. (2004), “The berth allocation problem: models and solution methods”, OR Spectrum, Vol. 26 No. 1, pp. 75-92.
Guldogan, E., Bulut, O. and Tasgetiren, M.F. (2012), A Dynamic Berth Allocation Problem With Priority Considerations Under Stochastic Nature, Springer-Verlag Berlin, Heidelberg, pp. 74-82.
Han, X., Lu, Z. and Xi, L. (2010), “A proactive approach for simultaneous berth and quay crane scheduling problem with stochastic arrival and handling time”, European Journal of Operational Research, Vol. 207 No. 3, pp. 1327-1340.
Hansen, P., Oğuz, C. and Mladenović, N. (2008), “Variable neighborhood search for minimum cost berth allocation”, European Journal of Operational Research, Vol. 191 No. 3, pp. 636-649.
IHS (2016), “Iran container growth prospects seen”, available at: http://fairplay.ihs.com/commerce/article/ 4255931/iran-container-growth-prospects-seen (accessed 10 April 2016).
Imai, A., Nishimura, E. and Papadimitriou, S. (2001), “The dynamic berth allocation problem for a container port”, Transportation Research Part B, Vol. 35 No. 4, pp. 401-417.
Imai, A., Nishimura, E. and Papadimitriou, S. (2003), “Berth allocation with service priority”, Transportation Research Part B, Vol. 37 No. 5, pp. 437-457.
Imai, A., Sun, X., Nishimura, E. and Papadimitriou, S. (2005), “Berth allocation in a container port: using a continuous location space approach”, Transportation Research Part B, Vol. 39 No. 3, pp. 199-221.
Imai, A., Zhang, J.T., Nishimura, E. and Papadimitriou, S. (2007), “The berth allocation problem with service time and delay time objectives”, Maritime Economics & Logistics, Vol. 9 No. 4, pp. 269-290.
Kim, K.H. and Moon, K.C. (2003), “Berth scheduling by simulated annealing”, Transportation Research Part B, Vol. 37 No. 6, pp. 541-560.
Lalla-Ruiz, E., Expósito-Izquierdo, C., Melián-Batista, B. and Moreno-Vega, J.M. (2016), “A set-partitioning-based model for the berth allocation problem under time-dependent limitations”, European Journal of Operational Research, Vol. 250 No. 3, pp. 1001-1012.
Meisel, F. and Bierwirth, C. (2009), “Heuristics for the integration of crane productivity in the berth allocation problem”, Transportation Research Part E, Vol. 45 No. 1, pp. 196-209.
Monaco, M.F. and Sammarra, M. (2007), “The berth allocation problem: a strong formulation solved by a Lagrangean approach”, Transportation Science, Vol. 41 No. 2, pp. 265-280.
Moorthy, R. and Teo, C.P. (2006), “Berth management in container terminal: the template design problem”, OR Spectrum, Vol. 28 No. 4, pp. 495-518.
Nishimura, E., Imai, A. and Papadimitriou, S. (2001), “Berth allocation planning. Berth allocation planning in the public berth system by genetic algorithms”, European Journal of Operational Research, Vol. 131 No. 2, pp. 282-292.
Park, Y.M. and Kim, K.H. (2003), “A scheduling method for berth and quay cranes”, OR Spectrum, Vol. 25 No. 1, pp. 1-23.
Pinedo, M. (2008), Scheduling: Theory, Algorithms, and Systems, Springer Science + Business Media, LLC.
Qin, T., Du, Y. and Sha, M. (2016), “Evaluating the solution performance of IP and CP for berth allocation with time-varying water depth”, Transportation Research Part E: Logistics and Transportation Review, Vol. 87, pp. 167-185.
Robenek, T., Umang, N., Bierlaire, M. and Ropke, S. (2014), “A branch-and-price algorithm to solve the integrated berth allocation and yard assignment problem in bulk ports”, European Journal of Operational Research, Vol. 235 No. 2, pp. 399-411.
Saharidis, G., Golias, M.M. and Zhang, T. (2012), “Discrete time formulation for the assignment problem applied in cross docking facilities”, Proceedings of the Transportation Research Board 91st Annual Meeting, Washington, DC.
Sheikholeslami, A., Ilati, G. and Kobari, M. (2014), “The continuous dynamic berth allocation problem at a marine container terminal with tidal constraints in the access channel”, International Journal of Civil Engineering, Vol. 12 No. 3, pp. 344-353.
Stahlbock, R. and Voß, S. (2008), “Operations research at container terminals: a literature update”, OR Spectrum, Vol. 30 No. 1, pp. 1-52.
Steenken, D., Voß, S. and Stahlbock, R. (2004), “Container terminal operation and operations research-a classification and literature review”, OR Spectrum, Vol. 26 No. 1, pp. 3-49.
Umang, N., Bierlaire, M., Vacca, I. (2013), “Exact and heuristic methods to solve the berth allocation problem in bulk ports”, Transportation Research Part E, Vol. 54, pp. 14-31.
UNCTAD (2015), “Review of maritime transport 2015”, United Nations Conference on Trade and Development, New York, NY, Geneva.
Xu, D., Li, C.L. and Leung, J.Y. (2012), “Berth allocation with time-dependent physical limitations on vessels”, European Journal of Operational Research, Vol. 216 No. 1, pp. 47-56.