The Dynamic Berth Allocation Problem: A linearized formulation
RAIRO - Operations Research - Recherche Opérationnelle, Volume 49 (2015) no. 3, pp. 473-494.

International shipping is a multi-billion dollar business which has undergone significant growth during the last decade. Considerable benefits could be gained by improving and optimizing container terminal operations. One specific challenge facing container terminals is the berth allocation problem, referred to as (BAP). In this paper, a new formulation is proposed for the dynamic berth allocation problem (DBAP). Initially the problem was formulated as a non-linear mixed integer program, followed by incorporating techniques to present an equivalent mixed integer program (MIP). A genetic algorithm (GA) heuristic was developed and applied to different instances of the problems, and through computational experiments the best, average, and worst case performances were analyzed to determine the efficiency of the algorithms.

Received:
Accepted:
DOI: 10.1051/ro/2014039
Classification: 90Bxx
Keywords: Container terminal, linear program, non-linear program, dynamic berth allocation
Simrin, Ahmed 1; Diabat, Ali 1

1 Department of Engineering Systems & Management, Masdar Institute of Science & Technology, Abu Dhabi, United Arab Emirates.
@article{RO_2015__49_3_473_0,
     author = {Simrin, Ahmed and Diabat, Ali},
     title = {The {Dynamic} {Berth} {Allocation} {Problem:} {A} linearized formulation},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {473--494},
     publisher = {EDP-Sciences},
     volume = {49},
     number = {3},
     year = {2015},
     doi = {10.1051/ro/2014039},
     mrnumber = {3349130},
     zbl = {1322.90022},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ro/2014039/}
}
TY  - JOUR
AU  - Simrin, Ahmed
AU  - Diabat, Ali
TI  - The Dynamic Berth Allocation Problem: A linearized formulation
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2015
SP  - 473
EP  - 494
VL  - 49
IS  - 3
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ro/2014039/
DO  - 10.1051/ro/2014039
LA  - en
ID  - RO_2015__49_3_473_0
ER  - 
%0 Journal Article
%A Simrin, Ahmed
%A Diabat, Ali
%T The Dynamic Berth Allocation Problem: A linearized formulation
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2015
%P 473-494
%V 49
%N 3
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ro/2014039/
%R 10.1051/ro/2014039
%G en
%F RO_2015__49_3_473_0
Simrin, Ahmed; Diabat, Ali. The Dynamic Berth Allocation Problem: A linearized formulation. RAIRO - Operations Research - Recherche Opérationnelle, Volume 49 (2015) no. 3, pp. 473-494. doi : 10.1051/ro/2014039. http://archive.numdam.org/articles/10.1051/ro/2014039/

N. Al-Dhaheri and A. Diabat, The quay crane scheduling problem. J. Manuf. Syst., in press, 2015.

C. Bierwirth and F. Meisel, A survey of berth allocation and quay crane scheduling problems in container terminals. Eur. J. Oper. Res. 202 (2010) 615–627. | DOI | Zbl

J.-F. Cordeau, G. Laporte, P. Legato and L. Moccia, Models and tabu search heuristics for the berth-allocation problem. Transp. Sci. 39 (2005) 526–538. | DOI

A. Diabat, Y.-M. Fu, A Lagrangian relaxation approach for solving the integrated quay crane assignment and scheduling problem. Appl. Math. Modell. 32 (2015) 1194–1201. | MR | Zbl

A. Diabat, E. Theodorou, An integrated quay crane assignment and scheduling problem. Comput. Ind. Eng. 73 (2014) 115–123. | DOI

Y.-M. Fu, A. Diabat, I.-T. Tsai, A multi-vessel quay crane assignment and scheduling problem: Formulation and heuristic solution approach. Exp. Syst. Appl. 41 (2014) 6959–6965. | DOI

M. Han, P. Li and J. Sun. The algorithm for berth scheduling problem by the hybrid optimization strategy GASA, in Proc. of the ninth international conference on Control, automation, robotics and vision (ICARCV’06). IEEE Comput. Soc., Washington DC (2006) 1–4.

P. Hansen and C. Oguz, A note on formulations of static and dynamic berth allocation problems. Les Cahiers du GERAD 30 (2003) 1–17.

P. Hansen and C. Oguz, N. Mladenovic, Variable neighborhood search for minimum cost berth allocation. Eur. J. Operat. Res. 191 (2008) 636–649. | DOI | Zbl

A. Imai, H.C. Chen, E. Nishimura and S. Papadimitriou, The simultaneous berth and quay crane allocation problem. Transp. Res. Part E 44 (2008) 900–920. | DOI

A. Imai, K. Nagaiwa and C.W. Tat, Efficient planning of berth allocation for container terminals in Asia. J. Adv. Transp. 31 (1997) 75–94. | DOI

A. Imai, E. Nishimura and S. Papadimitriou, The dynamic berth allocation problem for a container port. Transp. Res. Part B 35 (2001) 401–417. | DOI

A. Imai, E. Nishimura and S. Papadimitriou, Berth allocation with service priority. Transp. Res. Part B 37 (2003) 437–457. | DOI

A. Imai, E. Nishimura and S. Papadimitriou, Berthing ships at a multi-user container terminal with a limited quay capacity. Transp. Res. Part E 44 (2008) 136–151. | DOI

A. Imai, J.-T. Zhang, E. Nishimura and S. Papadimitriou, The berth allocation problem with service time and delay time objectives. Marit. Econ. Logist. 9 (2007b) 269–290. | DOI

D.-H. Lee, L. Song and H. Wang, Bilevel programming model and solutions of berth allocation and quay crane scheduling, in Proc. of 85th annual meeting of Transportation research board (CD-ROM), Washington DC (2006).

G.R. Mauri, A.C.M. Oliveira and L.A.N. Lorena, A hybrid column generation approach for the berth allocation problem, in Eighth European conference on Evolutionary computation in combinatorial optimisation EvoCOP, edited by J. van Hemert, C. Cotta. Lect. Note Comput. Sci., 4972, Springer, Berlin (2008) 110–122. | MR

M.F. Monaco and M. Sammarra, The berth allocation problem: a strong formulation solved by a Lagrangean approach. Transp. Sci. 41 (2007) 265–280. | DOI

S. Theofanis, M. Boile and M. Golias, An optimization based genetic algorithm heuristic for the berth allocation problem, in Proc. of IEEE congress on Evolutionary computation (CEC 2007). IEEE Computer Society, Washington DC (2007) 4439–4445.

C. Liang, Y. Huang and Y. Yang, A quay crane dynamic scheduling problem by hybrid evolutionary algorithm for berth allocation planning, Comput. Ind. Engrg. 56 (2008) 1021−1028. | DOI

G. Giallombardo, L. Moccia, M. Salani and I. Vacca, The tactical berth allocation problem with quay crane assignment and transshipment-related quadratic yard costs, in Proc. of the European Transport Conference (ETC) (2008) 1–27.

A. Popov, Genetic algorithms for optimization, User Manual (2005).

E. Theodorou, A. Diabat, A joint quay crane assignment and scheduling problem: formulation, solution algorithm and computational results. Optim. Lett., in press, 2014. | MR

P. Zhou, H. Kang and L. Lin, A dynamic berth allocation model based on stochastic consideration, in Proc. of the Sixth World Congress on Intelligent Control and Automation WCICA, IEEE Comput. Soc. Vol. 2, Washington DC (2006) 7297–7301.

Cited by Sources: