Berth Allocation Problem: Formulation and a Tunisian Case Study

Lobna KALLEL; Ezzeddine BENAISSA; Hichem KAMOUN; Mounir BENAISSA

doi:10.5604/01.3001.0013.6165

Authors

Lobna KALLEL University of Sfax, LOGIQ Laboratory, ISGI, Sfax, Tunisia Author https://orcid.org/0000-0001-9016-5463
Ezzeddine BENAISSA University of Sfax, LOGIQ Laboratory, ISGI, Sfax, Tunisia Author https://orcid.org/0000-0001-9894-2036
Hichem KAMOUN University of Sfax, MODELIS Laboratory, FSEG, Sfax, Tunisia Author https://orcid.org/0000-0002-6721-8958
Mounir BENAISSA Taif Univesity, Engineering Department, Taif, Saudi Arabia Author https://orcid.org/0000-0003-0487-1877

DOI:

https://doi.org/10.5604/01.3001.0013.6165

Keywords:

container terminals, seaport, Berth Allocation, flow time, scheduling of tasks, Tunisian port of Rades

Abstract

This paper examines one of the most important operational problems in seaport terminals, namely the Berth Allocation Problem (BAP) which finds an optimal assignment of ships to the berths that minimize the total waiting time of all ships and reduce congestion in ports. Our problem is to affect and schedule n ships on m berths to minimize the processing time and the waiting time for all the ships in the port. Therefore, ships stay time in the port known by the flow time, while respecting the physical constraints existing at the port (such as the depth of the water berth and the draft of the ship’s water), knowing that each ship can only accommodate one ship at a time. It is as if it was a case of n tasks and m machines in parallel, and we wanted to schedule the passage of different tasks on different machines, knowing that each task can only pass on one machine and that the interruption of the task is not allowed. For example, if a job started on a machine, it will remain on this machine up to its completion. In our case, tasks are ships and machines are berths that are opting to minimize the total flow time and, therefore, to decrease the residence time of all the ships in the port. In a first step, a Mixed Integer Linear Program model is designed to address the BAP with the aim of minimizing the flow time of the ships in the port, our sample can be used for both static and dynamic berth allocation cases. In a second step, this model is illustrated with a real case study in the Tunisian port of Rades and solved by a commercial solver CPLEX. Calculation results are presented and compared with those obtained by port authorities in Radès.

References

Arango, C., Cortés, P., Muñuzuri, J., & Onieva, L. (2011). Berth allocation planning in Seville inland port by simulation and optimisation. Advanced Engineering Informatics, 25(3), 452-461.

Barros, V. H., Costa, T. S., Oliveira, A. C., & Lorena, L. A. (2011). Model and heuristic for berth allocation in tidal bulk ports with stock level constraints. Computers & Industrial Engineering, 60(4), 606-613.

Golias, M. M., Boile, M., & Theofanis, S. (2009). Berth scheduling by customer service differentiation: A multi-objective approach. Transportation Research Part E: Logistics and Transportation Review, 45(6), 878-892.

Guan, Y., & Cheung, R. K. (2004). The berth allocation problem: models and solution methods. Or Spectrum, 26(1), 75-92.

Hansen, P., & Oguz, C. (2003). A note on formulations of the static and dynamic berth allocation problems. Groupe d'études et de recherche en analyse des décisions, HEC Montréal.

Hansen, P., Oğuz, C., & Mladenović, N. (2008). Variable neighborhood search for minimum cost berth allocation. European Journal of Operational Research, 191(3), 636-649.

Imai, A., Nishimura, E., & Papadimitriou, S. (2001). The dynamic berth allocation problem for a container port. Transportation Research Part B: Methodological, 35(4), 401-417.

Imai, A., Nishimura, E., & Papadimitriou, S. (2003). Berth allocation with service priority. Transportation Research Part B: Methodological, 37(5), 437-457.

Imai, A., Sasaki, K., Nishimura, E., & Papadimitriou, S. (2006). Multi-objective simultaneous stowage and load planning for a container ship with container rehandle in yard stacks. European Journal of Operational Research, 171(2), 373-389.

Imai, A., Sun, X., Nishimura, E., & Papadimitriou, S. (2005). Berth allocation in a container port: using a continuous location space approach. Transportation Research Part B: Methodological, 39(3), 199-221.

Kim, K. H., & Moon, K. C. (2003). Berth scheduling by simulated annealing. Transportation Research Part B: Methodological, 37(6), 541-560.

Lai, K. K., & Shih, K. (1992). A study of container berth allocation. Journal of advanced transportation, 26(1), 45-60.

Lee, D. H., Cao, J. X., Shi, Q., & Chen, J. H. (2009). A heuristic algorithm for yard truck scheduling and storage allocation problems. Transportation Research Part E: Logistics and Transportation Review, 45(5), 810-820.

Lee, D. H., Cao, Z., & Meng, Q. (2007). Scheduling of two-transtainer systems for loading outbound containers in port container terminals with simulated annealing algorithm. International Journal of Production Economics, 107(1), 115-124.

Lee, D. H., Chen, J. H., & Cao, J. X. (2010). The continuous berth allocation problem: A greedy randomized adaptive search solution. Transportation Research Part E: Logistics and Transportation Review, 46(6), 1017-1029.

Lee, D. H., Wang, H. Q., & Miao, L. (2008). Quay crane scheduling with noninterference constraints in port container terminals. Transportation Research Part E: Logistics and Transportation Review, 44(1), 124-135.

Lee, Loo Hay, Ek Peng Chew, Kok Choon Tan, and Yongbin Han. 2006. ‘An optimization model for storage yard management in trans-shipment hubs.’ Or Spectrum 28 (4), pp.539-561.

Lenstra, J. K., Kan, A. R., & Brucker, P. (1977). Complexity of machine scheduling problems. In Annals of discrete mathematics (Vol. 1, pp. 343-362). Elsevier.

Mironiuk, W. (2015). Model-based investigations on dynamic ship heels in relation to maritime transport safety. Archives of Transport, 33(1), 69-80.

Monaco, M. F., & Sammarra, M. (2007). The berth allocation problem: a strong formulation solved by a Lagrangean approach. Transportation Science, 41(2), 265-280.

Moorthy, R., & Teo, C. P. (2007). Berth management in container terminal: the template design problem. In Container Terminals and Cargo Systems (pp. 63-86). Springer, Berlin, Heidelberg.

Preston, P., & Kozan, E. (2001). An approach to determine storage locations of containers at seaport terminals. Computers & Operations Research, 28(10), 983-995.

Salmonowicz, H., (2014). The global maritime ports in logistics chains and supply networks. Scientific journal of Silesian University of technology. Serie transport, 85(1), pp.107-117.

Vacca, I., Salani, M., & Bierlaire, M. (2013). An exact algorithm for the integrated planning of berth allocation and quay crane assignment. Transportation Science, 47(2), 148-161.

Xu, D., Li, C. L., & Leung, J. Y. T. (2012). Berth allocation with time-dependent physical limitations on vessels. European Journal of Operational Research, 216(1), 47-56.

Zeinebou, Z., & Abdellatif, B. (2013, May). Development of a model of decision support for optimization of physical flows in a container terminal. In 2013 International Conference on Advanced Logistics and Transport (pp. 421-426). IEEE.

Zeinebou, Z., & Abdellatif, B. (2014, May). Comparing the effectiveness of different metaheuristics for optimization of flows of containers in a containers terminal. In 2014 International Conference on Advanced Logistics and Transport (ICALT) (pp. 235-240). IEEE.

Zhen, L., Lee, L. H., & Chew, E. P. (2011). A decision model for berth allocation under un-certainty. European Journal of Operational Re-search, 212(1), 54-68.

Zoubeir, Z., & Benabdelhafid, A. (2014, April). The Development of a Decision Support Model for the Problem of Berths Allocation in Containers Terminal Using a Hybrid of Genetic Algorithm and Simulated Annealing. In Asian Conference on Intelligent Information and Database Systems (pp. 454-463). Springer, Cham.