DOI: https://doi.org/10.15588/1607-3274-2020-2-3

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

O. V. Borovyk, R. V. Rachok, L. V. Borovyk, I. O. Basaraba

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.


Keywords


Complexity, optimization problem, graph, non-stationarity, method.

Full Text:

PDF

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.


GOST Style Citations


1. Математична модель задачі формування складу транспортної колони прикордонної комендатури швидкого реагування та її програмно-алгоритмічна реалізація / [О. В. Боровик, Р. В. Рачок, Л. В. Боровик, В. В. Купельський] // Збірник наукових праць Військового інституту Ки-
ївського національного університету імені Тараса Шевченка. – 2017. – № 55. – С. 17–30.

2. Вайнер А. Я. Тактические расчеты / А. Я. Вайнер. – М. : Воениздат, 1982. – 176 с.

3. Чорний М. В. Прогнозування ефективності маршу військового формування за надійністю зразків озброєння та військової техніки аналітичним моделюванням / М. В.Чорний, С. С. Степанов // Військово-технічний збірник АСВУ. – 2014. – № 2(14). – С. 64–69.

4. Матвейчук Т. А. Моделювання та програмна реалізація процесу планування вантажоперевезень у військовій логістиці / Т. А. Матвейчук // Військово-технічний збірник АСВУ. – 2016. – № 14. – С. 18–25.

5. Fast point-to-point shortest path computations with arc-flags / [M. Hilger, E. Kohler, R. Mohring et. аl.] // Discrete Mathematics and Theoretical Computer Science. – 2009. – Vol. 74. – Р. 41–72.

6. Antsfeld L. Finding Multi-criteria Optimal Paths in Multimodal Public Transportation Networks using the Transit Algorithm / L. Antsfeld, T. Walsh // Artificial Intelligence and Logistics AILog 2012 Workshop Proceedings. – 2012. – №1. – Р. 7–11.

7. Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks / [R. Geisberger, P. Sanders, D. Schultes et. al] // Experimental Algorithms. – 2008. – Vol. 5038. – Р. 319–333.

8. Delling D. Time-dependent SHARC-routing / D. Delling // Springer International Publishing AG. – 2011. – Vol. 60. – Р. 60–94.

9. Route Planning in Transportation Networks / [H. Bast, D. Delling, A. Goldberg et. al] // Springer International Publishing
AG. – 2016. – Vol. 9220. – Р. 19–80.

10. Resilience and efficiency in transportation networks / [A. Ganin, M. Kitsak, D. Marchese et. al] // Science Advances. – 2017. – № 3. – Р. 1–8.

11. 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. – Р. 1–10.

12. Кузькін О. Ф. Пошук шляхів у маршрутних мережах міст методом відгалужень і меж / О. Ф. Кузькін // Комунальне господарство міст. – 2012. – №103. – С. 378–388.

13. Василенко О. В. Геоінформаційні системи керування для завдань навігаційного забезпечення військ / О. В. Василенко, Д. П. Кучеров, О. О. Зацарицин // Геоінформаційні системи у військових задачах: Другий науково-технічний семінар, 21–22 січня 2011р.: Львів, 2011. – С. 5.

14. Петлюк І. В. ГІС-технології у військовій справі / І. В. Петлюк, С. Г. Власенко, О. І. Петлюк // Геоінформаційні системи та інформаційні технології у військових і спеціальних задачах, «Січневі ГІСи»: Третій науковопрактичний семінар, Львів, 2012. – С. 40.

15. Perencsik A. ArcGIS: Building a Geodatabase / A. Perencsik, S. Woo, B. Booth. – Redlands: ESRI Press, 2014. – 355 p.

16. ArcGIS Resource Center / ESRI. [Електронний ресурс]. – Режим доступу: http://doc.arcgis.com/ru/arcgis-online.

17. Лейс Т. Г. ArcGIS. ArcMap. Руководство пользователя / Т. Г. Лейс. – М. : МГУ, 2005. – 558 с.

18. Методика вибору оптимального маршруту руху колони техніки по нестаціонарній мережі доріг / [О. В. Боровик,
Р. В. Рачок, Л. В. Боровик, В. В. Купельський] // Радіоелектроніка, інформатика, управління. – 2019. – № 4(51). – С. 17–30.

19. Сплайн-функції та їх застосування / [Б. П. Довгий, А. В. Ловейкін, Є. С. Вакал та ін.]; під ред. Б. П. Довгого. – К. : Видавничо-поліграфічний центр «Київський університет», 2016. – 117 с.

20. Интерполяция неизвестных функций кубическими сплайнами / [И. Ю. Алешин, А. В. Сычева, Д. К. Агишева, Т. А. Матвеева] // Современные наукоемкие технологии. – 2014. – № 5–2. – С. 188–189.

21. Першина Ю. І. Наближення розривних функцій розривними сплайнами методом мінімакса / Ю. І. Першина, В. О. Пасічник // Вісник ХНТУ. – 2018. – № 3(66). – С. 82–87.

22. Боровик О. В. Методика оцінки ефективності військових перевезень колоною техніки / О. В. Боровик, В. В. Купельський // Системи озброєння і військова техніка. – 2019. – № 3(59). – С. 25–35.







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

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.