Continuous Berth Scheduling in Port Terminals

Continuous Berth Scheduling in Port Terminals

T. Ismail(1)*

(1) Basic & Applied Sciences Department, Faculty of Engineering & Technology,

Arab Academy for Science, Technology & Maritime Transport.

M. Elbeheiry (2), A. Elkharbotly (4), N. Afia (5)

(2),(4),(5) Design and Production Engineering Department, Faculty of Engineering,

Ain Shams University.

K. Abdalla (3),

(3) Supply Chain Management Department, College of International Transport and Logistics,

Arab Academy for Science, Technology & Maritime Transport.

Abstract – In this paper, a model was developed for scheduling vessels in port terminal with continuous berth. The model aims to determine optimal berthing times and positions for incoming vessels according to their scheduled arrival and promised departure times. The developed model was formulated for different objectives. The model was examined on a number of problems to check the feasibility of the obtained solutions. Then, the model was used to study port performance under different conditions and objectives. The problem under consideration was proved to be NP-hard; thus, solving large sized problems using this model will be time consumable.

Keywords: Berth scheduling; Continuous berth; Berth allocation

1- INTRODUCTION:

Due to the growth on global trade during the last couple of decades, ports have played an important role in the exchange of goods between continents. And due to the competition between port terminals, decision makers tend to minimize ports operating costs together with increasing productivity through efficient scheduling for ports operations. Effective scheduling for port operations leads to improved utilization of resources and minimizing penalties resulting from violating planned departures for incoming vessels and other sort of penalties. Container terminal operations can be classified into seaside operations and landside operations. Each group of operations relies on several resources which represent a capital cost and operating cost. Seaside operations include decisions concerning service priorities, berthing sequence and berthing positions along the quay. Since the cost of construction of the berthing quay is so large and may be constrained by several technological and spatial conditions, the available quay length at any port is a scarce resource that should be optimally utilized. Thus, effective scheduling for incoming vessels strongly affects the time vessels have to wait before being assigned to a berth resulting in penalties in case of violating promised departure times, also handling times will be affected by the distance between the berthing position of the ship and the location of the container storage yard. Berth allocation problem (BAP) has attracted the attention of research during the past starting from the past decade due to above

stated motives. BAP have been classified according to different schemes. BAP have classified into Static (SBAP) and Dynamic (DBAP) depending on the arrival times of the incoming vessels. For SBAP, all incoming vessels are assumed to be ready to be served at the beginning of the planning horizon. While for DBAP, the vessels are assumed to arrive during the planning horizon with known arrival times. Also, BAP are classified according the quay design into discrete berth allocation problem (DBAP), continuous berth allocation problem (CBAP) and hybrid berth allocation problems (HBAP). DABP considers the case where the quay is divided into a number of berthing locations; either of different or equal lengths; where each location can host one vessel at a time. (CBAP) deals with the case where the quay is a continuous length where vessels can berth at any position. Hybrid Berth allocation problem (HBAP) is a combination of the two types where several quays are available each can host one or more vessels according to the lengths of the berthed vessels compared to the overall quay length.

BAP was proved by several researchers to be NP-hard in a very strong sense, however; researchers have developed mathematical models and used several meta-heuristic techniques to solve BAP with reasonable computational efforts.

Imai et al. [1] proposed a heuristic procedure based on the Lagrangian relaxation for discrete berth assignment problem with ready known vessels arrival times. Their algorithm was found to be adaptable for the practical size of the problems. Imai et al. [2] developed a genetic algorithm based heuristic to schedule vessels in a discrete berth system with service priorities with the objective of minimizing the total service time where vessel handling times depend on the assigned berth. The problem was proved to be a non-linear NP Hard problem needing large computational effort although the sub-gradient method was adaptable to this problem. Imai et al. introduced a heuristic algorithm by extending the existing discrete quay location algorithms ignoring berth boundaries and ships committed departure time violations. A solution is obtained in two stages, in the first stage the algorithm of identifies a

solution given the number of berths, and in the second stage the other procedure relocates the ships that may overlap or be located sparsely in a scheduling space. Golias et al. [3] proposed an optimization model for discrete berth space and uncertain vessel arrivals and handling times. The objectives of the proposed model are: minimize the average service time, and the range of the total service time (measured by the difference between the worst and best performances of a given schedule) to evaluate the robustness of the obtained schedule.

Hansen et al. [4] proposed Variable Neighbourhood Search (VNS) heuristic for discrete berth allocation problem. The proposed VNS takes into account ship-dependent earliness premiums and lateness penalties; as a result, handling costs were not assumed to be proportional to handling times. Also, a local search routine (memtic algorithm) was added to a previously developed genetic algorithm for the addressed berth allocation problem considering service priorities in order to compare results of different meta- heuristics. The authors proved that for dynamic berth allocation instances VNS nearly always reaches this optimum defeating other heuristics.

Imai et al. [5] developed a model to minimize the total service time of ships in the port without considering any service priority. As he quoted that (Lai & Shih 1992) considered the berth allocation problem by proposing a FCFS heuristic. However, (Imai et al. 1997) showed that for high port throughput FCFS rules should not be considered. Thus, they proposed a heuristic algorithm to maximize the port throughput while minimizing ships dissatisfaction. Legato & Mazza [6]developed a closed queuing network simulation model for berthing decisions at a container terminal. The model considered two classes of vessels (primary and secondary vessels), where primary vessel has reserved slot in the primary area as close as possible to the storage yard area for the inbound and outbound containers for such vessel. While for secondary vessels, they could be assigned to slots in the primary area

according to the availability- or in the secondary area according to FIFO rule.

Moreno-Vega et al. [7] developed a biased random key genetic algorithm to assign quay crane profiles to incoming vessels in a discrete berth system, the objective of the developed model is to maximize the sum of the values of the chosen quay crane profiles assigned to all the ships and to minimize the yard housekeeping costs resulting from the transportation of transsipment containers within the port terminal. Zhi-Hua Hu developed a rolling-horizon heuristic algorithm for berth allocation problem targeting the maximization of periodic balancing utilization of cranes within a work shift through a mathematical model which minimize the total number of idle QC hours within all work shifts.

Chung-Cheng Lu et al. [8] developed a berth flow network model for Dynamic flexible berth allocation problem. The model aimed to minimizing the total waiting time and penalties for being unable to serve some vessels during a

short planning horizon (24 hours). A maximum waiting time is set for each vessel to prevent long waiting times and a FCFS rule was used for vessels of similar types and could be violated with penalties in other cases.

From the above literature, it is obvious that the CBAP and HBAP gained less attention by the researchers due to the complexity of the problem.

The rest of the paper is organized as follows: section three will include the mathematical formulation for the continuous berth allocation problem, section four will present the computational results obtained as well as a study for port performance for different problem objectives, and section five will include the conclusion and future work.

2- MATHEMATICAL FORMULATION

The problem under study considers a number of vessels with known arrival times and workloads. The required berthing length for each vessel is described in terms of number of sections where the section represents a certain length in meters which is constant for the entire problem but may differ from one problem to the other. The quay length is continuous and its length is described in terms of number of sections.

Nomenclature:

V : Total number of vessels to be served. P : Number of berth sections.

T : Planning horizon.

Ai : Estimated arrival time for vessel i, where i=1V.

li : Required berthing length for vessel i in terms of number of berth sections, where i=1V

Wi : Workload of vessel i, where i=1V.

startv,t : Binary decision variable representing the service start time t for vessel v.

startv,t = 1 if vessel v will start to be served at time t

= 0 otherwise

sv,t : Binary decision variable representing whether vessel v is being served during time period t or not.

serv,t = 1 if vessel v is being served during time period t

= 0 otherwise

v,p : Binary decision variable representing the position p at which vessel v will start berthing.

v,p = 1 if vessel v will start berthing at berth section p

= 0 otherwise

,1

=2

, , 1 &

1

(5)

bv,p : Binary decision variable indicating whether vessel v will be occupying position p during

0 ,

,+1

+1

+ ,

, 1

(6)

being served.

=1 =1

1 & ( )

1 1

bv,p = 1 if vessel v will be occupying position p

, = 1 (7)

=1

= 0 otherwise

Decision Variables

, , 1 &

1

, , 1 &

(8)

The model aims to determine vessels service start time and berthing positions for all incoming vessels. Thus, the model decision variables are starti,t , i,p for all vessels i{V}.

Objective Function

The developed model can be solved for different problem objectives. The below formulated objective functions

,1

=2

1 (9)

, ,

(10)

1 & 2 ( 1)

include solving the model for either minimum total vessel

1 ,1 + , =1 , +

waiting time represented by the time elapsed between vessel arrival and service start time, or minimum mean

1 ,

1

1

=1

(11)

flow time or minimum make span. Equation (1) shows the objective function for minimizing total vessels waiting time, where it represents the difference between vessels start time and the vessel arrival times. Equation (2) shows the objective function for minimizing the mean flow time, where it represents the difference between vessels departure time and vessels arrival times. Equation (3) shows the objective function for minimizing total make span,

( , ) (1)

=1 =1

1 & 1 ( 1)

Constraint#1 guarantees that no berthing conflict occurs as it never allows two vessels to be served at the same time while occupying the same berthing positions. Constraint#2 guarantees that the vessel will not be served before its determined arrival time. Constraints 3&4 guarantees that for every vessel there is a single service start time and a single berthing position. Constraints 5-8 guarantees that the vessels will occupy successive sections equal to the required berthing length starting from the assigned berthing section . Constraints 9-11 guarantees continuous serving for the vessel for number of hours equal to the vessel

( , + , )

(2)

workload.

=1

/

=1

( , + , 1) (3)

1. RESULTS AND DISCUSSION

   =1

   Constraints

   =1

   The objective of this research is to study port performance at different objectives and to compare different performance measures for every problem objectives in

   , + , + , + , 3

   1 & 1 & ,

   1

   (1)

   order to be able to evaluate the most appropriate objective for berth allocation problems. The developed mathematical model was applied to a number of problems of different configurations representing different vessel sizes, workloads, and arrival times. The feasibility of the obtained

   , 1 (2)

   =1

   , = 1 1 (3)

   =1

   solutions was checked for the examined problems to investigate the validity of the developed model.

   , = 1 1

   =1

   (4)

   Exact LP Model

   Problem size CPU

   Different performance measures are studied in order to investigate the relation and their effect on each other. Then,

   (# of vessels)

   Best

   Best

   	bound	solution
   6	10000	10000	0.00%	>100k
   6	21000	21000	0.00%	>100k
   6	42000	42000	0.00%	>200k
   6	86000	86000	0.00%	>100k
   8	1000	1000	0.00%	14400
   8	33000	30000	10.00%	>150k

   	bound	solution
   6	10000	10000	0.00%	>100k
   6	21000	21000	0.00%	>100k
   6	42000	42000	0.00%	>200k
   6	86000	86000	0.00%	>100k
   8	1000	1000	0.00%	14400
   8	33000	30000	10.00%	>150k

   gap

   time

   (sec)

   the factors affecting different performance measures are studied to evaluate the significance of each factor in port productivity and service levels as perceived by served shipping lines.

   A berth allocation problem has been solved to obtain optimal berth assignment with different objectives where the different performance measures were evaluated for each obtained solution. The results showed that solving the berth allocation problem for minimum mean flow time or minimum total vessels waiting time are obtained through the same vessel-berth assignment schedule. Also, minimum make span is obtained with the same schedule which maximizes the berth utilization. Figures 1&2 show the vessel-berth assignment for minimum mean flow time at figure 1 and minimum make span at figure 1. Throughout this section; two definitions for berth utilization will be used, the first is the nominal berth utilization which concerns with the utilization of the berth modules during the entire make span for a given number of vessels. The second definition is the effective berth utilization which concerns with the utilization of berth modules during the active part of the cycle represented by the time before berthing the last vessel. From the previous definitions, it

   can be concluded that both utilization measures are affected by the vessels berthing schedule. As shown in the figures, the nominal utilization of the berth will be 69.3 % for figure 1 while it increases to 79.4 % for figure 2 since the make span decreases. Considering the effective berth utilization, it is obvious from the two figures that unutilized portions of the berth during the active part of the cycle in figure 1 are much greater than that in figure 2.

   Figure 1: Berthing Schedule for Minimum Mean Flow Time

   Figure 2: Berthing Schedule for Minimum Make Span

   4- CONCLUSION

   This research presented a mathematical model for berth allocation in port terminals. The model considered continuous berth which was less tackled by researches due to the complexity of the problem. The model was found to capable of finding optimal feasible berthing schedules. It was found to be capable of solving small sized problems in reasonable computational time. While for medium and large size problems, exact solver failed to obtain an integer optimal solution. The developed model was used to study port performance for different problem objectives. Different performance measures were evaluated to determine the appropriate objective for solving berth allocation problems under given conditions. Future work may include developing a solution tool based on metaheuristics in order to be able to solve larger problems in reasonable computational time. Further investigation for port performance considering other factors and parameters is also a potential research topic.

   REFERENCES

   1. A. Imai, Corrigendum to The dynamic berth allocation problem for a container port , vol. 39, p. 6365, 2005.

   2. A. Imai, E. Nishimura, and S. Papadimitriou, Berth allocation with service priority, Transp. Res. Part B Methodol., vol. 37, no. 5, pp. 437457, 2003.

   3. M. Golias, I. Portal, D. Konur, E. Kaisar, and G. Kolomvos, Robust berth scheduling at marine container terminals via hierarchical optimization, Comput. Oper. Res., vol. 41, no. 1, pp. 412422, 2014.

   4. P. Hansen, C. Ouz, and N. Mladenovi, Variable neighborhood search for minimum cost berth allocation, Eur. J. Oper. Res., vol. 191, no. 3, pp. 636649, 2008.

   5. A. Imai, X. Sun, E. Nishimura, and S. Papadimitriou, Berth allocation in a container port: Using a continuous location space approach, Transp. Res. Part B Methodol., vol. 39, no. 3, pp. 199221, 2005.

   6. P. Legato and R. M. Mazza, Berth Planning and Resources Optimization at a Container Terminal via Discrete Event Simulation, Eur. J. Oper. Res., vol. 133, pp. 537547, 2001.

   7. E. Lalla-Ruiz, J. L. Gonzalez-Velarde, B. Melian-Batista, and J. M. Moreno-Vega, Biased random key genetic algorithm for the Tactical Berth Allocation Problem, Appl. Soft Comput. J., vol. 22, pp. 6076, 2014.

   8. S. Yan, C.-C. Lu, J.-H. Hsieh, and H.-C. Lin, A network flow model for the dynamic and flexible berth allocation problem, Comput. Ind. Eng., vol. 81, pp. 6577, 2015.