The berth allocation problem (also known as the berth scheduling problem) is a NP-complete problem in operations research, regarding the allocation of berth space for vessels in container terminals. Vessels arrive over time and the terminal operator needs to assign them to berths in order to be served (loading and unloading containers) as soon as possible. Different factors affect the berth and time assignment of each vessel.

Among models found in the literature, there are four most frequently observed cases:[citation needed]

  1. discrete vs. continuous berthing space,
  2. static vs. dynamic vessel arrivals,
  3. static vs. dynamic vessel handling times, and
  4. variable vessel arrivals.

In the discrete problem, the quay is viewed as a finite set of berths. In the continuous problem, vessels can berth anywhere along the quay and the majority of research deals with the former case. In the static arrival problem all vessels are already at the port whereas in the dynamic only a portion of the vessels to be scheduled are present. The majority of the published research in berth scheduling considers the latter case. In the static handling time problem, vessel handling times are considered as input, whereas in the dynamic they are decision variables. Finally, in the last case, the vessel arrival times are considered as variables and are optimized.

Technical restrictions such as berthing draft and inter-vessel and end-berth clearance distance are further assumptions that have been adopted in some of the studies dealing with the berth allocation problem, bringing the problem formulation closer to real world conditions. Introducing technical restrictions to existing berth allocation models is rather straightforward and it may increase the complexity of the problem but simplify the use of metaheuristics (decrease in the feasible space).

Some of the most notable objectives addressed in the literature are:[citation needed]

  1. Minimization of vessel total service times (waiting and handling times),
  2. Minimization of early and delayed departures,
  3. Optimization of vessel arrival times,
  4. Optimization of emissions and fuel consumption.

Problems have been formulated[by whom?] as single and multi-objective as well as single and bi-level.

See also

Further reading

  • Golias, Mihalis M.; et al. (2009). "The berth allocation problem: Optimizing vessel arrival time". Maritime Economics & Logistics. 11 (4): 358–377. doi:. S2CID .
  • Guan, Yongpei; Cheung, Raymond K. (2004). "The berth allocation problem: models and solution methods". OR Spectrum. 26 (1): 75–92. doi:. S2CID .
  • Pinedo, Michael L. (2008). Scheduling: Theory, Algorithms, and Systems. New York: Springer. ISBN 978-0-387-78934-7.
  • Briano C, Briano E., Bruzzone A. G., Revetria R. (2005) 2019-08-03 at the Wayback Machine. 19th European Conference on Modeling and Simulation. June 1–4, 2005 Riga, Latvia
  • Brown G.G., Cormican K.J., Lawphongpanich S., and Widdis, D.B. . Naval Research Logistics. Vol. 44, 1997, pp. 301–318.
  • Brown G.G., Lawphongpanich S., and Thurman K.P. Optimizing vessel berthing. Naval Research Logistics, Vol. 41, 1994, pp. 1–15.
  • Canonaco, P., Legato, P., Mazza, R., Musmanno, R. . Computers and Operations Research, Vol. 35(8), 2008, pp. 2432–2446.
  • Cordeau, J.-F., Laporte, G., Legato, P., Moccia, L. . Transportation Science. Vol. 39, 2005, pp. 526–538.
  • Dai, J., Liu, W., Moorthy, R. and Teo, C.-P. .
  • Dragović, B., Park N-K, Radmilović Z. . Maritime Policy & Management, Vol. 33 (3), 2006, pp. 281–299.
  • Edmond E. D., and Maggs R. P., 1978. Journal of the Operational Research Society, Vol. 29, 1978, pp. 741–750.
  • Golias M.M. (2011) . Journal of Maritime Economics and Logistics. 13:419-441
  • Golias M.M., Haralambides H.E. . (2011) Journal of Maritime Economics and Logistics. 13:174-189
  • Golias M.M., Boilé M., Theofanis S., Efstathiou C. (2010) . Transportation Research Record: Journal of the Transportation Research Board, Marine Transportation and Port Operations, 2166, 20-27.
  • Golias M.M., Boilé M., Theofanis S. (2010) . Transportation Research Record: Journal of the Transportation Research Board, Freight Transportation Modeling, Planning, and Logistics, 2168, 1-8.
  • Golias M.M., Boilé M., Theofanis S., Taboada A.H. (2010) . International Journal of Information Technology Project Management, 1(1), 54-73.
  • Saharidis G.K.D., Golias M.M., Boilé M., Theofanis S., Ierapetritou M. (2009) . International Journal of Advanced Manufacturing Technology, 46(1-4), 377-393.
  • Golias M.M., Boilé M., Theofanis S. (2009) Service time based customer differentiation berth scheduling. Transportation Research Part E: Logistics and Transportation Review, 45(6), 878-892.
  • Golias M.M., Boilé M., Theofanis S. (2009) A lambda-optimization based heuristic for the discrete berth scheduling problem. Transportation Research Pt. C, 18(5), 794-806.
  • Golias M.M., Boilé M., Theofanis S. (2009) An adaptive time window partitioning based algorithm for the discrete and dynamic berth scheduling problem. Transportation Research Record: Journal of the Transportation Research Board, Network Modeling, 2091, 21-30.
  • Boilé M., Golias M.M., Theofanis S. (2009) Scheduling of berthing resources at a marine container terminal via the use of Genetic Algorithms: Current and Future Research. In: Pinheiro dos Santos, Wellington et al. (Eds.), Evolutionary Computation. Vukovar: In-Teh. ISBN 978-953-307-008-7, pp. 61–76.
  • Guan Y, Xiao W-Q, Cheung R K, and Li C-L. . Operations Research Letters, Vol. 30, 2002, pp. 343–350.
  • Han M., Ping L., and Sun J. “”, 9th International Conference on Control, Automation, Robotics and Vision, ICARCV, 2006.
  • Hansen P., and Oguz C. . Report, Les Cahiers du Gerad, G-2003-20, 2003.
  • Hansen, P., Oguz, C. and Mladenovic, N. [dead link]. European Journal of Operational Research, Vol. 131(3), 2008, pp. 636–649.
  • Imai A., J-T. Zhang, E. Nishimura, and S. Papadimitriou. [dead link], Maritime Economics & Logistics, Vol. 9, 2007, pp. 269–290.
  • Imai A., Nagaiwa K., Tat C-W. . Journal of Advanced Transportation, Vol. 31, 1997, pp. 75–94.
  • Imai A., Nishimura E., and Papadimitriou S. 2019-08-03 at the Wayback Machine. Transportation Research Part B, Vol. 37, 2003, pp. 437–457.
  • Imai A., Nishimura E., Hattori M., and Papadimitriou S. . European Journal of Operations Research, Vol. 179 (2), 2007, pp. 579–593.
  • Imai A., Sun X., Nishimura E., and Papadimitriou S. . Transportation Research Part B, Vol. 39, 2005, pp. 199–221.
  • Imai, A., Nishimura, E. and Papadimitriou, S. . Transportation Research Part E, Vol. 44(1), 2007, pp. 136–151.
  • Imai, A., Nishimura, E. and Papadimitriou, S. Corrigendum to “The dynamic berth allocation problem for a container port”. Transportation Research Part B, Vol. 39(3), 2005a, p. 197.
  • Imai, A., Nishimura, E., Papadimitriou, S. . Transportation Research Part B, Vol. 35, 2001, pp. 401–417.
  • Iris, C., Pacino, D., Ropke, S., Larsen, A., . Transportation Research Part E, Vol. 81, 2015, pp. 75–97.
  • Kim K.H., and Moon K.C. . Transportation Research Part B, Vol. 37, 2003, pp. 541–560.
  • Lai K.K, and Shih K. . Journal of Advanced Transportation, Vol. 26, 1992, pp. 45–60.
  • Lee D-H, Song L., and Wang H.,. A genetic algorithm for a bi-level programming model of berth allocation and quay crane scheduling. Proceedings of the 2006 Annual Transportation Research Board Meeting. Washington D.C., 2006.
  • Lee, Y. and Chen, Y.-C. . European Journal of Operational Research, 2008 (In Press).
  • Legato, P. and Mazza, R. . European Journal of Operational Research, Vol.133(3), 2001
  • Li C-L, Cai X, and Lee C-Y. . IIE Transactions. Vol. 30, 1998, pp. 433–445.
  • Lim A. . Operations Research Letters .Vol. 22, 1998, pp. 105–110.
  • Lokuge, P. and Alahakoon, P. . European Journal of Operational research, Vol. 177(3), 2007, pp. 1985–2015.
  • Meersmans, P.J.M. and Dekker, R. Operations Research supports container handling. Econometric Institute Report EI 2001-22, Erasmus University, Netherlands, 2001.
  • Meisel F. and Bierwirth C., . Operations Research Proceedings, Vol. 2005, Springer Berlin Heidelberg, 2006.
  • Meisel, F. (2009). . Physica-Verlag Berlin Heidelberg.
  • Meisel, F., and Bierwirth, C. (2009) . Transportation Research Part E 45(1): 196-209.
  • Monaco, M.F. and Samara, M. ”, Transportation Science, Vol. 41, No.2, 2007, pp. 265–280.
  • Moorthy R. and Teo C-P. . OR Spectrum. Vol. 28(4), 2006, pp. 495–518.
  • Nikolaou N.S. . Journal of Waterways Highways Div. Proc. Am. Soc. Civ. Engrs., Vol. 93, 1967, pp. 107–132.
  • Nishimura E., Imai A., Papadimitriou S. [dead link]. European Journal of Operational Research, Vol. 131, 2001, pp. 282–292.
  • Notteboom, T.E. The time factor in Liner Services. Maritime Economics and Logistics, Vol. 8(1), 2006, pp. 19–39.
  • Park M.Y., and Kim H.K.A. . OR Spectrum, Vol. 25, 2003, pp. 1–23.
  • Park, K.T. and Kim, K.H. . Journal of Operational Research Society, Vol. 53, 2002, pp. 1054–1062.
  • Stahlbock, R. and Voss, S. . OR Spectrum, Vol. 30, 2007, pp. 1–52.
  • Steenken, D., Voss, S. and Stahlbock, R. . OR Spectrum, Vol. 26, 2004, pp. 3–49.
  • Theofanis S., Boilé M., Golias M.M (2009) [dead link]. Transportation Research Record: Journal of the Transportation Research Board, Marine Transportation and Port Operations, 2100, 22-28.
  • Tong, C.J., Lau, H.C. and Lim, A. . Proceedings of the Asian Comp. Sci. Conf. (ASIAN), pp. 359–370, 1999.
  • Umang, N., Bierlaire, M. and Vacca, I. . Transportation Research Part E: Logistics and Transportation Review, Vol. 54, 2013, pp. 14–31.
  • Vis, I.F.A. and de Koster, R. . European Journal of Operational Research, Vol.147, 2003, pp. 1–16.
  • Wang F, Lim A (2007) . Decision Support Systems, Vol. 42, 2007, pp. 2186–2196.
  • Zhou P, Kang H., and Lin L. (2006) . Proceedings of the 6th World Congress on Intelligent Control and Automation. Dalian, China.
  • Karam, A., and A. B. Eltawil. "." Logistics, Informatics and Service Sciences (LISS), 2015 International Conference on. IEEE, 2015.
  • El-Boghdadly, T., Bader-El-Den, M., & Jones, D. (2016, July). . In Evolutionary Computation (CEC), 2016 IEEE Congress on (pp. 2880-2887). IEEE.
  • Wang, C., Miao, L., Zhang, C., Wu, T., & Liang, Z. (2023). . Naval Research Logistics (NRL), 1–25.