Новый алгоритм управления дорожным трафиком в реальном времени с помощью квантовых вычислений разработали исследователи Университета Иннополис. Алгоритм способен проанализировать транспортную нагрузку на дороги, оптимизировать городские маршруты для автомобилистов и вычислять новые меньше, чем за секунду. Исследование опубликовал международный журнал Nature Scientific Reports.
Исследователи Университета Иннополис провели виртуальные эксперименты, создав модели реальных сложных дорожных сетей с многочисленными пунктами отправления и назначения на карте казахстанского города Алматы. Учёные использовали квантовый процессор компании D-Wave с топологией Pegasus и наборы данных от 100 до 500 автомобилей. Сотрудники ИТ-вуза разбивали дорожную схему города на сегменты и транспортные узлы для оценки её пропускной способности, выбирали участки дорог с максимальной загруженностью и преобразовывали задачи в форму, пригодную для дальнейшего вычисления на QPU — квантовых процессорах. Затем задачи решались автономно на квантовой архитектуре D-Wave с итеративным уточнением — повторением вычислений до достижения оптимального распределения дорожного трафика.
Предложенный «мини-масштабный» метод оптимизации помог снизить загруженность транспортного потока на 25% для 100 автомобилей и на 62% для 500 автомобилей, в то время как классический гибридный подход улучшил дорожную ситуацию лишь на 7%. При этом время вычислений для нового способа составило 0,15—0,225 секунды на каждую итерацию, что в 13—20 раз быстрее гибридного метода, который справился с задачей за 3 секунды.
Ярослав Холодов, руководитель Лаборатории квантовых вычислений Университета Иннополис: «Пробки на дорогах любого города мира несут множество негативных последствий, включая потерю времени автомобилистов и пассажиров, экономические издержки, повышенное загрязнение окружающей среды и отрицательное влияние на здоровье жителей. Оптимизация дорожного трафика относится к сложным вычислительным задачам. Традиционные методы, такие как адаптивные системы управления сигналами светофоров и алгоритмы оптимизации автомобильных маршрутов, сталкиваются с ограничениями при работе с большими объёмами данных в реальном времени. Квантовые вычисления предлагают принципиально новый подход, позволяя обрабатывать множество данных одновременно и находить оптимальные решения намного быстрее классических методов».
Как отмечают исследователи, в экспериментах компаний Volkswagen и D-Wave, которым первым в мире удалось продемонстрировать потенциал квантовых вычислений для оптимизации транспортных потоков, использовался гибридный классическо-квантовый подход. Тогда квантовый процессор не полностью справлялся с задачей из-за ограничения размерности: чем выше размерность задачи, то есть больше транспортная сеть и количество автомобилей в ней, тем больше архитектурные ограничения влияют на вычислительный процесс.
Команда Университета Иннополис предложила декомпозировать — разбить —- глобальную задачу оптимизации трафика на несколько небольших подзадач, которые легче решить на квантовом вычислителе. Такой подход, по словам учёных, снимает ограничения размерности, позволяет преодолеть вычислительные ограничения квантовых процессоров и обеспечить ускорение ключевых этапов оптимизации. Это особенно важно, например, для управления динамическими транспортными потоками, требующими одновременного учёта множества факторов. Свой метод эксперты назвали «мини-масштабной оптимизацией».
Ярослав Холодов, руководитель Лаборатории квантовых вычислений Университета Иннополис: «Наш численный эксперимент подтвердил, что квантовые вычисления повышают скорость и эффективность оптимизации трафика в реалистичных сценариях, открывая путь для практического применения квантовых технологий в управлении городской мобильностью. В перспективе модель можно усовершенствовать, добавив реальные параметры: синхронизацию светофоров, погодные условия и поведение водителей. Это позволит создать более точную систему управления трафиком, совместимую с существующей инфраструктурой — детекторами транспорта и дорожными видеокамерами».
Статью «Мини-масштабная оптимизация трафика: итеративный подход QUBO с переходом от гибридного решателя к чисто квантовому процессору» (Mini-scale Traffic Flow Optimization: An Iterative QUBOs Approach Converting from Hybrid Solver to Pure Quantum Processing Unit) опубликовал научный журнал Scientific Reports, издаваемый Nature Portfolio. Её авторы — исследователи Университета Иннополис: руководитель Лаборатории квантовых вычислений Ярослав Холодов, программист-математик Института ИИ Хади Саллум, аспирант Амер Аль Бадр и студент Санжар Жаналин.
