Abstract
Major liner shipping companies aim to solve the stowage planning problem by optimally allocating containers to vessel locations during a multi-port voyage. Due to a large variety of combinatorial aspects, a scalable algorithm to solve a representative problem is yet to be found. This paper will show that deep reinforcement learning can optimize a non-trivial master bay planning problem. Our experiments show that proximal policy optimization efficiently finds reasonable solutions, serving as preliminary evidence of the potential value of deep reinforcement learning in stowage planning. In future work, we will extend our architecture to address a full-featured master bay planning problem.
This work is partially sponsored by the Danish Maritime Fund under grant 2021-069.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Akiba, T., Sano, S., Yanase, T., Ohta, T., Koyama, M.: Optuna: a next-generation hyperparameter optimization framework (2019). http://arxiv.org/abs/1907.10902
Ambrosino, D., Anghinolfi, D., Paolucci, M., Sciomachen, A.: An experimental comparison of different heuristics for the master bay plan problem. In: Festa, P. (ed.) SEA 2010. LNCS, vol. 6049, pp. 314–325. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13193-6_27
Ambrosino, D., Sciomachen, A., Tanfani, E.: Stowing a containership: the master bay plan problem. Transp. Res. Part A 38(2), 81–99 (2004). https://doi.org/10.1016/j.tra.2003.09.002, http://linkinghub.elsevier.com/retrieve/pii/S0965856403000892, http://www.sciencedirect.com/science/article/pii/S0965856403000892
Avriel, M., Penn, M., Shpirer, N., Witteboon, S.: Stowage planning for container ships to reduce the number of shifts. Ann. Oper. Res. 76(1-4), 55–71 (1998). http://search.ebscohost.com/login.aspx?direct=true &db=bth &AN=18925445 &site=ehost-live, http://link.springer.com/article/10.1023/A:1018956823693
Azevedo, A., Cassilda Maria, R., de Sena, G.J., Chaves, A.A., Neto, L.L.S., Moretti, A.C.: Solving the 3D container ship loading planning problem by representation by rules and meta-heuristics. Int. J. Data Anal. Tech. Strategies 6(3), 228–260 (2014). https://doi.org/10.1504/IJDATS.2014.063060
Bergstra, J., Bardenet, R., Bengio, Y., Kégl, B.: Algorithms for hyper-parameter optimization. In: NIPS 2011: Proceedings of the 24th International Conference on Neural Information Processing Systems, pp. 2546–2554 (2011). https://proceedings.neurips.cc/paper_files/paper/2011/file/86e8f7ab32cfd12577bc2619bc635690-Paper.pdf
Bilican, M.S., Evren, R., Karatas, M.: A mathematical model and two-stage heuristic for the container stowage planning problem with stability parameters. IEEE Access 8, 113392–113413 (2020). https://doi.org/10.1109/ACCESS.2020.3003557
Botter, R., Brinati, M.: Stowage container planning: a model for getting an optimal solution. Comput. Appl. Autom. Shipyard Oper. Ship Design VII(C), 217–228 (1992)
Chao, S.L., Lin, P.H.: Minimizing overstowage in master bay plans of large container ships. Maritime Econ. Logist. 23(1), 71–93 (2021). https://doi.org/10.1057/s41278-019-00126-6
Delgado, A., Jensen, R.M., Guilbert, N.: A placement heuristic for a commercial decision support system for container vessel stowage. In: 38th Latin America Conference on Informatics, CLEI 2012 - Conference Proceedings (2012). https://doi.org/10.1109/CLEI.2012.6427181
Ding, D., Chou, M.C.: Stowage planning for container ships: a heuristic algorithm to reduce the number of shifts. Eur. J. Oper. Res. (2015). https://doi.org/10.1016/j.ejor.2015.03.044, http://linkinghub.elsevier.com/retrieve/pii/S0377221715002660
Dubrovsky, O., Levitin, G., Penn, M.: A genetic algorithm with a compact solution encoding for the container ship stowage problem. J. Heuristics 8(6), 585–599 (2002). https://doi.org/10.1023/A:1020373709350, http://link.springer.com/article/10.1023/A:1020373709350
Engstrom, L., et al.: Implementation matters in deep policy gradients: a case study on PPO and TRPO (2020). http://arxiv.org/abs/2005.12729
Foa, S., Coppola, C., Grani, G., Palagi, L.: Solving the vehicle routing problem with deep reinforcement learning (2022). http://arxiv.org/abs/2208.00202
Goodfellow, I., Bengio, Y., Courville, A.: Deep Learning. MIT Press (2016). http://www.deeplearningbook.org
Hamedi, M.: Containership load planning with crane operations. Ph.D. thesis, University of Maryland (2011)
Hottung, A., Kwon, Y.D., Tierney, K.: Efficient active search for combinatorial optimization problems. In: International Conference on Learning Representations 2022 (2021). http://arxiv.org/abs/2106.05126
Jensen, R.M., Pacino, D., Ajspur, M.L., Vesterdal, C.: Container vessel stowage planning. Weilbach (2018)
Kebedow, K.G., Oppen, J.: Including containers with dangerous goods in the slot planning problem. In: 2019 Proceedings of the International Conference on Industrial Engineering and Operations Management, pp. 225–232 (2019)
Kingma, D.P., Ba, J.: Adam: a method for stochastic optimization. In: 2015 International Conference on Learning Representations (2014). http://arxiv.org/abs/1412.6980
Korach, A., Brouer, B.D., Jensen, R.M.: Matheuristics for slot planning of container vessel bays. Eur. J. Oper. Res. 282(3), 873–885 (2020). https://doi.org/10.1016/j.ejor.2019.09.042
Kwon, Y.D., Choo, J., Kim, B., Yoon, I., Gwon, Y., Min, S.: POMO: policy optimization with multiple optima for reinforcement learning (2020). https://doi.org/10.48550/ARXIV.2010.16011, https://arxiv.org/abs/2010.16011
Larsen, R., Pacino, D.: A heuristic and a benchmark for the stowage planning problem. Maritime Econ. Logist. 23(1), 94–122 (2021). https://doi.org/10.1057/s41278-020-00172-5
Mirhoseini, A., et al.: A graph placement methodology for fast chip design. Nature 594(7862), 207–212 (2021). https://doi.org/10.1038/s41586-021-03544-w
Mnih, V., et al.: Playing Atari with Deep Reinforcement Learning (2013)
Pacino, D.: An LNS approach for container stowage multi-port master planning. In: Computational Logistics, pp. 35–44 (2013). https://doi.org/10.1007/978-3-642-41019-2_3, http://link.springer.com/10.1007/978-3-642-41019-2_3
Pacino, D.: Crane intensity and block stowage strategies in stowage planning. In: Cerulli, R., Raiconi, A., Voß, S. (eds.) ICCL 2018. LNCS, vol. 11184, pp. 191–206. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-00898-7_12
Pacino, D., Delgado, A., Jensen, R.M., Bebbington, T.: Fast generation of near-optimal plans for eco-efficient stowage of large container vessels. In: Böse, J.W., Hu, H., Jahn, C., Shi, X., Stahlbock, R., Voß, S. (eds.) ICCL 2011. LNCS, vol. 6971, pp. 286–301. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-24264-9_22
Pacino, D., Jensen, R.M.: A 3-phase randomized constraint based local search algorithm for stowing under deck locations of container vessel bays (2010). https://en.itu.dk/-/media/EN/Research/About-ITU-Research/Technical-Reports/2010/ITU-TR-2010-123-pdf
Parreño-Torres, C., Çalık, H., Alvarez-Valdes, R., Ruiz, R.: Solving the generalized multi-port container stowage planning problem by a matheuristic algorithm. Comput. Oper. Res. 133, 105383 (2021). https://doi.org/10.1016/j.cor.2021.105383
Roberti, R., Pacino, D.: A decomposition method for finding optimal container stowage plans. Transp. Sci. 52(6), 1444–1462 (2018). https://doi.org/10.1287/trsc.2017.0795
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., Klimov, O.: Proximal policy optimization algorithms (2017). http://arxiv.org/abs/1707.06347
Shen, Y., Zhao, N., Xia, M., Du, X.: A deep Q-learning network for ship stowage planning problem. Pol. Maritime Res. 24(S3), 102–109 (2017). https://doi.org/10.1515/pomr-2017-0111
Sutton, R.S., Barto, A.G.: Reinforcement Learning: An Introduction. MIT Press, Cambridge (2018)
Tierney, K., Pacino, D., Jensen, R.M.: On the complexity of container stowage planning problems. Discrete Appl. Math. 169, 225–230 (2014). https://doi.org/10.1016/j.dam.2014.01.005, http://dx.doi.org/10.1016/j.dam.2014.01.005
van Twiller, J., Sivertsen, A., Pacino, D., Jensen, R.M.: Literature survey on the container stowage planning problem. Under review (2023)
Wilson, I.D., Roach, P.A.: Container stowage planning: a methodology for generating computerised solutions. J. Oper. Res. Soc. 51(11), 1248–1255 (2000). https://doi.org/10.1057/palgrave.jors.2601022, https://www.tandfonline.com/doi/full/10.1057/palgrave.jors.2601022
Zhao, N., Guo, Y., Xiang, T., Xia, M., Shen, Y., Mi, C.: Container ship stowage based on Monte Carlo tree search. J. Coastal Res. 83, 540–547 (2018). https://doi.org/10.2112/SI83-090.1
Zhu, H., Ji, M., Guo, W.: Integer linear programming models for the containership stowage problem. Math. Probl. Eng. 2020 (2020). https://doi.org/10.1155/2020/4382745
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
van Twiller, J., Grbic, D., Jensen, R.M. (2023). Towards a Deep Reinforcement Learning Model of Master Bay Stowage Planning. In: Daduna, J.R., Liedtke, G., Shi, X., Voß, S. (eds) Computational Logistics. ICCL 2023. Lecture Notes in Computer Science, vol 14239. Springer, Cham. https://doi.org/10.1007/978-3-031-43612-3_6
Download citation
DOI: https://doi.org/10.1007/978-3-031-43612-3_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-43611-6
Online ISBN: 978-3-031-43612-3
eBook Packages: Computer ScienceComputer Science (R0)