Quantum Annealing for Realistic Traffic Flow Optimization: Clustering and Data-Driven QUBO

기술 요약: 현실적인 교통 흐름 최적화를 위한 양자 어닐링

문제 정의
본 연구는 도시 네트워크 내에서 각 차량에 대해 사전 계산된 대안 경로 세트 중 정확히 하나의 경로를 할당하는 교통 흐름 최집화(Traffic Flow Optimization, TFO) 문제를 다룬다. 목적 함수는 다음 두 가지 요소로 구성된 복합 비용 함수를 최소화하는 것이다:

1. 시공간적 혼잡도: 차량이 동일한 방향의 동일한 도로 구간을 겹치는 시간에 점유하는 "리더-팔로워(leader–follower)" 상호작용으로 모델링된다. 혼잡도는 차량 간 시간 간격(time headway)을 기반으로 산출된 점수에 민감도 파라미터 $\gamma$를 곱하여 정량화된다.
2. 경로 소요 시간 페널티: 개별 주행 효율이 시스템 전체의 이득을 위해 과도하게 희생되지 않도록, 가장 짧은 가용 경로보다 현저히 긴 경로를 할당하는 것에 대해 선형 페널티를 부여한다.

이 문제는 이차 무제약 이진 최적화(Quadratic Unconstrained Binary Optimization, QUBO) 문제로 정식화된다. 이진 변수 $x_{i,a_i}$는 차량 $i$의 경로 $a_i$ 선택을 나타낸다. QUBO 목적 함수는 쌍별(pairwise) 혼잡 상호작용을 인코딩하는 이차 항과 소요 시간 페널티를 위한 일차 항을 포함한다. 핵심 구성 요소는 Verma–Lewis 원칙을 따라 수동 튜닝 없이 "원-핫(one-hot)" 제약 조건(각 차량이 정확히 하나의 경로를 선택함)을 강제하는 해석적으로 도출된 페널티 파라미터 $\lambda$이다.

방법론
본 연구는 도시 네트워크 추출을 위한 OpenStreetMap(OSM)과 차량당 다수의 경로 대안을 생성하기 위한 Valhalla 라우팅 엔진을 활용하는 데이터 기반 워크플로우를 채택한다. 차량 궤적은 고정된 간격으로 샘플링되어 시공간적 중첩에 기반한 혼잡 가중치를 계산한다.

대규모 인스턴스(최대 25,000대 차량)에서의 변수 조합 폭발 문제를 해결하기 위해, 본 프레임워크는 **라이덴 클러스터링(Leiden clustering)**을 활용한다. 차량들은 쌍별 혼잡 상호작용을 기준으로 밀집된 커뮤니티로 분할된다. 이러한 분해를 통해 전역 문제를 일련의 작고 독립적인 하위 문제들로 나누어 해결할 수 있다.

최적화는 다음을 사용하여 평가된다:

• 양자/하이브리드 솔버: 양자 어닐러를 클래식 하이브리드 워크플로우 내의 서브루틴으로 사용하는 D-Wave의 LeapHybridBQMSampler (QAHS).
• 클래식 솔버: Gurobi (정확한 혼합 정수 계획법), CBC (오픈 소스 MILP), 시뮬레이티드 어닐링 (SA), 타부 서치 (Tabu Search).
• 베이스라인: 무작위 경로 할당 및 최단 시간 경로 지정.

평가는 세 가지 인스턴스 범주를 포괄한다: 소규모(직접 QPU 실행), 중규모, 그리고 여러 도시(Košice, Prague, Cardiff)에 걸친 대규모 도시 시나리오.

주요 기여

1. 데이터 기반 QUBO 정식화: 미세한 시공간적 차량 충돌과 주행 시간 페널티를 포착하는 확장 가능한 시계열 TFO 모델.
2. 해석적 페널티 파라미터: 경험적 튜닝 없이도 유효한 원-핫 경로 할당을 보장하는 해석적으로 도출된 $\lambda$.
3. 확장 가능한 워크플로우: 라이덴 클러스터링과 혼잡 모델링을 결합하여 최대 25,000대의 차량이 포함된 인스턴스에서도 벤치마킹이 가능하도록 설계된 시뮬레이션-최적화 파이프라인.
4. 광범-한 벤치마킹: 다양한 도시 토폴로지와 교통 패턴(무작위 vs. 유인 지점 지향 흐름)에 걸친 양자, 하이브리드 및 클래식 솔버의 비교 분석.
5. 프레임워크 유연성: 단독 분석 도구 또는 내비게이션 플랫폼의 애드온 모듈로 작동할 수 있는 확장 가능한 아키텍처로, 이벤트나 도로 폐쇄에 따른 동적 조정을 지원함.

결과

• 솔루션 품질: 대규모 시나리오 전반에서 하이브리드 양자-클래식 접근 방식(QAHS)은 정확한 솔버인 Gurobi가 달성한 목적 함수 값의 약 1% 이내의 오차로 유효한 솔루션을 일관되게 생성한다.
• 혼잡 감소: 최단 경로 베이스라인과 비교했을 때, 제안된 최적화 방식은 하이브리드 솔버의 경우 혼잡 비용 목적 함수를 최대 24.4%, Gurobi의 경우 **29.4%**까지 감소시킨다.
• 확장성 및 실행 시간: 작은 규모($n \le 4,000$)에서는 Gurobi가 QAHS보다 실행 시간 면에서 우수하지만, QAHS는 문제 규모가 커짐에 따라 지수적인 복잡도 증가를 겪는 클래식 솔버와 달리 안정적이고 예측 가능한 실행 시간(약 3초 ~ 117초 범위)을 보여준다. QPU 접근 시간은 무시할 만한 수준(<0.1초)이며, 병목 현상은 문제 임베딩과 오케스트레이션에서 발생한다.
• 토폴로지 민감도: 솔버 성능은 도시 지도 구조의 영향을 크게 받는다. 규칙적인 토폴로지(예: Cardiff)는 QAHS와 Gurobi 사이의 에너지 격차가 작지만(<0.83%), 불규칙하고 이질적인 네트워크(예: Košice)는 더 큰 편차를 보인다.
• 클러스터링 효능: 라이덴 클러스터링은 하위 문제 내에서 지배적인 혼잡 상호작용의 대부분을 성공적으로 포착하지만(내부 클러스터 상호작용 비율 $\eta$), 차량 수가 증가하고 상호작용이 더 분산됨에 따라 이 비율은 감소한다.

의의 및 주장
본 논문은 하이브리드 양자-클래식 접근 방식이 TFO와 같은 복잡한 대규모 최적화 문제를 위한 유망한 보완적 방법이 될 수 있다고 주장한다. 본 연구는 정확한 클래식 솔버(Gurobi)가 현재로서는 절대적으로 최선의 솔루션을 달성하지만, 하이브리드 솔버는 안정적인 실행 시간과 도시 규모 네트워크에 대한 최적에 가까운 품질을 제공하며 실용적인 대안이 될 수 있음을 입증한다.

저자들은 이 프레임워크가 개별 운전자의 효율성과 시스템 전체의 혼잡 감소 사이의 균형을 맞추며, 지능형 교통 시스템(ITS)에 추가될 수 있는 잠재력을 가지고 있다고 강조한다. 또한 양자 어닐링의 효과는 인스턴스 의존적이며, 특히 네트워크 토폴로지와 쌍별 상호작용의 밀도에 민감하다는 점을 밝힌다. 본 연구는 오프라인 전처리(실시간 아님)의 필요성과 정적 시뮬레이션 윈도우에 대한 의존성 등 현재의 한계를 인정하면서도, 양자 하드웨어와 임베딩 기술이 성숙함에 따라 이 접근 방식이 더 크고 상세한 정식화 모델을 다룰 수 있을 것이라고 시사한다.