Перевод названия: Обзор алгоритмов поиска оптимального маршрута транспортных средств
Тип публикации: статья из журнала
Год издания: 2020
Идентификатор DOI: 10.36724/2072-8735-2020-14-2-52-56
Ключевые слова: suboptimal algorithms, А* algorithm, Theta* algorithm, route planning, vehicle, субоптимальные алгоритмы, алгоритм A*, алгоритм Theta*, планирование маршрута, транспортное средство
Аннотация: 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 А* 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. Управление перевозками грузов невозможно без качественного планирования, которое должно быть направлено на эффективное использование транспортных средств. Ключевыми задачами управления перевозками являются маршрутизация грузоперевозок и распределение транспортных средств по маршрутам при условии выполнения плана перевозок в соответствии с выбранным критерием оптимизации. Современное развитие информационно-коммуникационных технологий позволяет существенно повысить качество планирования и контроля исполнения заказов на перевозку грузов наземным транспортом. Оснащение водителей грузовых транспортных средств устройствами спутниковой навигации и терминалами с выходом в Интернет обеспечивает техническую возможность информационного взаимодействия с диспетчерами в режиме реального времени, что определяет новые требования к интеллектуальным системам планирования транспортных ресурсов с учетом человеческого фактора [9]. При создании симуляторов, подразумевающих перемещение различных типов транспортных средств по большим территориям с учетом текущей тактической обстановки, возникают проблемы с выбором алгоритма поиска оптимального пути, так как на его использование накладываются ограничения. Существует большое количество алгоритмов, позволяющих определить маршрут, по которому можно попасть из одной точки в другую. Главная проблема задачи поиска пути заключается в том, что не существует какого-либо универсального алгоритма ее решения. Проведен обзор алгоритмов поиска оптимального пути для транспортных средств (Алгоритм A* и его модификации, в частности Beam search (поиск по лучу); Iterative deepening (итеративное погружение); Dynamic weighting (использование переменных весов); Bidirectional search (двунаправленный поиск); Bandwidth search (Поиск полосы пропускания); Jump Point Search (поиск точки перехода); Theta*). Сделан вывод о целесообразности использования различных алгоритмов на этапах построения предварительного варианта маршрута и его оптимизации.
Журнал: T-Comm: Телекоммуникации и транспорт
Выпуск журнала: Т. 14, № 2
Номера страниц: 52-56
ISSN журнала: 20728735
Место издания: Москва
Издатель: ООО "Издательский дом Медиа паблишер"