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.
Accepté le :
DOI : 10.1051/ro/2014039
Mots-clés : Container terminal, linear program, non-linear program, dynamic berth allocation
@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://www.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://www.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://www.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, Tome 49 (2015) no. 3, pp. 473-494. doi : 10.1051/ro/2014039. http://www.numdam.org/articles/10.1051/ro/2014039/
N. Al-Dhaheri and A. Diabat, The quay crane scheduling problem. J. Manuf. Syst., in press, 2015.
and , A survey of berth allocation and quay crane scheduling problems in container terminals. Eur. J. Oper. Res. 202 (2010) 615–627. | DOI | Zbl
, , and , Models and tabu search heuristics for the berth-allocation problem. Transp. Sci. 39 (2005) 526–538. | DOI
, , A Lagrangian relaxation approach for solving the integrated quay crane assignment and scheduling problem. Appl. Math. Modell. 32 (2015) 1194–1201. | MR | Zbl
, , An integrated quay crane assignment and scheduling problem. Comput. Ind. Eng. 73 (2014) 115–123. | DOI
, , , 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.
and , A note on formulations of static and dynamic berth allocation problems. Les Cahiers du GERAD 30 (2003) 1–17.
and , , Variable neighborhood search for minimum cost berth allocation. Eur. J. Operat. Res. 191 (2008) 636–649. | DOI | Zbl
, , and , The simultaneous berth and quay crane allocation problem. Transp. Res. Part E 44 (2008) 900–920. | DOI
, and , Efficient planning of berth allocation for container terminals in Asia. J. Adv. Transp. 31 (1997) 75–94. | DOI
, and , The dynamic berth allocation problem for a container port. Transp. Res. Part B 35 (2001) 401–417. | DOI
, and , Berth allocation with service priority. Transp. Res. Part B 37 (2003) 437–457. | DOI
, and , Berthing ships at a multi-user container terminal with a limited quay capacity. Transp. Res. Part E 44 (2008) 136–151. | DOI
, , and , 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
and , 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.
, and , 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.
Cité par Sources :
