Извините, этот техт доступен только в “Американский Английский”. For the sake of viewer convenience, the content is shown below in the alternative language. You may click the link to switch the active language.
OVERVIEW OF ALGORITHMS FOR FINDING THE OPTIMAL ROUTE FOR VEHICLES
Julia V. Mahovikova, Reshetnev Siberian State University of Science and Technology, Krasnoyarsk, Russia, mahovikova1994@gmail.com
Svetlana N. Mironenko, Reshetnev Siberian State University of Science and Technology, Krasnoyarsk, Russia, sn-mironenko@mail.ru
Aleksandr V. Devjatkov, Reshetnev Siberian State University of Science and Technology, Krasnoyarsk, Russia, dav009@bk.ru
Jaroslav I. Shamlitskiy, Reshetnev Siberian State University of Science and Technology, Krasnoyarsk, Russia, 2538357@mail.ru
Abstract
Cargo transportation management is impossible without quality planning, which should be aimed at efficient use of vehicles. The key tasks of transportation management are cargo routing and distribution of vehicles along routes, provided that the transportation plan is fulfilled in accordance with the selected optimization criteria. The modern development of information and communication technologies allows us to significantly improve the quality of planning and monitoring the execution of orders for the transportation of goods by land transport. Equipping drivers of cargo vehicles with satellite navigation devices and terminals with Internet access provides a technical opportunity for information interaction with dispatchers in real time, which determines new requirements for intelligent transport resource planning systems taking into account the human factor [9]. When creating simulators that involve moving different types of vehicles over large areas, taking into account the current tactical situation, there are problems with choosing the optimal path search algorithm, since its use is subject to restrictions. There are a large number of algorithms that allow you to determine the route by which you can get from one point to another. The main problem with the path search problem is that there is no universal algorithm for solving it. An overview of algorithms for finding the optimal path for vehicles (the Algorithm A* and its modifications, in particular Beam search; Iterative deepening; Dynamic weighing; Bidirectional search; Bandwidth search; Jump Point Search; Theta*). It is concluded that it is advisable to use different algorithms at the stages of building a preliminary route variant and optimizing it.
Keywords: suboptimal algorithms, A* algorithm, Theta* algorithm, route planning, vehicle.
References
- Botea A., Muller M., Schaeffer J. (2004). Near Optimal Hierarchical Path-Finding. Journal of Game Development. Vol. 1, issue 1, pp. 7-28.
- Eric Hansen, Terry Huntsberger and Les Elkins. (2006). Autonomous maritime navigation : developing autonomy skill sets for USVs. Proc. SPIE 6230, 62300U.
- Nash A. Any-Angle Path Planning. Dis. … Doctor of Philosophy (Computer Science). University of South California. August 2012.
- Variants of A*, Amit Patel’s Home Page. http://theory.stanford.edu/~amitp/GameProgramming/Variations.html (accessed 15.12.2019).
- Basarab M.A., Domracheva A.B., Kupljakov V.M. (2013). Algoritmy reshenija zadachi bystrogo poiska puti na geograficheskih kartah. Inzhenernyj zhurnal: nauka i innovacii. No. 11. URL: http://engjournal.ru/ catalog/it/hidden/1054.html (accessed 20.12.2019). (in Russian)
- Kravchenko M.K., Krivosheev S.V., Mal’cheva R.V. (2018). Realizacija algoritma poiska puti dlja transportnogo sredstva. Sovremennye tendencii razvitija i perspektivy vnedrenija innovacionnyh tehnologij v mashinostroenii, obrazovanii i jekonomike. Azov. Vol. 4. No. 1(3), pp. 107-111. (in Russian)
- Krivosheev S.V. (2012). Issledovanie jeffektivnosti parallel’nyh arhitektur vychislitel’nyh sistem dlja rascheta parametrov dvizhenija transportnogo sredstva. Nauchnye trudy Doneckogo nacional‘nogo tehnicheskogo universiteta. No. 1 (10) — 2 (11). Serija «Problemy modelirovanija i avtomatizacii proektirovanija». Doneck, DonNTU, pp. 207-214. (in Russian)
- Mal’cheva R.V., Krivosheev S.V., Zavadskaja T.V. (2015). Razrabotka simuljatorov transportnyh sredstv s ispol’zovaniem operacionnoj sistemy Android. Informatika i kibernetika. No. 2, pp. 76-81. (in Russian)
- Pejsahovich, D.G. Upravlenie interaktivnoj dispetcherizaciej v edinom informacionnom prostranstve posrednicheskogo transportnogo operatora : dissertacija kandidata tehnicheskih nauk : 05.13.10. Mesto zashhity: Penzenskij gosudarstvennyj universitet . Penza, 2014, pp. 151. (in Russian)
Information about authors:
Julia V. Mahovikova, Reshetnev Siberian State University of Science and Technology, graduate student, Krasnoyarsk, Russia
Svetlana N. Mironenko, Reshetnev Siberian State University of Science and Technology, graduate student, Krasnoyarsk, Russia
Aleksandr V. Devjatkov, Reshetnev Siberian State University of Science and Technology, graduate student, Krasnoyarsk, Russia
Jaroslav I. Shamlitskiy, Reshetnev Siberian State University of Science and Technology, Candidate of Engineering Sciences (Ph.D), associate professor Department of Information Management Systems, Krasnoyarsk, Russia