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.

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

зберегти цю сторінку в PDF