Icebreaker Planning Under Dynamic Ice Conditions
DOI:
https://doi.org/10.32603/2071-2340-2025-4-49-60Keywords:
graph optimization, vehicle routing problem, ice navigation, heuristic algorithmsAbstract
This paper addresses the problem of optimal joint routing of ship convoys escorted by icebreakers under time-varying ice conditions. We propose a mathematical model that reduces the problem to discrete optimization on a temporal graph with edge weights dependent on ice coverage. A specialized two-level heuristic algorithm is developed, combining graph-based route search with greedy convoy formation scheduling. Experimental evaluation on real-world data demonstrates the method's ability to generate feasible solutions in near real-time while significantly reducing total vessel delivery time.
References
P. Toth and D. Vigo, Eds., The Vehicle Routing Problem, Philadelphia, PA, USA: SIAM, 2002.
A. G. Topaj, O. V. Tarovik, A. A. Bakharev, and A. A. Kondratenko, “Optimal ice routing of a ship with icebreaker assistance,” Appl. Ocean Res., vol. 86, pp. 177–187, 2019, doi: 10.1016/j.apor.2019.02.021.
C. E. Cortés, M. Matamala, and C. Contardo, “The pickup and delivery problem with transfers: Formulation and a branch-and-cut solution method,” Eur. J. Oper. Res., vol. 200, no. 3, pp. 711–724, 2010, doi: 10.1016/j.ejor.2009.01.022.
T. Y. Ma, S. Rasulkhani, J. Y. J. Chow, and S. H. Chung, “A dynamic ridesharing dispatch and idle vehicle repositioning strategy with integrated transit transfers,” Transportation Research Part E: Logistics and Transportation Review, vol. 128, pp. 417–442, 2019, doi: 10.1016/j.tre.2019.07.002.
S. Arutyunyan and M. Subbotin, Web service source code. (Jun. 2024). GitHub. [Online]. Available: https://github.com/sttie/ldt-rosatom/
Published
Issue
Section
License
Copyright (c) 2026 Aleksandr Kodukov, Samvel Arutyunyan, Maksim Subbotin
This work is licensed under a Creative Commons Attribution 4.0 International License.
This work is licensed under a Creative Commons Attribution 4.0 International License.
