Robust berth scheduling using machine learning for vessel arrival time prediction

Flexible Services and Manufacturing Journal - Tập 35 - Trang 29-69 - 2022
Lorenz Kolley1, Nicolas Rückert1, Marvin Kastner2, Carlos Jahn2, Kathrin Fischer1
1Institute for Operations Research and Information Systems, Hamburg University of Technology, Hamburg, Germany
2Institute of Maritime Logistics, Hamburg University of Technology, Hamburg, Germany

Tóm tắt

In this work, the potentials of data-driven optimization for the well-known berth allocation problem are studied. The aim of robust berth scheduling is to derive conflict-free vessel assignments at the quay of a terminal, taking into account uncertainty regarding the actual vessel arrival times which may result from external influences as, e.g., cross wind and sea current. In order to achieve robustness, four different Machine Learning methods-from linear regression to an artificial neural network-are employed for vessel arrival time prediction in this work. The different Machine Learning methods are analysed and evaluated with respect to their forecast quality. The calculation and use of so-called dynamic time buffers (DTBs), which are derived from the different AIS-based forecasts and whose length depends on the estimated forecast reliability, in the berth scheduling model enhance the robustness of the resulting schedules considerably, as is shown in an extensive numerical study. Furthermore, the results show that also rather simple Machine Learning approaches are able to reach high forecast accuracy. The optimization model does not only lead to more robust solutions, but also to less actual waiting times for the vessels and hence to an enhanced service quality, as can be shown by studying the resulting schedules for real vessel data. Moreover, it turns out that the accuracy of the resulting berthing schedules, measured as the deviation of planned and actually realisable schedules, exceeds the accuracy of all forecasts which underlines the usefulness of the DTB approach.

Tài liệu tham khảo

Akiba T, Sano S, Yanase T, Ohta T, Koyama M (2019) Optuna: a next-generation hyperparameter optimization framework. In: Proceedings of the 25th SIGKDD international conference on knowledge discovery and data mining. ACM, Anchorage, pp 2623–2631

Arguedas VF, Pallotta G, Vespe M (2018) Maritime traffic networks: from historical positioning data to unsupervised maritime traffic monitoring. IEEE Trans Intell Transp Syst 19:722–732. https://doi.org/10.1109/tits.2017.2699635

Baumgarten P, Malina R, Lange A (2014) The impact of hubbing concentration on flight delays within airline networks: an empirical analysis of the US domestic market. Transp Res E Logist Transp Rev 66:103–114. https://doi.org/10.1016/j.tre.2014.03.007

Belousov B, Abdulsamad H, Klink P, Parisi S, Peters J (Eds) (2021) Reinforcement learning algorithms: analysis and applications. Studies in computational intelligence, vol 883. Springer, Cham: Denmark https://doi.org/10.1007/978-3-030-41188-6

Bergstra J, Bardenet R, Bengio Y, Kégl B (2011) Algorithms for hyper-parameter optimization. In: Advances in neural information processing systems 24. Curran Associates, Granada. https://proceedings.neurips.cc/paper/2011/file/86e8f7ab32cfd12577bc2619bc635690-Paper.pdf

Bergstra J, Bengio Y (2012) Random search for hyper-parameter optimization. J Mach Learn Res 13:281–305

Bierwirth C, Meisel F (2010) A survey of berth allocation and quay crane scheduling problems in container terminals. Eur J Oper Res 202:615–627. https://doi.org/10.1016/j.ejor.2009.05.031

Bierwirth C, Meisel F (2015) A follow-up survey of berth allocation and quay crane scheduling problems in container terminals. Eur J Oper Res 244:675–689. https://doi.org/10.1016/j.ejor.2014.12.030

Bose I, Mahapatra RK (2001) Business data mining-a machine learning perspective. Inf Manag 39:211–225. https://doi.org/10.1016/s0378-7206(01)00091-x

Carlo HJ, Vis IFA, Roodbergen KJ (2015) Seaside operations in container terminals: literature overview, trends, and research directions. Flex Serv Manuf J 27:224–262. https://doi.org/10.1007/s10696-013-9178-3

Chen M, Hao Y, Hwang K, Wang L, Wang L (2017) Disease prediction by machine learning over big data from healthcare communities. IEEE Access 5:8869–8879. https://doi.org/10.1109/ACCESS.2017.2694446

Chen S, Wang F, Wei X, Tan Z, Wang H (2020) Analysis of tugboat activities using AIS data for the Tianjin port. Transp Res Rec 2674:498–509. https://doi.org/10.1177/0361198120916734

Cheimanoff N, Fontane F, Kitri MN, Tchernev N (2021) A reduced VNS based approach for the dynamic continuous berth allocation problem in bulk terminals with tidal constraints. Expert Syst Appl 168:114215. https://doi.org/10.1016/j.eswa.2020.114215

de León AD, Lalla-Ruiz E, Melián-Batista B, Moreno-Vega JM (2017) A machine learning-based system for berth scheduling at bulk terminals. Expert Syst Appl 87:170–182. https://doi.org/10.1016/j.eswa.2017.06.010

Dobrkovic A, Iacob M-E, van Hillegersberg J, Mes MRK, Glandrup M (2016) Towards an approach for long term AIS-based prediction of vessel arrival times. In: Zijm H, Klumpp M, Clause U, ten Hompel M (eds) Logistics and supply chain innovation: bridging the gap between theory and practice, 1st edn. Springer, Cham. https://doi.org/10.1007/978-3-319-22288-2_16

Dobrkovic A, Iacob M-E, van Hillegersberg J (2018) Maritime pattern extraction and route reconstruction from incomplete AIS data. Int J Data Sci Anal 5:111–136. https://doi.org/10.1007/s41060-017-0092-8

Dornemann J, Rückert N, Fischer K, Taraz A (2020) Artificial intelligence and operations research in maritime logistics. In: Jahn C, Kersten W, Ringle CM (Eds.) Data science in maritime and city logistics: data-driven solutions for logistics and sustainability. Proceedings of the Hamburg international conference of logistics. Epubli GmbH, Hamburg, pp 337–381. https://doi.org/10.15480/882.3140

Eggensperger K, Feurer M, Hutter F, Bergstra K, Snoek J, Hoos HH, Leyton-Brown K (2013) Towards an empirical foundation for assessing bayesian optimization of hyperparameters. In: NIPS Workshop on bayesian optimization in theory and practice. https://www.cs.ubc.ca/~hoos/Publ/EggEtAl13.pdf

Fancello G, Pani C, Pisano M, Serra P, Zuddas P, Fadda P (2011) Prediction of arrival times and human resources allocation for container terminal. Marit Econ Logist 13:142–173. https://doi.org/10.1057/mel.2011.3

Feng M, Shaw S-L, Peng G, Fang Z (2020) Time efficiency assessment of ship movements in maritime ports: a case study of two ports based on AIS data. J Transp Geogr 86:102741. https://doi.org/10.1016/j.jtrangeo.2020.102741

Filom S, Amiri AM, Razavi S (2022) Applications of machine learning methods in port operations-a systematic literature review. Transp Res E 161:102722

Franzkeit J, Pache H, Jahn C (2020) Investigation of vessel waiting times using AIS data. In: Freitag M, Haasis H-D, Kotzab H, Pannek J (eds) Dynamics in logistics: proceedings of the 7th international conference LDIC 2020. Springer, Bremen, pp 70–78. https://doi.org/10.1007/978-3-030-44783-0_7

Frochte J (2019) Maschinelles Lernen: Grundlagen und algorithmen in Python, 2nd edn. Hanser, München. https://doi.org/10.3139/9783446459977

Fujino I, Claramunt C, Boudraa A-O (2018) Extracting courses of vessels from AIS data and real-time warning against off-course. In: Proceedings of the 2nd international conference on big data research. ACM, Weihai, pp 62–69. https://doi.org/10.1145/3291801.3291823

Géron A (2018) Praxiseinstieg machine learning Mit Scikit-Learn Und Tensorflow: Konzepte, tools Und Techniken Für Intelligente Systeme, 1st edn. O’Reilly, Heidelberg

Grida M, Lee C-Y (2018) An empirical model for estimating berth and sailing times of mega container ships. Marit Policy Manag 45:1078–1093. https://doi.org/10.1080/03088839.2018.1452304v

Hendriks M, Laumanns M, Lefeber E, Udding JT (2010) Robust cyclic berth planning of container vessels. OR Spectr 32:501–517. https://doi.org/10.1007/s00291-010-0198-z

Heilig L, Stahlbock R, Voß S (2020) From digitalization to data-driven decision making in container terminals. In: Böse JW (ed) Handbook of terminal planning, 2nd edn. Springer, Cham, pp 125–154. https://doi.org/10.1007/978-3-030-39990-0_6

Jahn C, Scheidweiler T (2018) Port call optimization by estimating ships’ time of arrival. In: Freitag M, Kotzab H, Pannek J (eds) Dynamics in logistics: proceedings of the 6th international conference LDIC 2018. Springer, Bremen, pp 172–177. https://doi.org/10.1007/978-3-319-74225-0_23v

Kingma DP, Ba JL (2015) ADAM: A method for stochastic optimization. In: 3rd international conference for learning representations. San Diego. https://arxiv.org/abs/1412.6980

Kolley L, Rückert N, Fischer K (2021) A robust berth allocation optimization procedure based on machine learning. In: Buscher U, Lasch R, Schönberger J (eds) Logistics management contributions of the section logistics of the German Academic Association for business research. Springer, Dresden, pp 107–122. https://doi.org/10.1007/978-3-030-85843-8_7

Kolley L, Rückert N, Kastner M, Jahn C, Fischer K (2022) Robust berth scheduling using machine learning for vessel arrival time prediction-refined dataset. TUHH Universitätsbibliothek. https://doi.org/10.15480/336.4471

Kwun H, Bae H (2021) Prediction of vessel arrival time using auto identification system data. Int J Innov Comput Inf Control 17:725–734. https://doi.org/10.24507/ijicic.17.02.725

Langley P, Simon HA (1995) Applications of machine learning and rule induction. Commun ACM 38:54–64. https://doi.org/10.1145/219717.219768

Lee H-T, Lee J-S, Son W-J, Cho I-S (2020) Development of machine learning strategy for predicting the risk range of ship’s berthing velocity. J Mar Sci Eng 8:376. https://doi.org/10.3390/jmse8050376

Leus R, Herroelen W (2007) Scheduling for stability in single-machine production systems. J Sched 10:223–235. https://doi.org/10.1007/s10951-007-0014-z

Li Y, Chu F, Zheng F, Kacem I (2019) Integrated berth allocation and quay crane assignment with uncertain maintenance activities. In: Zheng F, Chu F, Liu M (ed) 2019 international conference on industrial engineering and systems management. IEEE, Shanghai, pp 1–6. https://doi.org/10.1109/iesm45758.2019.8948115

Li B, He Y (2020) Container terminal liner berthing time prediction with computational logistics and deep learning. In: 2020 IEEE international conference on systems, man, and cybernetics. IEEE, Toronto, pp 2417–2424. https://doi.org/10.1109/smc42975.2020.9282816

Li B, He Y (2021) Computational logistics for container terminal handling systems with deep learning. Comput Intell Neurosci 2021:5529914. https://doi.org/10.1155/2021/5529914

Liu DC, Nocedal J (1989) On the limited memory BFGS method for large scale optimization. Math Prog 45:503–528. https://doi.org/10.1007/BF01589116

Liu C, Xiang X, Zheng L (2017) Two decision models for berth allocation problem under uncertainty considering service level. Flex Serv Manuf J 29:312–344. https://doi.org/10.1007/s10696-017-9295-5

Liu C, Xiang X, Zheng L (2020) A two-stage robust optimization approach for the berth allocation problem under uncertainty. Flex Serv Manuf J 32:425–452. https://doi.org/10.1007/s10696-019-09343-w

Mestl T, Dausendschön K (2016) Port ETA Prediction based on AIS Data. In: Bertram V (ed) 15th international conference on computer and it applications in the maritime industries COMPIT 16. Lecce, Italy, pp 331–338.

Pallotta G, Vespe M, Bryan K (2013) Vessel pattern knowledge discovery from AIS data: a framework for anomaly detection and route prediction. Entropy 15:2218–2245. https://doi.org/10.3390/e15062218

Pani C, Fadda P, Fancello G, Frigau L, Mola F (2014) A data mining approach to forecast late arrivals in a transhipment container terminal. Transport 29:175–184. https://doi.org/10.3846/16484142.2014.930714

Pani C, Vanelslander T, Fancello G, Cannas M (2015) Prediction of late/early arrivals in container terminals-a qualitative approach. Eur J Transp Infrastruct Res 15:536–550. https://doi.org/10.18757/ejtir.2015.15.4.3096

Park K, Sim S, Bae H (2021) Vessel estimated time of arrival prediction system based on a path-finding algorithm. Marit Transp Res 2:100012. https://doi.org/10.1016/j.martra.2021.100012

Parolas I (2016) ETA prediction for containerships at the port of Rotterdam using machine learning techniques. MSc Thesis, TU Delft

Rodriguez-Molins M, Ingolotti L, Barber F, Salido MA, Sierra MR, Puente J (2014a) A genetic algorithm for robust berth allocation and quay crane assignment. Prog Artif Intell 2:177–192. https://doi.org/10.1007/s13748-014-0056-3

Rodriguez-Molins M, Salido MA, Barber F (2014b) Robust scheduling for berth allocation and quay crane assignment problem. Math Probl Eng. https://doi.org/10.1155/2014/834927

Salcedo-Sanz S, Cornejo Bueno L, Prieto L, Paredes D, García-Herrera R (2018) Feature selection in machine learning prediction for renewable energy applications. Renew Sustain Energy Rev 90:728–741. https://doi.org/10.1016/j.rser.2018.04.008

Schmidt-Hieber J (2020) Nonparametric regression using deep neural networks with ReLU activation function. Ann Stat 48:1875–1897. https://doi.org/10.1214/19-AOS1875

Scholl A (2001) Robuste Planung und Optimierung. Physica-Verlag, Heidelberg

Shukla AK, Singh P, Vardhan M (2019) A hybrid framework for optimal feature subset selection. J Intell Fuzzy Syst 36:2247–2259. https://doi.org/10.3233/JIFS-169936

Takano Y, Miyashiro R (2020) Best subset selection via cross-validation criterion. TOP 28:475–488. https://doi.org/10.1007/s11750-020-00538-1

Umang N, Bierlaire M, Erera AL (2017) Real-time management of berth allocation with stochastic arrival and handling times. J Sched 20:67–83. https://doi.org/10.1007/s10951-016-0480-2

Virjonen P, Nevalainen P, Pahikkala T, Heikkonen J (2018) Ship movement prediction using k-NN method. In: 2018 baltic geodetic congress. IEEE. Olsztyn, pp 304–309. https://doi.org/10.1109/bgc-geomatics.2018.00064

Wang Z, Guo C (2018) Minimizing the risk of seaport operations efficiency reduction affected by vessel arrival delay. Ind Manag Data Syst 118:1498–1509. https://doi.org/10.1108/IMDS-12-2017-0563

Wu L, Xu Y, Wang F (2020) Identifying port calls of ships by uncertain reasoning with trajectory data. ISPRS Int J Geo-Inf 9:756. https://doi.org/10.3390/ijgi9120756

Wu Y, Miao L (2020) A robust scheduling model for continuous berth allocation problem under uncertainty. In: 5th international conference on electromechanical control technology and transportation. IEEE. Nanchang, pp 43–49. https://doi.org/10.1109/icectt50890.2020.00017

Xiang X, Liu C, Miao L (2017) A bi-objective robust model for berth allocation scheduling under uncertainty. Transp Res E Logist Transp Rev 106:294–319. https://doi.org/10.1016/j.tre.2017.07.006

Xiao Z, Ponnambalam L, Fu X, Zhang W (2017) Maritime traffic probabilistic forecasting based on vessels’ waterway patterns and motion behaviors. IEEE Trans Intell Transp Syst 18:3122–3134. https://doi.org/10.1109/tits.2017.2681810

Xu Y, Chen Q, Quan X (2012) Robust berth scheduling with uncertain vessel delay and handling time. Ann Oper Res 192:123–140. https://doi.org/10.1007/s10479-010-0820-0

Yang D, Wu L, Wang S, Jia H, Li KX (2019) How big data enriches maritime research–a critical review of automatic identification system (AIS) data applications. Transp Rev 39:755–773. https://doi.org/10.1080/01441647.2019.1649315

Yu J, Tang G, Song X, Yu X, Qi Y, Li Da, Zhang Y (2018) Ship arrival prediction and its value on daily container terminal operation. Ocean Eng 157:73–86. https://doi.org/10.1016/j.oceaneng.2018.03.038

Zhang G, Patuwo BE, Hu MY (1998) Forecasting with artificial neural networks: the state of the art. Int J Forecast 14:35–62. https://doi.org/10.1016/S0169-2070(97)00044-7

Zhang X, Sun B, Sun J, Gou Z (2014) The berth and quay cranes integrated scheduling based on redundancy policy. In: Proceedings of the 33rd Chinese control conference. IEEE, Nanjing, pp 7595–7600. https://doi.org/10.1109/chicc.2014.6896265

Zhen L, Lee LH, Chew EP (2011) A decision model for berth allocation under uncertainty. Eur J Oper Res 212:54–68. https://doi.org/10.1016/j.ejor.2011.01.021

Zheng Y (2015) Trajectory data mining: an overview. ACM Trans Intell Syst Technol 6:1–41. https://doi.org/10.1145/2743025

Thông tin
Thông tin xuất bản

Flexible Services and Manufacturing Journal

Tập 35

29-69

Thông tin tác giả