루트 기반 동적 할당 알고리즘 (Path-based Dynamic Assignment)

루트 기반 동적 할당 알고리즘(Path-based Dynamic Assignment, PDA)은 교통 수요자(운전자 또는 통행자)가 시간에 따라 변화하는 교통 상황을 고려하여, 가능한 경로들 중에서 실제 선택되는 경로를 예측하고, 이를 기반으로 교통 흐름을 네트워크에 동적으로 분배하는 알고리즘이다. 기존의 정적 경로 할당(static assignment) 또는 링크 기반(link-based) 할당과 달리, 경로 단위(path-based)로 수요를 추적하고, 시간 축을 반영하여 도로 네트워크에 수요를 동적으로 할당한다는 점에서 교통현실과 밀접한 예측을 가능하게 한다.

이 알고리즘은 특히 출발 시간이 다른 다수의 사용자들이 교통 상황에 따라 경로를 달리 선택할 수 있다는 전제를 기반으로 하며, 도심 교통 흐름의 재구성, 혼잡 예측, 스마트 내비게이션 알고리즘 설계 등 다양한 분야에 활용된다.

---

1. 루트 기반 동적 할당의 개념과 필요성

기존의 교통배분 모델은 OD(출발지–도착지) 수요를 전체 경로에 평균적으로 분배하거나, 링크에 고정된 비율로 나누는 방식이 많았다. 그러나 실제 교통현상은 다음과 같은 특징을 가진다:

• 교통 수요는 시간에 따라 변동하며, 피크 시간대 또는 이벤트 발생 시 수요 패턴이 급변한다.
• 운전자들은 교통 상황(혼잡, 사고 등)에 따라 다양한 경로를 선택하며, 이러한 경로 선택은 실시간 교통 정보, 신호 주기, 대기 시간 등에 의해 영향을 받는다.
• 같은 OD쌍이라 하더라도 출발 시간과 경로 선택에 따라 실제 통행 시간은 매우 다르게 나타난다.

이러한 현실을 반영하기 위해 고안된 것이 루트 기반 동적 할당(Path-based Dynamic Assignment)이다. 이 모델은 ‘누가, 언제, 어떤 경로로 이동하는가’에 대한 정보를 기반으로, 시간 단위로 교통 수요를 각 경로에 분배하고, 네트워크의 혼잡도에 따라 다시 수요를 조정하는 동적 피드백 구조를 가진다.

---

2. 알고리즘 구조와 작동 원리

루트 기반 동적 할당 알고리즘은 일반적으로 다음과 같은 절차로 구성된다.

▶ 1) OD 수요 시간 분할

• 전체 OD 수요를 시간 단위(예: 5분, 15분 간격 등)로 나눈다.
• 각 시간대의 수요는 일정한 출발률로 표현되며, 시간에 따라 달라지는 교통량을 반영한다.

▶ 2) 경로 세트 정의 (Feasible Path Set)

• 각 OD쌍에 대해 실제 선택 가능한 경로들(Path Set)을 도출한다.
• 이때 K단 최단 경로(K-shortest paths), 최소 혼잡 경로, 신호 연동 경로 등을 포함시킬 수 있다.

▶ 3) 초기 경로 분배

• 각 시간대의 OD 수요를 경로 세트에 일정 기준(예: 시간 최소, 유틸리티 최대 등)으로 초기 분배한다.
• 예: 모든 수요자가 최단 시간 경로를 선택한다고 가정하여 초기 분배

▶ 4) 네트워크 흐름 계산

• 경로별 교통 흐름을 바탕으로 각 링크의 시간 가변적 통행시간(travel time)을 계산
• 셀 전이 모델(Cell Transmission Model, CTM) 등 시뮬레이션 기법과 연계 가능

▶ 5) 경로 비용 피드백 및 재분배

• 계산된 경로 통행시간을 기반으로 다음 반복에서 수요를 재분배
• 사용자는 자신이 선택한 경로의 통행시간을 인지하고, 더 나은 경로로 이동하려는 경향을 반영

이 과정을 수렴 조건(convergence criteria)을 만족할 때까지 반복하여, 최종적으로 사용자 평형(User Equilibrium) 또는 시스템 최적(System Optimum) 상태에 도달한다.

---

3. 수학적 모델과 사용자 평형 조건

루트 기반 동적 할당의 핵심은 각 경로에 대한 시간 의존적 통행시간 함수와 경로 선택 확률의 상호작용이다. 주요 조건은 다음과 같다:

• 사용자 평형(User Equilibrium, UE) 조건:
   → "동일 OD쌍 내의 모든 선택된 경로는 동일한 통행시간을 가지며, 이보다 낮은 통행시간을 갖는 경로는 선택되지 않는다."
• 시간 의존 사용자 평형(Time-Dependent UE, T-DUE) 조건:
   → “같은 OD쌍에 대해, 같은 시간에 출발하는 사용자는 자신이 선택한 경로보다 빠른 경로로 이동할 수 없다.”

이 조건을 만족시키기 위해 수요 재분배는 고정점 반복(Fixed-Point Iteration) 또는 유틸리티 기반 로짓모델(Logit Assignment)로 수행된다. 특히 로짓모형을 활용하면 사용자가 경로 간 차이를 확률적으로 인지하고 선택하는 행태적 모델링이 가능하다.

---

4. 주요 응용 분야

루트 기반 동적 할당 알고리즘은 다음과 같은 교통 시스템 설계 및 정책 분석에 활용된다.

▷ 동적 신호 운영 전략 수립

– 시간대별 혼잡 경로를 파악하고, 특정 경로에 수요가 집중될 경우 : 적응형 신호 주기를 조정하여 교통 흐름을 개선

▷ 혼잡 요금제 시뮬레이션

– 특정 시간·구간에 통행이 집중될 경우, 혼잡통행료를 도입했을 때 : 경로 재배분 효과를 예측할 수 있음

▷ 스마트 내비게이션 알고리즘 검증

– 경로 추천 알고리즘이 실제 사용자의 경로 선택에 어떤 영향을 주는지 시뮬레이션 기반으로 확인 가능

▷ 긴급상황 대응 시나리오

– 재난 또는 사고 발생 시, 수요 분산 경로를 제시하고 그에 따른 새로운 균형 상태를 예측하여 우회 전략 설계

---

5. 실제 적용 사례와 연구 동향

▷ 미국 DynaMIT 시스템

MIT에서 개발한 DynaMIT는 대표적인 루트 기반 동적 할당 시뮬레이션 시스템이다.
실시간 센서 데이터를 기반으로 OD 수요를 예측하고, 동적 경로 재분배를 수행하여 교통 흐름을 시뮬레이션하고 운영 전략을 도출한다.

▷ 서울시 내비게이션 연계 시뮬레이션

T맵 기반 교통 데이터를 활용하여, 실제 사용자가 선택한 경로를 기반으로 루트 기반 할당 결과와 비교 분석을 수행함.
내비게이션의 경로 추천이 어떻게 도시 전체 혼잡도에 영향을 주는지 분석하는 데 활용

▷ 유럽 SUMO 연계 DTA 실험

오픈소스 시뮬레이터 SUMO와 연동하여 PDA 모델을 구현하고, BPR 기반 통행시간 함수와 비교 분석 수행

---

6. 기술적 과제와 향후 확장

▷ 경로 세트의 정의 기준

– 실제 운전자가 인지 가능한 경로만을 반영해야 현실성 확보
– 너무 많은 경로는 계산량 증가, 너무 적은 경로는 정확도 저하 → 최적 경로세트 추출 알고리즘 필요

▷ 수렴성 문제

– 동적 경로 재분배는 반복이 많아질수록 계산량 증가
– 특히 대규모 네트워크에서는 병렬 연산, 클라우드 기반 처리 필요

▷ 행태적 요소 반영

– 경로 선택은 단순히 시간만의 문제가 아님 (안전성, 도로 환경 등도 고려됨)
– 로짓 기반 선택 모델, GPS 궤적 기반 경로 이탈 학습 등을 함께 고려해야 함

---

7. 경로 중심 사고로의 교통 모델링 전환

루트 기반 동적 할당은 단지 수요를 나누는 수치적 과정이 아니라, ‘도시 내 이동이 어떻게 선택되고 분산되는지’를 이해하는 프레임워크이다. 각 사용자의 출발 시간, 목적지, 경로 선택 행태를 고려하여 도시 전체의 흐름을 유연하게 구성할 수 있는 이 알고리즘은 스마트시티, 자율주행, 디지털 트윈 기반 교통 정책의 핵심 도구가 될 것이다. 교통공학자는 이제 도로의 정체를 수치로 보는 것을 넘어, 시간과 공간, 그리고 사람의 선택이 만들어내는 도시의 흐름을 설계하는 '경로 전략가'로 진화해야 한다.