Облачное управление транспортом: выбор оптимального маршрута

Информационные технологии

Аннотация

Рассматривается алгоритм построения оптимального маршрута на дорожной инфраструктуре между двумя координатами, которые отождествляются с пунктом отправления и прибытия. Возможные ограничения связаны с дорожными коллизиями, авариями и ремонтом дорог, что также должно быть учтено при выборе оптимального маршрута. Предполагается, что реализация алгоритма будет представлена в качестве online облачного сервиса для водителей транспортных средств в рамках создания киберфизической системы интеллектуального облачного управления транспортом. Предлагается также критерий качества топологии, учитывающий суммы всех расстояний между каждой парой компонентов или вершин соответствующего графа, приведенной к числу ребер. Ставятся и решаются следующие задачи: 1) определить все кратчайшие пути и соответствующие расстояния из фиксированной вершины v до остальных вершин инфраструктуры; 2) найти кратчайшие расстояния между всеми парами вершин для графа с единичными весовыми коэффициентами, заданного матрицей смежности; 3) найти кратчайшие расстояния между всеми парами вершин и оценить инфраструктуры по разработанным критериям качества для различных типов графов, заданных матрицами смежности; 4) выполнить сравнение различных архитектур и графовых структур в целях определения эффективных решений для сокращения времени движения по заказанному маршруту. В результате проведенных исследований выполнен пошаговый синтез предложенного метода построения оптимального маршрута движения транспортного средства. Упрощенные критерии качества топологий показывают, что дорожная инфраструктура, построенная на треугольных соединениях пунктов отправления и прибытия, в два раза эффективнее, чем общепринятая топология “Манхеттен”.