DOI: https://doi.org/10.15588/1607-3274-2019-4-11

THE METHOD OF SELECTION OF THE OPTIMAL ROUTE OF MOVEMENT OF COLUMNS OF VEHICLES UNDER NON-STATIONARY ROAD NETWORK

O. V. Borovyk, R. V. Rachok, L. V. Borovyk, V. V. Kupelsky

Abstract


Context. Effective solution of a large number of applications requires optimal transportation. Construction of optimal routes on
a static in time graph describing a network of roads is a classic and detailed study of tasks. However, in many applications, there is a
need to take into account the possible dynamics of the change in time of road conditions, which requires the development of the
appropriate scientific and methodical apparatus.
Objective. The purpose of the work is to develop a methodology for choosing the optimal route of movement of the equipment
column on a non-stationary road network.
Method. In the paper a mathematical model of the choice of the optimal route of the movement of the vehicles column along the
network is proposed. A graph is used to describe the network of roads. The criterion of optimality when choosing a route is to
minimize the time spent on travel. The peculiarity of the model is to take into account the possibility of dynamically changing the
weight of the edges of the graph when moving the column of technology on the chosen route. Based on the use of this model, a
technique is proposed which ensures the selection of optimal route for discrete-stochastic, discrete-deterministic and continuouslyindefinite
cases of changes in the weight of the edges of the graph.
Results. In the article the algorithms are chosen and the features of their application are shown, which provide solution of the
problem of choosing the optimal route in the conditions of the ribs that are not fixed in time, which describe the network of roads.
The description of the algorithmic and programmatic implementation of the proposed methodology is given. With the use of
developed software, the research model of the road network with a non-stationary weight of the ribs. The example shows the
imperfection of the solutions for optimal route under the non-stationary weight of the edges of the graph obtained using classical
methods.
Conclusions. Failure to take into account the possible change in the road situation, which manifests itself in the change in the
time scale of the edges of the graph, which describes the network of roads, may lead to the non-optimality of the solutions obtained
using the classic methods of finding the shortest route in the graph. To get the best routes, taking into account the change in the time
of the road situation during the movement of the column, it is possible to use the method proposed in this study. The obtained results
extend the possibilities for solving the problems in the field of discrete optimization taking into account the dynamics of the changing
situation in the implementation of optimal solutions.

Keywords


Route Optimization, Graph, Dijkstra’s Method.

References


Hilger M., Kohler E., Mohring R. and Schilling H., Fast pointto-point shortest path computations with arc-flags, DIMACS,

, Vol. 74, pp. 41–72.

Antsfeld L. and Walsh T. Finding Multi-criteria Optimal Paths in Multi-modal Public Transportation Networks using the

Transit Algorithm, Artificial Intelligence and Logistics AILog 2012 Workshop Proceedings, 2012, No. 1, pp. 7–11.

Geisberger R., Sanders P., Schultes D. and Delling D., Contraction Hierarchies: Faster and Simpler Hierarchical

Routing in Road Networks. Springer-Verlag Berlin Heidelberg, 2008, Vol. 5038, pp. 319–333.

Delling D. Time-dependent SHARC-routing, Springer International Publishing AG, 2008, Vol. 60, pp. 60–94.

Bast H., Delling D., Goldberg A., Müller-Hannemann M., Pajor T., Sanders P., Wagner D. and Werneck R. F. Route Planning in

Transportation Networks, Springer International Publishing AG, 2016, Vol. 9220, pp. 19–80.

Ganin A. A., Kitsak M., Marchese D., Keisler J. M., Seager T. and Linkov I. Resilience and efficiency in transportation

networks, Science Advances, 2017, No. 3, pp. 1–8.

Zhao T., Huang J., Shi J. and Chen C. Route Planning for Military Ground Vehicles in Road Networks under Uncertain

Battlefield Environment, Journal of Advanced Transportation Received, 2018, No. 1, pp. 1–10.

Kuz’kin O. F. Poshuk shlyakhiv u marshrutnykh merezhakh mist metodom vidhaluzhen’ i mezh, Communal economy of cities,

, No. 103, pp. 378–388.

Leys T. G., ArcGIS. ArcMap. Rukovodstvo pol’zovatelya. Moscow, MSU, 2005, 558 p.

Crosier S. ArcGIS 9: Getting started with ArcGIS, Redlands, Calif., 2005, 256 p.

ArcGIS 9 ArcMap Rukovodstvo pol’zovatelya, Access mode to the resource: https://www.rulit.me/books/arcgis-9-arcmaprukovodstvo-polzovatelya.

Matveychuk T. A. Modelyuvannya ta prohramna realizatsiya protsesu planuvannya vantazhoperevezen’ u viys’koviy

lohistytsi, Military-technical collection, 2016, No. 14, pp. 18–25.

Borovik, O.V., Rachok, R.V., Borovik, L.V. and Kupelskiy V. V. The mathematical model of the problem of formation of the

convoy of frontier commandant rapid response and its softwarealgorithmic implementation, Military-technical collection,

, No. 55, pp. 17–30.

Borovik O. V. and Kupelskiy V. V., Rozmichennya hrafa merezhi dorih pry rozv’yazuvanni zadachi vyboru

optymal’noho marshrutu rukhu kolony tekhniky prykordonnoyi komendatury shvydkoho reahuvannya, Military-technical

collection, 2018, No. 76, pp. 244–255.


GOST Style Citations


1. Fast point-to-point shortest path computations with arc-flags / [M. Hilger, E. Kohler, R. H. Mohring, H. Schilling] // The
Shortest Path Problem. – Rhode Island: American Society, 2009. – (DIMACS). – (Discrete Mathematics and Theoretical
Computer Science; Vol. 74). – P. 41–72.
2. Antsfeld L. Finding Multi-criteria Optimal Paths in Multi-modal Public Transportation Networks using the Transit Algorithm /
L. Antsfeld, T. Walsh // Artificial Intelligence and Logistics AILog 2012 Workshop Proceedings. – 2012. – №1. – P. 7–11.
3. Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks / [R. Geisberger, P. Sanders, D. Schultes
et al.] // Experimental Algorithms. – Berlin : Springer-Verlag Berlin Heidelberg, 2008. – (Springer-Verlag Berlin Heidelberg).
– (Theoretical informatics and general questions; vol. 5038). – P. 319–333.
4. Delling D. Time-dependent SHARC-routing / Daniel Delling // Algorithmica. – Cham: Springer International Publishing AG,
2011. – (Springer-Verlag). – (Special Issue: European Symposium on Algorithms; Vol. 60). – P. 60–94.
5. Route Planning in Transportation Networks / [H. Bast, D. Delling, A. Goldberg et al.] // Algorithm Engineering. –
Cham: Springer International Publishing AG, 2016. – (Springer Nature). – (Theoretical informatics and general questions; Vol.
9220). – P. 19–80.
6. Resilience and efficiency in transportation networks / [A. A. Ganin, M. Kitsak, D. Marchese et al.]. // Science Advances.
– 2017. – №3. – P. 1–8.
7. Route Planning for Military Ground Vehicles in Road Networks under Uncertain Battlefield Environment / [T. Zhao, J. Huang,
J. Shi et al.]. // Journal of Advanced Transportation Received. – 2018. – №1. – pp. 1–10.
8. Кузькін О. Ф. Пошук шляхів у маршрутних мережах міст методом відгалужень і меж / О. Ф. Кузькін // Комунальне
господарство міст. – 2012. – № 103. – С. 378–388.
9. Лейс Т. Г. ArcGIS. ArcMap. Руководство пользователя / Т. Г. Лейс. – М. : МГУ, 2005. – 558 с.
10. Crosier S. ArcGIS 9: Getting started with ArcGIS / Scott Crosier. – Redlands, Calif.: ESRI, 2004. – 256 с. – (ESRI).
11. ArcGIS 9 ArcMap Руководство пользователя [Електронний ресурс] // ESRI. – 2004. – Режим доступу до ресурсу:
https://www.rulit.me/books/arcgis-9-arcmap-rukovodstvopolzovatelya.
12. Матвейчук Т. А. Моделювання та програмна реалізація процесу планування вантажоперевезень у військовій
логістиці / Т. А. Матвейчук // Військово-технічний збірник АСВУ. – 2016. – № 14. – С. 18–25.
13. Математична модель задачі формування складу транспортної колони прикордонної комендатури швидкого
реагування та її програмно-алгоритмічна реалізація / О. В. Боровик, Л. В. Рачок, Л. В. Боровик,
В. В. Купельський. // Збірник наукових праць ВІКНУ. – 2017. – № 55. – С. 17–30.
14. Боровик О. В. Розмічення графа мережі доріг при розв’язуванні задачі вибору оптимального маршруту руху
колони техніки прикордонної комендатури швидкого реагування / О. В. Боровик, В. В. Купельський. // Збірник
наукових праць НАДПСУ. – 2018. – № 76. – С. 244–255.






Copyright (c) 2020 O. V. Borovyk, R. V. Rachok, L. V. Borovyk, V. V. Kupelsky

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Address of the journal editorial office:
Editorial office of the journal «Radio Electronics, Computer Science, Control»,
National University "Zaporizhzhia Polytechnic", 
Zhukovskogo street, 64, Zaporizhzhia, 69063, Ukraine. 
Telephone: +38-061-769-82-96 – the Editing and Publishing Department.
E-mail: rvv@zntu.edu.ua

The reference to the journal is obligatory in the cases of complete or partial use of its materials.