Methods for constructing routes outside urban areas based on GPS data
Автор: Krutko D.A., Kalashnikov A.S., Buryachenko V.V.
Журнал: Siberian Aerospace Journal @vestnik-sibsau-en
Рубрика: Informatics, computer technology and management
Статья в выпуске: 2 vol.23, 2022 года.
Бесплатный доступ
Route constructing methods include the task of finding the shortest trajectory between two or more ob-jects, which may vary depending on weather conditions, altitude coordinates, and other parameters. The methods discussed in the article allow constructing routes using GPS tracks for various fields of knowledge: designing routes within a city, region, country, or with remote sensing of the earth. The consid-ered algorithms are used in the field of environmental monitoring in emergency situations, to search for optimal data transmission routes in satellite systems and their validation, as well as in organizational and economic systems. The most widely used approaches for constructing routes are graph theory and search in the state space, where any trajectory between objects is given its own weight. However, there is still no system that allows to make a tourist route over rough terrain. The article discusses such methods as the Dijkstra, Levit, Floyd-Warshell algorithm, and it also compares their effectiveness in terms of running time and complexity. The aim of the work is to develop an algorithm for finding the shortest path and building a tourist route from a given point A to point B. This development will open up new opportunities for citizens to independently visit new interesting areas, actively spend their free time and get to know the surroundings of the city. The system has been tested on the territory of the Torgashinsky ridge, includes more than 38 route points located at a distance of more than 25 kilometers, and allows to build the desired routes within less than 15 milliseconds. At the same time, the system enters person’s coordinates, which are considered when constructing routes.
Shortest path, graph theory, constructing routes, gpx-tracks, Dijkstra’s algorithm
Короткий адрес: https://sciup.org/148329618
IDR: 148329618 | DOI: 10.31772/2712-8970-2022-23-2-168-176
Список литературы Methods for constructing routes outside urban areas based on GPS data
- Krutko D. A. [The problem of automating the construction of hiking route schemes in the moun-tains of the Krasnoyarsk Territory]. Proceedings of the VII International Scientific and Practical Con-ference “Actual Problems of Aviation and Cosmonautics”. Krasnoyarsk, 2021, Vol. 2, P. 260–262 (In Russ.).
- Ivanova K. A., Malikova O. V. [Technology of integrated processing of geospatial data for mon-itoring the consequences of emergency situations]. Regional problems of remote sensing of the Earth: materials of the II Intern. scientific conference. September 22–25, 2015. Krasnoyarsk, Sib. feder. un-t Publ., 2015, P. 62–65 (In Russ.).
- Agafonov A. A., Maksimov A. I., Borodinov A. A. [Study of the efficiency of calculating a reliable shortest path using GPU]. VI International Conference and Youth School “Information Technologies and Nanotechnologies” (ITNT-2020). 2020, P. 1–7 (In Russ.).
- Agafonov A. A., Myasnikov V. V. [A method for determining a reliable shortest path in a stochastic network using parametrically specified stable probability distributions]. SPIIRAN. 2020. Vol. 3, Iss. 18, P. 558–582 (In Russ.).
- Fedorov A. A., Soshilov I. V., Loginov V. N. [Heuristic algorithms for searching for data trans-mission routes in satellite systems and their validation]. Proceedings OF MIPT. 2020, Vol. 12, No. 3, P. 1–9 (In Russ.).
- Ramzaev V. M., Khaimovich I. N., Martynov I. V. [Methods for finding shortest paths on graphs in organizational and economic systems and their implementation]. V International Conference and Youth School “Information Technologies and Nanotechnologies” (ITNT-2019). 2019, P. 1–8 (In Russ.).
- Stytsenko F. V., Saigin I. A., Bartalev S. A. [Study of the possibilities of long-term monitoring of the state of forests damaged by fires based on satellite data]. Information technologies in remote sensing of the Earth. RORSE 2018. IKI RAS, 2019, P. 185–190. Doi: 10.21046/rorse2018.185.
- Miklashevich T. S., Bartalev S. A., Plotnikov D. E. [Interpolation algorithm for restoring long time series of satellite observations of vegetation cover]. Modern problems of remote sensing of the Earth from space. 2019, Vol. 16, P. 1–10 (In Russ.).
- Zhen B., Noon C. Shortest Path Algorithms: An Evaluation using Real Road Networks Trans-portation Science, 1998, P. 1–10,
- Madyatmadja E., Nindito H., Bhaskoro R. et. al. Algorithm to find tourism place shortest route: a systematic literature review. Journal of Theoretical and Applied Information Technology. 2021. Vol. 99, No. 4, P. 1–10.
- Fitriansyah A., Parwati N., Wardhani D., Kustian N. Dijkstra's Algorithm to Find Shortest Path of Tourist Destination in Bali ICASMI, 2018.
- Basic algorithms for finding shortest paths in weighted graphs. Available at: https://habr. com/ru/post/119158/.
- Levit’s algorithm – search algorithms on graphs. Available at: https://amp.ww.google-info.org/ 3957083/1/algoritm-levita.html.
- Roopa Dr., Apoorva R., Srinivasu H., Viswanatah M. A Study on Different Algorithms for Shortest Route Problem International. Journal of Engineering Research & Technology (IJERT). 2013, Vol. 2, Iss. 9, P. 1–13.
- Krutko D. A. [The problem of finding the shortest path in three-dimensional space on the terri-tory of the Torgashinsky ridge]. Materials of the VIII International Scientific and Practical Confer-ence “Actual problems of aviation and cosmonautics“. Krasnoyarsk, 2022 (In Russ.).
- xml.dom.minidom – Minimal DOM implementation. Available at: https://docs.python.org/3/ library/xml.dom.minidom.html.
- Calculation of the distance and initial azimuth between two points on the sphere. Available at: https://gis-lab.info/qa/great-circles.html.
