1.4 Использование квантовых вычислений для поиска кратчайшего пути (Q-ROUTE)

ОБЛАСТЬ (СФЕРА), К КОТОРОЙ ОТНОСИТСЯ РАЗРАБОТКА: Информационные технологии, облачные технологии, предприятия Минсвязи и транспорта .

ЦЕЛЬ (ПРОБЛЕМА) РАЗРАБОТКИ: Одной из самых сложных задач, встающей перед автомобилистами, является построение оптимального маршрута по карте дорог. На сегодняшний день данная задача решается не полностью при помощи существующих устройств, т.к. они не учитывают различные метрики, влияющие на время прохождения маршрута. Цель разработки – ускорение вычисления кратчайшего пути за счет использования квантовых вычислений.

КРАТКОЕ ОПИСАНИЕ РАЗРАБОТКИ: В данной работе предложен новый подход нахождения кратчайшего маршрута на графе дорог. Этот подход основан на теории графов и использует основные принципы квантовых вычислений. Одним из многочисленных преимуществ квантовых вычислений является высокое быстродействие при выполнении параллельных операций. Предложенный подход позволяет находить несколько возможных путей одновременно и выбирать оптимальный маршрут на основе специальных метрик и параметров.

ИННОВАЦИОННЫЕ ХАРАКТЕРИСТИКИ РАЗРАБОТКИ: Инновационная привлекательность разработки заключается в том, что предложенная интеллектуальная система поиска кратчайшего маршрута предоставляет пользователю актуальную информацию о дорожной ситуации, которая меняется ежесекундно. Так же стоит отметить то, что у пользователя появляется возможность самостоятельного выбора критериев и метрик оптимального маршрута. Актуальность этой возможности в том, что для каждого пользователя системы, в зависимости от обстоятельств, для одного и того же направления могут быть важны различные критерии в разных ситуациях (скорость, расстояние или качество дорожного покрытия). Предлагаемая система позволяет учитывать данные параметры в поиске оптимального маршрута и находить несколько маршрутов одновременно (в один момент времени) посредством использования квантовых вычислений нового поколения.

ПРЕИМУЩЕСТВА РАЗРАБОТКИ: Вся карта на требуемом промежутке представляется в виде ориентированного графа дорог. Граф дорог представляет собой набор метрически и топологически связанных вершин и дуг, которые точно передают направление движения, расстояние и связи между перекрестками и развязками.  Направление дуг означает направленность движения потока, вершины графа или узлы – перекрестки и развязки. Каждой дуге присваивается вес, рассчитанный на основе метрик. Метрики выбираются на этапе построения графа, например минимальное количество левых поворотов, лучшее качество дороги, наивысшая возможная скорость, минимальное количество светофоров и т.п.

Повышается актуальность информации о маршрутах за счет обновления графа дорог при каждом запросе оптимального пути. К примеру, изменить дорожную ситуацию могут ремонтные работы, аварии, блокирование движения во время массовых мероприятий и др. Постоянное обновление графа дорог для запрашиваемого участка позволит генерировать оптимальный маршрут в данный момент времени и этот маршрут не потеряет актуальность до следующего обновления графа дорог.

Под обновлением графа дорог понимается пересчет весов дуг графа. Перестраивать граф полностью при каждом запросе не имеет смысла, т. к. положение дорог на карте, их направление и связи на перекрестках и развязках остаются неизменными на протяжении достаточно длительного промежутка времени. Обновление весов графа позволяет проследить все нюансы изменения дорожной сети и позволяет использовать постоянный граф дорог.

АНАЛИЗ РЫНКА: Существующие системы поиска кратчайшего маршрута не отвечают современным требованиям быстродействия. Квантовые технологии позволяют в разы ускорить процесс поиска кратчайшего маршрута на графе дорог. Такой подход не был использован ни в одной системе мира.

ОЦЕНКА ТРАНСФЕРА РАЗРАБОТКИ: Предложенные пути трансфера разработки: обмен опытом и информацией о научно-технологические достижения, проведение консультаций по вопросам применения технологий, поставки технологий в рамках договоров об их трансфер с учетом рыночной потребности.

СТАДИЯ РАЗРАБОТКИ: Частичная реализация, прототип, заявка на получение патента. Проект является участником конкурса «IT-Kharkіv» в 2013 г.

ФИНАНСОВЫЕ РАСХОДЫ НА РАЗРАБОТКУ: По наличию в стране 10 миллионов автомобилей и стоимости одной метки RFID $100, затраты на оснащение всего транспортного парка составляют $1 млрд. Расходы на создание масштабного прототипа ИИДР – $10 млн. плюс накладные расходы по технической поддержке и эксплуатации инфраструктуры. Годовая стоимость продажи облачного сервиса – не более $100  для каждой машины. Это составляет около $2 млрд. прибыли после 3 лет эксплуатации облака. Срок окупаемости ИИДР – 1,5 года. Возможные источники финансирования: 1) бюджетные средства на разработку комплексной научно-исследовательской фундаментальной работы «Интеллектуальная инфраструктура дорожного движения – облачный сервис «Зеленая волна»» (2014-2016), выигравшая конкурс в рамках приоритетного направления развития науки и техники (по Закону Украины от 12.10.2010 № 2519-17) «Фундаментальные научные исследования по наиболее важным проблемам развития научно-технического, социально-экономического, общественно-политического, человеческого потенциала для обеспечения конкурентоспособности Украины в мире и устойчивого развития общества и государства, п. 1.10 – математические основы интеллектуальных систем обработки информации; экспертные системы; математические проблемы понимания естественного языка» по приоритетному тематическому направлению (согласно Постановлению КМУ от 07.09.2011 № 942) «Важнейшие проблемы физико-математических и технических наук», 2) собственные средства – $10000.

ИНФОРМАЦИЯ ОБ АВТОРСКОМ КОЛЛЕКТИВЕ: Хаханов Владимир Иванович, д.т.н., проф.; Чумаченко Светлана Викторовна, д.т.н., проф.; Литвинова Евгения Ивановна, д.т.н., проф.; Зиарманд Артур Нисарович; Мизь Владимир Александрович; Филипенко Олег Игоревич, к.т.н.

cохранить эту страницу в PDF