METHOD OF SOLUTION OF COMPLEX OPTIMIZATION PROBLEM FOR FORMATION OF COMPONENT COLUMN OF TECHNIQUE AND ROUTE SELECTION OF ITS MOVEMENT BY NON-STATIONARY ROAD NETWORK
DOI:
https://doi.org/10.15588/1607-3274-2020-2-3Keywords:
Complexity, optimization problem, graph, non-stationarity, method.Abstract
Context. Effective solution of a number of application problems related to transportation, as a rule, depends on the solution of two problems: the correct formation of the composition of the column of technique and the successful choice of the route of its movement. Each of the problems is optimization, the methods of solving which are currently being worked out. Theoretical studies of each of the individual problems and their practical applications indicate their interdependence, which has not yet been fully studied. Practical applications necessitate the development of a suitable scientific and methodological apparatus.
Objective. The purpose of this work is development of a method for solving a complex optimization problem of forming a column of vehicles and choosing the route of its movement on a non-stationary road network.
Method. The mathematical model of solving the optimization problem of complex formation of the composition of the column of machinery and the choice of its route of motion is proposed. A heterogeneous set was used to describe the array from which the vehicles were selected. A graph was used to describe the road network. As a criterion for the optimality of the complex problem is the minimization of time spent on moving. The peculiarity of the model is to take into account the possibility of dynamically changing the time weights of edges of the graph when implementing the movement of a column of machinery along the chosen route. Based on the use of this model, a method is proposed, which provides a comprehensive choice of the composition of the column of equipment and optimal routes of its movement on a non-stationary road network.
Results. The article proposes an algorithm that provides the solution of the optimization problem of complex formation of the composition of machinery column and the choice of its route of motion in terms of time-fixed edges that describe the network of roads. The features of application of the proposed algorithm are given. Using the developed software, the choice of technique from an existing inhomogeneous array and the choice of a route on a graph with a non-stationary time weight of edges was investigated. The example shows the imperfection of decisions regarding the complex formation of the column composition and the choice of its optimal route of travel on a non-stationary network of roads obtained using classical methods.
Conclusions. Not taking into account the impact of a possible change in traffic conditions, as evidenced by a change in the time weights of the edges of the graph describing the road network, on the composition of the column of machinery can lead to suboptimality of the obtained solutions using classical methods of forming the composition of the column and finding the shortest route in the graph. The method proposed in this study can be used to obtain the optimum composition of the column and the route, taking into account the change in road conditions during the movement of the column. The obtained results extend the possibilities of the theory of discrete optimization and the theory of graphs.
References
Borovik O. V., Rachok R. V., Borovik L. V., Kupel’s’kij V. V. Matematichna model’ zadachі formuvannja skladu transportnoї koloni prikordonnoї komendaturi shvidkogo reaguvannja ta її programnoalgoritmіchna realіzacіja, Zbіrnik naukovih prac’ Vіjs’kovogo іnstitutu Kiїvs’kogo nacіonal’nogo unіversitetu іmenі Tarasa Shevchenka, 2017, No. 55, pp. 17–30.
Vajner A. Ja. Takticheskie raschjoty. Moscow, Voenizdat, 1982, 176 p.
Chornij M. V., Stepanov S. S. Prognozuvannja efektivnostі marshu vіjs’kovogo formuvannja za nadіjnіstju zrazkіv ozbroєnnja ta vіjs’kovoї tehnіki analіtichnim modeljuvannjam, Vіjs’kovo-tehnіchnij zbіrnik ASVU, 2014. No. 2(14), pp. 64–69.
Matvejchuk T. A. Modeljuvannja ta programna realіzacіja procesu planuvannja vantazhoperevezen’ u vіjs’kovіj logіsticі, Vіjs’kovo-tehnіchnij zbіrnik ASVU, 2016, No. 14, pp. 18–25.
Hilger M., Kohler E., Mohring R. et. al Fast point-to-point shortest path computations with arc-flags, Discrete Mathematics and Theoretical Computer Science, 2009, Vol. 74, – pp. 41–72.
Antsfeld L., 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. et. аl. Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks, Experimental Algorithms, 2008, Vol. 5038, pp. 319–333.
Delling D. Time-dependent SHARC-routing, Springer International Publishing AG, 2011, Vol. 60, pp. 60–94.
H. Bast, D. Delling, A. Goldberg et. al. Route Planning in Transportation Networks, Springer International Publishing AG, 2016, Vol. 9220, pp. 19–80.
Ganin A., Kitsak M., Marchese D. et. al. Resilience and efficiency in transportation networks, Science Advances, 2017, No. 3, pp. 1–8.
Zhao T., Huang J., Shi J. et. al. 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’kіn O. F. Poshuk shljahіv u marshrutnih merezhah mіst metodom vіdgaluzhen’ і mezh, Komunal’ne gospodarstvo mіst, 2012, No.103, pp. 378–388.
Vasilenko O. V., Kucherov D. P., Zacaricin O. O. Geoіnformacіjnі sistemi keruvannja dlja zavdan’ navіgacіjnogo zabezpechennja vіjs’k, Geoіnformacіjnі sistemi u vіjs’kovih zadachah: Drugij naukovo-tehnіchnij semіnar, 21–22 sіchnja 2011r. L’vіv, 2011, P. 5.
Petljuk І. V., Vlasenko S. G., Petljuk O. І. GІS-tehnologії u vіjs’kovіj spravі, Geoіnformacіjnі sistemi ta іnformacіjnі tehnologії u vіjs’kovih і specіal’nih zadachah, «Sіchnevі GІSi»: Tretіj naukovo-praktichnij semіnar. L’vіv, 2012, pp. 40.
Perencsik A., Woo S., Booth B. ArcGIS: Building a Geodatabase. Redlands, ESRI Press, 2014, 355 p.
ArcGIS Resource Center / ESRI. [Elektronnij resurs]. Rezhim dostupu.: http://doc.arcgis.com/ru/arcgis-online.
Lejs T. G. ArcGIS. ArcMap. Rukovodstvo pol’zovatelja. Moscow, MGU, 2005, 558 p.
Borovik O. V., Rachok R. V., Borovik L. V., Kupel’s’kij V. V. Metodika viboru optimal’nogo marshrutu ruhu koloni tehnіki po nestacіonarnіj merezhі dorіg, Radio Electronics, Computer Science, Control, 2019, No. 4(51), pp. 17–30.
Dovgij B. P., Lovejkіn A. V., Vakal Є. S. ta іn.; pіd red. B. P. Dovgogo Splajn-funkcії ta їh zastosuvannja. Kiїv, Vidavnicho-polіgrafіchnij centr “Kiїvs’kij unіversitet”, 2016, 117 p.
Aleshin I. Ju., Sycheva A. V., Agisheva D. K., Matveeva T. A. Interpoljacija neizvestnyh funkcij kubicheskimi splajnami, Sovremennye naukoemkie
tehnologii, 2014, No. 5–2, pp. 188–189.
Pershina Ju. І., Pasіchnik V. O. Nablizhennja rozrivnih funkcіj rozrivnimi splajnami metodom mіnіmaksa, Vіsnik HNTU, 2018, No. 3(66), pp. 82–87.
Borovik O. V., Kupel’s’kij V. V Metodika ocіnki efektivnostі vіjs’kovih perevezen’ kolonoju tehnіki, Sistemi ozbroєnnja і vіjs’kova tehnіka, 2019, No. 3(59), pp. 25–35.
Downloads
How to Cite
Issue
Section
License
Copyright (c) 2020 O. V. Borovyk, R. V. Rachok, L. V. Borovyk, I. O. Basaraba
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.
