Abstract
Container Relocation Problem (CRP) is one of the most important and fundamental problems in the terminal’s operations. Given a specified layout of the container yard with all the container retrieval priorities, CRP aims to identify an ideal container movement sequence so as to minimize the total number of container rehandling operations. In this paper, we are the first to propose a deep reinforcement learning method to tackle the problem. It adopts a dynamic attention model to respond to the changes of the layout. The long short-term memory and multi-head attention layers are introduced to better extract the features of stacks. We use a policy gradient algorithm with rollout baseline to train the model. The experiments demonstrate that our method can solve the problem effectively compared with other classic approaches. We conclude that the deep reinforcement learning approach has a great potential in solving CRP, as it can find desirable solution without using much expert domain knowledge.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Bacci, T., Mattia, S., Ventura, P.: A branch-and-cut algorithm for the restricted block relocation problem. Eur. J. Oper. Res. 287(2), 452–459 (2020)
Bello, I., Pham, H., Le, Q.V., Norouzi, M., Bengio, S.: Neural combinatorial optimization with reinforcement learning (2017)
Caserta, M., Schwarze, S., Voß, S.: A mathematical formulation and complexity considerations for the blocks relocation problem. Eur. J. Oper. Res. 219(1), 96–104 (2012)
Caserta, M., Voß, S., Sniedovich, M.: Applying the corridor method to a blocks relocation problem. OR Spectrum 33(4), 915–929 (2011)
Expósito-Izquierdo, C., Melián-Batista, B., Moreno-Vega, J.M.: A domain-specific knowledge-based heuristic for the blocks relocation problem. Adv. Eng. Inf. 28(4), 327–343 (2014)
Expósito-Izquierdo, C., Melián-Batista, B., Moreno-Vega, J.M.: An exact approach for the blocks relocation problem. Expert Syst. Appl. 42(17), 6408–6422 (2015). https://doi.org/10.1016/j.eswa.2015.04.021. https://www.sciencedirect.com/science/article/pii/S0957417415002511
Galle, V., Barnhart, C., Jaillet, P.: A new binary formulation of the restricted container relocation problem based on a binary encoding of configurations. Eur. J. Oper. Res. 267(2), 467–477 (2018)
Jin, B., Tanaka, S.: An exact algorithm for the unrestricted container relocation problem with new lower bounds and dominance rules. Eur. J. Oper. Res. 304(2), 494–514 (2022)
Jovanovic, R., Tuba, M., Voß, S.: An efficient ant colony optimization algorithm for the blocks relocation problem. Eur. J. Oper. Res. 274(1), 78–90 (2019)
Kim, K.H., Hong, G.P.: A heuristic rule for relocating blocks. Comput. Oper. Res. 33(4), 940–954 (2006)
Kingma, D.P., Ba, J.: Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 (2014)
Kool, W., van Hoof, H., Welling, M.: Attention, learn to solve routing problems! In: International Conference on Learning Representations (2018)
Ku, D., Arthanari, T.S.: On the abstraction method for the container relocation problem. Comput. Oper. Res. 68, 110–122 (2016)
Li, K., Zhang, T., Wang, R., Wang, Y., Han, Y., Wang, L.: Deep reinforcement learning for combinatorial optimization: covering salesman problems. IEEE Trans. Cybern. 52(12), 13142–13155 (2021)
Lu, C., Zeng, B., Liu, S.: A study on the block relocation problem: lower bound derivations and strong formulations. IEEE Trans. Autom. Sci. Eng. 17(4), 1829–1853 (2020)
Peng, B., Wang, J., Zhang, Z.: A deep reinforcement learning algorithm using dynamic attention model for vehicle routing problems. In: Li, K., Li, W., Wang, H., Liu, Y. (eds.) ISICA 2019. CCIS, vol. 1205, pp. 636–650. Springer, Singapore (2020). https://doi.org/10.1007/978-981-15-5577-0_51
Quispe, K.E.Y., Lintzmayer, C.N., Xavier, E.C.: An exact algorithm for the blocks relocation problem with new lower bounds. Comput. Oper. Res. 99, 206–217 (2018)
da Silva, M.D.M., Toulouse, S., Calvo, R.W.: A new effective unified model for solving the pre-marshalling and block relocation problems. Eur. J. Oper. Res. 271(1), 40–56 (2018)
Silver, D., et al.: Mastering the game of go with deep neural networks and tree search. Nature 529(7587), 484–489 (2016)
Tanaka, S., Mizuno, F.: An exact algorithm for the unrestricted block relocation problem. Comput. Oper. Res. 95, 12–31 (2018)
Tanaka, S., Takii, K.: A faster branch-and-bound algorithm for the block relocation problem. IEEE Trans. Autom. Sci. Eng. 1(13), 181–190 (2016)
Tanaka, S., Voß, S.: An exact approach to the restricted block relocation problem based on a new integer programming formulation. Eur. J. Oper. Res. 296(2), 485–503 (2022)
Tricoire, F., Scagnetti, J., Beham, A.: New insights on the block relocation problem. Comput. Oper. Res. 89, 127–139 (2018)
Vaswani, A., et al.: Attention is all you need. In: Advances in Neural Information Processing Systems, vol. 30 (2017)
Zehendner, E., Caserta, M., Feillet, D., Schwarze, S., Voß, S.: An improved mathematical formulation for the blocks relocation problem. Eur. J. Oper. Res. 245(2), 415–422 (2015)
Zehendner, E., Feillet, D.: A branch and price approach for the container relocation problem. Int. J. Prod. Res. 52(24), 7159–7176 (2014)
Zhang, C., Guan, H., Yuan, Y., Chen, W., Wu, T.: Machine learning-driven algorithms for the container relocation problem. Trans. Res. Part B: Methodol. 139, 102–131 (2020)
Zhu, W., Qin, H., Lim, A., Zhang, H.: Iterative deepening a* algorithms for the container relocation problem. IEEE Trans. Autom. Sci. Eng. 9(4), 710–722 (2012)
Acknowledgements
This work is supported by the Natural Science Foundation of Guangdong Province (No. 2019A1515011169, 2021A1515011301).
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
Liu, F., Ye, T., Zhang, Z. (2023). Dynamic Attention Model – A Deep Reinforcement Learning Approach for Container Relocation Problem. In: Fujita, H., Wang, Y., Xiao, Y., Moonis, A. (eds) Advances and Trends in Artificial Intelligence. Theory and Applications. IEA/AIE 2023. Lecture Notes in Computer Science(), vol 13926. Springer, Cham. https://doi.org/10.1007/978-3-031-36822-6_24
Download citation
DOI: https://doi.org/10.1007/978-3-031-36822-6_24
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-36821-9
Online ISBN: 978-3-031-36822-6
eBook Packages: Computer ScienceComputer Science (R0)