THE METHOD OF SELECTION OF THE OPTIMAL ROUTE OF MOVEMENT OF COLUMNS OF VEHICLES UNDER NON-STATIONARY ROAD NETWORK
DOI:
https://doi.org/10.15588/1607-3274-2019-4-11Keywords:
Route Optimization, Graph, Dijkstra’s Method.Abstract
Context. Effective solution of a large number of applications requires optimal transportation. Construction of optimal routes ona 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.
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.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2020 O. V. Borovyk, R. V. Rachok, L. V. Borovyk, V. V. Kupelsky
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Creative Commons Licensing Notifications in the Copyright Notices
The journal allows the authors to hold the copyright without restrictions and to retain publishing rights without restrictions.
The journal allows readers to read, download, copy, distribute, print, search, or link to the full texts of its articles.
The journal allows to reuse and remixing of its content, in accordance with a Creative Commons license СС BY -SA.
Authors who publish with this journal agree to the following terms:
-
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License CC BY-SA that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
-
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
-
Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
