Berth allocation problem

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 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:

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:

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 as single and multi-objective as well as single and bi-level.

See also

• List of NP-complete problems
• Quay crane scheduling
• Container terminals

Further reading

• Golias, Mihalis M.; et al. (2009). "The berth allocation problem: Optimizing vessel arrival time". Maritime Economics & Logistics. 11 (4): 358–377. doi:10.1057/mel.2009.12.
• Guan, Yongpei; Cheung, Raymond K. (2004). "The berth allocation problem: models and solution methods". OR Spectrum. 26 (1): 75–92. doi:10.1007/s00291-003-0140-8.
• 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) Models for Support Maritime Logistics: A Case Study for Improving Terminal Planning. 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. Optimizing submarine berthing with a persistence incentive. 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. A queuing network model for the management of berth crane operations. Computers and Operations Research, Vol. 35(8), 2008, pp. 2432–2446.
• Cordeau, J.-F., Laporte, G., Legato, P., Moccia, L. Models and tabu search heuristics for the berth-allocation problem. Transportation Science. Vol. 39, 2005, pp. 526–538.
• Dai, J., Liu, W., Moorthy, R. and Teo, C.-P. Berth Allocation Planning Optimization in Container Terminals. http://www.bschool.nus.edu.sg/staff/bizteocp/berthplanningjuly2004.pdf%5B%5D
• Dragović, B., Park N-K, Radmilović Z. Ship-berth link performance evaluation: simulation and analytical approaches. Maritime Policy & Management, Vol. 33 (3), 2006, pp. 281–299.
• Edmond E. D., and Maggs R. P., 1978. How useful are queue models in port investment decisions for container berths? Journal of the Operational Research Society, Vol. 29, 1978, pp. 741–750.
• Golias M.M. (2011) A bi-objective berth allocation formulation to account for vessel handling time uncertainty. Journal of Maritime Economics and Logistics. 13:419-441
• Golias M.M., Haralambides H.E. Berth scheduling with variable cost functions. (2011) Journal of Maritime Economics and Logistics. 13:174-189
• Golias M.M., Boilé M., Theofanis S., Efstathiou C. (2010) The berth scheduling problem: Maximizing berth productivity and minimizing fuel consumption and emissions production. 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) The discrete berth scheduling problem: Towards a unified mathematical formulation. 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) A multi-objective decision and analysis approach for the berth scheduling problem. 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) The berth scheduling problem with customer differentiation: A new methodological approach based on hierarchical optimization. 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. A multiprocessor task scheduling model for berth allocation: heuristic and worst case analysis. Operations Research Letters, Vol. 30, 2002, pp. 343–350.
• Han M., Ping L., and Sun J. “The Algorithm For Berth Scheduling Problem By The Hybrid Optimization Strategy GASA”, 9th International Conference on Control, Automation, Robotics and Vision, ICARCV, 2006.
• Hansen P., and Oguz C. A note on formulations of static and dynamic berth allocation problems. Report, Les Cahiers du Gerad, G-2003-20, 2003.
• Hansen, P., Oguz, C. and Mladenovic, N. Variable neighborhood search for minimum cost berth allocation. European Journal of Operational Research, Vol. 131(3), 2008, pp. 636–649.
• Imai A., J-T. Zhang, E. Nishimura, and S. Papadimitriou. The Berth Allocation Problem with Service Time and Delay Time Objectives, Maritime Economics & Logistics, Vol. 9, 2007, pp. 269–290.
• Imai A., Nagaiwa K., Tat C-W. Efficient planning of berth allocation for container terminals in Asia. Journal of Advanced Transportation, Vol. 31, 1997, pp. 75–94.
• Imai A., Nishimura E., and Papadimitriou S. Berth allocation with service priority. Transportation Research Part B, Vol. 37, 2003, pp. 437–457.
• Imai A., Nishimura E., Hattori M., and Papadimitriou S. Berth allocation at indented berths for mega-containerships. European Journal of Operations Research, Vol. 179 (2), 2007, pp. 579–593.
• Imai A., Sun X., Nishimura E., and Papadimitriou S. Berth Allocation in a Container Port: Using Continuous Location Space Approach. Transportation Research Part B, Vol. 39, 2005, pp. 199–221.
• Imai, A., Nishimura, E. and Papadimitriou, S. Berthing ships at a multi-user container terminal with a limited quay capacity. 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. The dynamic berth allocation problem for a container port. Transportation Research Part B, Vol. 35, 2001, pp. 401–417.
• Iris, C., Pacino, D., Ropke, S., Larsen, A., Integrated Berth Allocation and Quay Crane Assignment Problem: Set partitioning models and computational results. Transportation Research Part E, Vol. 81, 2015, pp. 75–97.
• Kim K.H., and Moon K.C. Berth scheduling by simulated annealing. Transportation Research Part B, Vol. 37, 2003, pp. 541–560.
• Lai K.K, and Shih K. A study of container berth allocation. 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. An Optimization Heuristic for the Berth Scheduling Problem. European Journal of Operational Research, 2008 (In Press).
• Legato, P. and Mazza, R. Berth Planning and resources optimization at a container terminal via discrete event simulation. European Journal of Operational Research, Vol.133(3), 2001
• Li C-L, Cai X, and Lee C-Y. Scheduling with multiple-job-on-one-processor pattern. IIE Transactions. Vol. 30, 1998, pp. 433–445.
• Lim A. The berth planning problem. Operations Research Letters .Vol. 22, 1998, pp. 105–110.
• Lokuge, P. and Alahakoon, P. Improving the adaptability in automated vessel scheduling in container ports using intelligent software agents. 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., Integration of Berth Allocation and Crane Assignment to Improve the Resource Utilization at a Seaport Container Terminal. Operations Research Proceedings, Vol. 2005, Springer Berlin Heidelberg, 2006.
• Meisel, F. (2009). Seaside operations planning in container terminals. Physica-Verlag Berlin Heidelberg.
• Meisel, F., and Bierwirth, C. (2009) Heuristics for the integration of crane productivity in the berth allocation problem. Transportation Research Part E 45(1): 196-209.
• Monaco, M.F. and Samara, M. The Berth Allocation Problem: a Strong Formulation Solved by a Lagrangean Approach”, Transportation Science, Vol. 41, No.2, 2007, pp. 265–280.
• Moorthy R. and Teo C-P. Berth Management in Container Terminal: The Template Design Problem. OR Spectrum. Vol. 28(4), 2006, pp. 495–518.
• Nikolaou N.S. Berth planning by evaluation of congestion and cost. Journal of Waterways Highways Div. Proc. Am. Soc. Civ. Engrs., Vol. 93, 1967, pp. 107–132.
• Nishimura E., Imai A., Papadimitriou S. Berth allocation planning in the public berth system by genetic algorithms. 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. Scheduling method for berth and quay cranes. OR Spectrum, Vol. 25, 2003, pp. 1–23.
• Park, K.T. and Kim, K.H. Berth scheduling for container terminals by using sub-gradient optimization techniques. Journal of Operational Research Society, Vol. 53, 2002, pp. 1054–1062.
• Stahlbock, R. and Voss, S. Operations research at container terminals: a literature update. OR Spectrum, Vol. 30, 2007, pp. 1–52.
• Steenken, D., Voss, S. and Stahlbock, R. Container terminal operation and operations research – a classification and literature review. OR Spectrum, Vol. 26, 2004, pp. 3–49.
• Theofanis S., Boilé M., Golias M.M (2009) Container terminal berth planning: critical review of research approaches and practical challenges. 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. Ant Colony Optimization for the Ship Berthing Problem. Proceedings of the Asian Comp. Sci. Conf. (ASIAN), pp. 359–370, 1999.
• Umang, N., Bierlaire, M. and Vacca, I. Exact and heuristic methods to solve the berth allocation problem in bulk ports. Transportation Research Part E: Logistics and Transportation Review, Vol. 54, 2013, pp. 14–31.
• Vis, I.F.A. and de Koster, R. Transshipment of containers at a container terminal: An overview. European Journal of Operational Research, Vol.147, 2003, pp. 1–16.
• Wang F, Lim A (2007) A stochastic beam search for the berth allocation problem. Decision Support Systems, Vol. 42, 2007, pp. 2186–2196.
• Zhou P, Kang H., and Lin L. (2006) A Dynamic Berth Allocation Model Based on Stochastic Consideration. Proceedings of the 6th World Congress on Intelligent Control and Automation. Dalian, China.
• Karam, A., and A. B. Eltawil. "A new method for allocating berths, quay cranes and internal trucks in container terminals." Logistics, Informatics and Service Sciences (LISS), 2015 International Conference on. IEEE, 2015.
• El-Boghdadly, T., Bader-El-Den, M., & Jones, D. (2016, July). Evolving local search heuristics for the integrated berth allocation and quay crane assignment problem. In Evolutionary Computation (CEC), 2016 IEEE Congress on (pp. 2880-2887). IEEE.