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

Authors

  • O. V. Borovyk National Academy of State Border Guard Service of Ukraine Named After Bohdan Khmelnitsky, Khmelnitsky, Ukraine
  • R. V. Rachok National Academy of State Border Guard Service of Ukraine Named After Bohdan Khmelnitsky, Khmelnitsky, Ukraine
  • L. V. Borovyk National Academy of State Border Guard Service of Ukraine Named After Bohdan Khmelnitsky, Khmelnitsky, Ukraine
  • V. V. Kupelsky National Academy of State Border Guard Service of Ukraine Named After Bohdan Khmelnitsky, Khmelnitsky, Ukraine

DOI:

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

Keywords:

Route Optimization, Graph, Dijkstra’s Method.

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.

Author Biographies

O. V. Borovyk, National Academy of State Border Guard Service of Ukraine Named After Bohdan Khmelnitsky, Khmelnitsky

Dr. Sc., Deputy Rector of the Academy of Educational Work

R. V. Rachok, National Academy of State Border Guard Service of Ukraine Named After Bohdan Khmelnitsky, Khmelnitsky

Dr. Sc., Associate Professor, Chief of the Department of General Scientific and Engineering Disciplines

L. V. Borovyk, National Academy of State Border Guard Service of Ukraine Named After Bohdan Khmelnitsky, Khmelnitsky

Dr. Sc., Associate Professor, Professor of the Department of General Scientific and Engineering Disciplines

V. V. Kupelsky, National Academy of State Border Guard Service of Ukraine Named After Bohdan Khmelnitsky, Khmelnitsky

Adjunct

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.

Published

2019-11-25

How to Cite

Borovyk, O. V., Rachok, R. V., Borovyk, L. V., & Kupelsky, V. V. (2019). THE METHOD OF SELECTION OF THE OPTIMAL ROUTE OF MOVEMENT OF COLUMNS OF VEHICLES UNDER NON-STATIONARY ROAD NETWORK. Radio Electronics, Computer Science, Control, (4), 111–120. https://doi.org/10.15588/1607-3274-2019-4-11

Issue

Section

Progressive information technologies