교통 배정

1. 개요[편집]

교통 배정 Traffic assignment
위치	4단계 수요모형의 마지막 단계
입력	OD 통행량 행렬 + 네트워크 + 링크 성능함수
출력	링크별 유량과 통행시간
성능함수	BPR $t = t_0\bigl(1+\alpha(x/c)^\beta\bigr)$, 국룰 $\alpha=0.15,\ \beta=4$
표준 해법	프랭크-울프 (LeBlanc 등 1975) · MSA · 경사투영법
수렴 판정	상대격차(relative gap), 실무 목표 $10^{-4}$ 이하
확장	확률적 사용자 균형(SUE) · 동적 배정(DTA) · 미시 시뮬레이션

교통 배정(traffic assignment)은 기점-종점(OD) 통행량 행렬과 도로망이 주어졌을 때 각 통행이 어느 경로를 택할지 결정해 링크별 유량을 산출하는 절차다. 교통 계획에서 “이 도로를 넓히면 몇 대가 늘어나는가”라는 질문에 숫자로 답하는 유일한 단계이고, 그래서 예산이 걸린 논쟁은 결국 배정 결과를 놓고 벌어진다.

균형 개념 자체는 워드롭 균형이 정의하고, 그 균형이 왜 최적이 아닌지는 브라에스 역설과 무정부의 대가가 다룬다. 이 문서는 그래서 그 균형을 실제로 어떻게 계산하느냐를 본다. 결론부터 말하면 “최단경로를 돌리고, 그쪽으로 조금만 옮기고, 반복한다”가 전부이며, 나머지는 얼마나 옮길지와 언제 멈출지에 대한 60년치 논쟁이다.

2. 4단계 모형에서의 위치[편집]

전통적 교통수요 예측은 네 단계로 나뉜다.

1. 통행발생(trip generation) — 존별로 몇 통행이 나가고 들어오는가.
2. 통행분포(trip distribution) — 어느 존에서 어느 존으로. 중력 모형이 고전이다.
3. 수단선택(mode choice) — 승용차냐 버스냐 지하철이냐. 로짓 계열 이산 선택 모형.
4. 노선배정(traffic assignment) — 이 문서.

앞의 세 단계가 뽑아낸 OD 행렬 $q^{rs}$ 를 네트워크에 얹는 것이 배정이다. 순차 구조의 근본 결함은 널리 알려져 있다 — 배정 결과로 나온 통행시간이 앞 단계의 입력과 다르다. 그래서 실무에서는 배정 → 통행시간 갱신 → 수단선택·분포 재계산의 외부 루프를 몇 번 돌리는 “피드백 4단계”를 쓰고, 이 외부 루프의 수렴 역시 감쇠 없이는 진동한다. 활동기반 모형(activity-based model)은 이 구조 자체를 갈아엎으려는 시도지만, 배정 단계만큼은 대개 그대로 재사용한다.

3. 링크 성능함수[편집]

배정의 물리는 링크 성능함수 하나에 다 들어 있다. 미국 도로국이 1964년에 제안한 BPR 함수가 사실상 표준이다.

$$t_a(x_a) \;=\; t_a^0\left(1 + \alpha\left(\frac{x_a}{c_a}\right)^{\beta}\right), \qquad \alpha = 0.15,\ \ \beta = 4$$

$t_a^0$ 는 자유속도 통행시간, $c_a$ 는 실용용량이다. 순증가·미분가능·볼록이라 워드롭 균형의 베크만 변환이 요구하는 조건을 전부 만족하고, 적분도 닫힌 형태로 나온다.

$$\int_0^{x} t_a(w)\,dw \;=\; t_a^0\left(x + \frac{\alpha}{\beta+1}\cdot\frac{x^{\beta+1}}{c_a^{\beta}}\right)$$

정직하게 말해 두면 이 함수는 물리가 아니라 회귀식이다. 결함이 두 가지 있다.

• 용량을 넘어도 유한한 값을 준다. $x/c = 2$ 면 $3.4\,t^0$, $x/c = 3$ 이어도 $13.2\,t^0$ 밖에 안 된다. 실제로는 용량을 넘는 순간 대기행렬이 생기고 통행시간은 수요가 아니라 대기시간이 지배한다. 정적 배정은 그걸 못 본다.
• 대기행렬이 상류로 안 번진다. 링크 성능이 자기 유량만의 함수라는 가정 자체가 spillback 을 금지한다. 이게 아래의 동적 배정이 필요한 첫 번째 이유다.

$\beta=4$ 라는 값도 근거가 튼튼하지는 않다.¹ 도시부는 더 완만한 값이 낫다는 연구가 많고, 기관마다 도로 등급별로 다른 $(\alpha,\beta)$ 표를 쓴다. 모형 결과가 $\beta$ 에 민감하면 그건 결과가 아니라 가정이다 — 민감도 해석을 붙여야 하는 지점.

4. 전량배정과 용량제약 반복[편집]

가장 단순한 배정은 전량배정(All-Or-Nothing, AON)이다. 자유속도 통행시간으로 다익스트라 알고리즘을 돌려 OD 별 최단경로를 찾고, 그 경로에 수요를 전부 얹는다. 혼잡을 무시하므로 균형이 아니고, 최단경로가 살짝만 바뀌어도 결과가 통째로 뒤집힌다. 그럼에도 사라지지 않는 이유는 모든 균형 알고리즘의 내부 부품이기 때문이다.

여기서 자연스럽게 나오는 발상이 용량제약 반복이다. AON → 통행시간 갱신 → 다시 AON → …. 그리고 이건 거의 반드시 발산하거나 진동한다. 전원이 매번 통째로 옮겨 다니기 때문이다. 두 개의 평행 링크에 수요를 얹어 보면 전원이 좌우로 왕복하며 영원히 안 멈추는 걸 즉시 볼 수 있다.

처방은 두 가지 계열이다.

• 점증배정(incremental) — 수요를 20 %씩 다섯 번에 나눠 얹으며 매번 통행시간을 갱신. 간단하지만 균형에 수렴하지 않고, 나눈 횟수에 답이 의존한다.
• 감쇠 반복 — AON 결과를 방향으로만 쓰고 이동량을 제어. 이게 프랭크-울프와 MSA 다.

5. 프랭크-울프[편집]

르블랑 등(1975)이 베크만 문제에 프랭크-울프 알고리즘을 붙인 것이 교통 배정의 사실상 표준이 됐다.² 논리는 이렇다. 베크만 목적함수

$$z(x) \;=\; \sum_a \int_0^{x_a} t_a(w)\,dw$$

를 현재 점 $x^n$ 에서 선형화하면 그래디언트가 $\nabla z = \bigl(t_a(x_a^n)\bigr)$ 이므로, 부분문제는

$$\min_{y \in \Omega} \ \sum_a t_a(x_a^n)\, y_a$$

가 된다. 그런데 이 선형계획은 그냥 현재 통행시간으로 최단경로를 찾아 전량배정하는 것이다. 유량 보존 다면체 위에서 선형함수를 최소화하는 문제가 최단경로 문제로 분해되기 때문이다. 즉 프랭크-울프의 부분문제를 푸는 데 LP 솔버는 필요 없고 다익스트라 알고리즘이면 된다. 이 성질 하나가 이 조합을 60년째 살아 있게 만들었다.

전체 절차는 다섯 줄이다. ① 자유속도 통행시간으로 AON 해서 $x^0$ 을 만든다. ② 현재 통행시간 $t_a^n = t_a(x_a^n)$ 로 AON 해서 방향점 $y^n$ 을 얻는다. ③ 선탐색으로 $\lambda^n \in [0,1]$ 을 정한다. ④ $x^{n+1} = x^n + \lambda^n (y^n - x^n)$. ⑤ 상대격차가 목표 아래면 종료, 아니면 ②로.

선탐색이 이 알고리즘에서 유일하게 머리를 쓰는 곳인데, 다행히 1차원 볼록 문제라 도함수의 근만 찾으면 된다.

$$\frac{d}{d\lambda}\,z\bigl(x^n + \lambda(y^n - x^n)\bigr) \;=\; \sum_a (y_a^n - x_a^n)\, t_a\bigl(x_a^n + \lambda (y_a^n - x_a^n)\bigr) \;=\; 0$$

$\lambda=0$ 에서 음수, $\lambda=1$ 에서 양수인 단조 증가 함수이므로 이분법 몇 번이면 충분하다. 라인서치의 교과서적 사용례이며, 굳이 뉴턴법을 쓸 이유도 없다 — 함수 평가가 링크 수만큼의 BPR 계산이라 이분법 30회가 AON 한 번보다 싸다.

장점은 명확하다 — 경로를 저장하지 않는다. 메모리가 링크 수에 비례하고, 1970년대 계산기에서도 대도시 네트워크를 돌릴 수 있었던 이유다. 단점도 명확하다. 수렴이 $O(1/n)$ 으로 느리고, 방향점이 항상 다면체의 꼭짓점이라 해 근처에서 지그재그가 심해진다. 상대격차 $10^{-2}$ 까지는 수십 번이면 가지만 $10^{-4}$ 로 가는 데 수천 번이 들고, $10^{-6}$ 은 사실상 도달 못 한다. 개선판으로 이전 방향과 켤레를 이루게 하는 켤레 프랭크-울프(CFW)·이중켤레(BFW) 계열이 있고, 같은 반복 수로 한두 자릿수를 더 번다.

6. MSA와 수렴 판정[편집]

연속평균법(Method of Successive Averages, MSA)은 선탐색을 포기하고 스텝을 $\lambda^n = 1/n$ 으로 고정한다.

$$x^{n+1} \;=\; x^n + \frac{1}{n}\bigl(y^n - x^n\bigr)$$

$\sum \lambda^n = \infty$, $\sum (\lambda^n)^2 < \infty$ 라는 고전적 확률근사 조건을 만족해 수렴이 보장되고, 목적함수를 평가할 필요가 없다. 그래서 아래의 SUE 나 목적함수가 존재하지 않는 비대칭 문제(변분부등식 정식화)에서 사실상 유일한 범용 처방이 된다. 대가는 느린 수렴 — 나중 반복의 스텝이 너무 작아져 기어간다.

수렴 판정은 목적함수로 하면 안 된다. 베크만 목적함수는 물리적 의미가 없고 스케일도 크다. 표준 지표는 상대격차다. 총 통행시간(TSTT)과 현재 통행시간 기준 최단경로 통행시간의 합(SPTT)을 각각

$$\mathrm{TSTT} = \sum_a x_a\, t_a(x_a), \qquad \mathrm{SPTT} = \sum_{rs} q^{rs} u^{rs} = \sum_a y_a\, t_a(x_a)$$

로 두면($y$ 는 현재 통행시간에서의 AON 유량)

$$\mathrm{RG} \;=\; \frac{\mathrm{TSTT} - \mathrm{SPTT}}{\mathrm{TSTT}}$$

이다. AON 이 $\sum_a t_a(x_a) y_a$ 를 최소화하므로 항상 $\mathrm{SPTT} \le \mathrm{TSTT}$ 이고, 균형에서는 쓰이는 경로가 전부 최단경로가 되어 정확히 0 이 된다. 덤으로 같은 양이 베크만 최적값의 하한 $z(x) - (\mathrm{TSTT}-\mathrm{SPTT})$ 을 주므로, 목적함수 값과 함께 보면 최적성 간극을 직접 잴 수 있다. 실무 기준은 대개 $10^{-4}$, 프로젝트 대안 비교처럼 두 시나리오의 차이를 봐야 할 때는 $10^{-6}$ 를 요구하기도 한다.³ 분모를 SPTT 로 쓰는 정의도 유통되므로 문서끼리 비교할 때는 정의부터 맞춰야 한다. 총 수요로 나눈 평균초과비용(AEC)도 자주 쓰이며, 단위가 분이라 해석이 직관적이다.

7. 경로기반·기점기반[편집]

프랭크-울프의 정밀도 한계를 정면으로 깬 것은 상태를 링크가 아니라 경로나 기점 단위로 들고 있는 알고리즘들이다.

계열	대표	상태	도달 가능 격차
링크기반	프랭크-울프, CFW/BFW	링크 유량	$10^{-4}$ 부근
경로기반	경사투영법(1994), 경로균등화	OD 별 활성 경로 집합	$10^{-8}$ 이하
기점기반	기점기반 배정(2002), TAPAS(2010)	기점별 비순환 부분망	$10^{-12}$ 이하

경사투영법(gradient projection)은 OD 마다 현재 최단경로를 기준으로 나머지 경로의 유량을 옮긴다. 경로 $k$ 와 최단경로 $\bar k$ 의 통행시간 차이를 2계 근사로 나눠 이동량을 정하고, 음수가 되면 0 으로 투영한다. 경로 집합을 필요할 때만 늘리는 열 생성 구조라 메모리도 생각만큼 안 든다.

기점기반은 경로를 아예 안 들고, 기점마다 “비순환 부분망 + 그 위의 유량 비율”을 유지한다. 경로 유량이 유일하지 않다는 워드롭 균형의 골칫거리를 우회하면서 극단적으로 정밀한 해를 준다. 요즘 상용 패키지(Aimsun, VISUM 등)가 고정밀 모드로 채택하는 쪽이다.

정밀도가 왜 중요한가. 대안 비교 때문이다. 도로 하나를 넓힌 시나리오와 안 넓힌 시나리오의 링크 유량 차이가 수백 대인데 배정 오차가 수천 대면, 보고서에 적히는 숫자는 정책이 아니라 수렴 잔차다. 실제로 정밀도가 낮은 배정에서 “같은 입력, 같은 코드, 다른 링크 순서”만으로 결론이 뒤집힌 사례가 여러 번 보고됐다.

8. 확률적 사용자 균형[편집]

결정론적 UE 는 모두가 통행시간을 정확히 안다고 가정한다. 현실에서는 인지 오차가 있고, 통행시간이 조금 더 긴 경로도 누군가는 쓴다. 인지된 통행시간을 $C_k = c_k + \varepsilon_k$ 로 두고 각자 자기 인지 최단경로를 고른다고 하면 확률적 사용자 균형(Stochastic User Equilibrium, SUE)이 된다. 다간조·셰피(1977)의 정의다.

$\varepsilon$ 이 검벨 분포면 경로 선택 확률이 로짓 형태 $P_k \propto \exp(-\theta c_k)$ 가 되고, 피스크(1980)가 이 로짓 SUE 의 등가 볼록계획을 찾았다 — 베크만 목적함수에 엔트로피 항을 더한 것이다.

$$\min \ \sum_a \int_0^{x_a} t_a(w)\,dw \;+\; \frac{1}{\theta}\sum_{rs}\sum_k f_k^{rs}\ln f_k^{rs}$$

$\theta \to \infty$ 면 엔트로피 항이 사라져 결정론적 UE 로 되돌아간다. UE 는 SUE 의 극한이라는 뜻이다. 나머지 두 축은 이렇다.

• 다이얼 알고리즘(1971). 로짓 SUE 를 경로 열거 없이 계산하는 고전. “기점에서 멀어지고 종점에 가까워지는” 링크만 남겨 비순환 부분망을 만든 뒤, 전방 패스로 링크 가중치를 누적하고 후방 패스로 유량을 배분한다. 링크 수에 선형이라 지금도 SUE 구현의 기본 뼈대다.
• 프로빗 SUE. $\varepsilon$ 이 다변량 정규분포. 닫힌 형태가 없어 몬테카를로 방법으로 통행시간을 교란시켜 AON 을 반복하고 평균 낸다(셰피·파월 1981). 대신 경로 중복 문제를 자연스럽게 처리한다. 로짓은 거의 같은 두 경로를 독립 대안으로 세는 IIA 문제가 있어 C-로짓·경로크기 로짓 같은 보정이 따로 필요하다.

SUE 는 목적함수를 선탐색하기 어렵거나(프로빗은 아예 없다) 방향점이 확률적이므로, 표준 해법은 거의 항상 MSA 다.

9. 동적 배정과 미시 시뮬레이션[편집]

정적 배정의 결정적 한계는 시간이 없다는 것이다. 첨두 3시간을 한 덩어리로 얹으므로 대기행렬의 형성·소산, 상류 전파, 출발 시각 선택을 전부 못 본다.

동적 교통배정(DTA)은 링크에 시간 차원을 넣는다. 각 시각의 진입·진출 유량과 링크 내 차량 수를 상태로 두고 교통류 모형(셀 전달 모형 같은)으로 전파시키며, 동적 사용자 균형 — 같은 출발 시각의 쓰이는 모든 경로의 실제 경험 통행시간이 같다 — 을 찾는다. 정적 판보다 훨씬 어렵다. 선입선출(FIFO) 제약과 차량 보존을 동시에 만족시키는 것부터 까다롭고, 볼록계획 정식화는 일반적으로 없다. 실무 코드(DYNASMART, DTALite, 상용 메조 모듈)는 대개 “시뮬레이션으로 통행시간 산출 + MSA 로 경로 재배정”의 반복이다.

한 단계 더 내려가면 미시 시뮬레이션이다. 차량 한 대씩을 차량추종·차선변경 모형으로 굴린다. SUMO(오픈소스), VISSIM(비덴만 차량추종 모형), Aimsun 이 대표적이고, 에이전트 기반으로 하루 활동 전체를 공진화시키는 MATSim 계열도 있다. 여기서 균형은 방정식으로 정의되지 않고 날짜 반복(day-to-day replanning)으로 근사된다 — 어제 겪은 통행시간으로 오늘의 경로를 다시 고르고, 점수가 안정될 때까지 며칠을 돌린다. 사실상 MSA 를 에이전트 수준에서 돌리는 것이며, 수렴 판정도 여전히 격차 계열 지표로 한다.

10. 실무 체크리스트[편집]

• 격차를 항상 보고하라. “배정을 수행했다”는 문장은 정보가 없다. 어떤 알고리즘으로 몇 번 반복해 상대격차 얼마에 도달했는지가 재현성의 전부다.
• 시나리오 비교는 같은 격차에서. 두 시나리오의 반복 수가 다르면 차이의 절반은 수렴 잔차다.
• 경로 유량은 결과물이 아니다. 유일하지 않다(워드롭 균형). 보고할 것은 링크 유량과 OD 최소 통행시간.
• 용량 초과 링크를 세라. $x/c > 1$ 인 링크가 많으면 BPR 이 이미 물리 밖으로 나간 것이고, 정적 배정의 결과를 그대로 쓰면 안 된다. DTA 로 넘어가거나 최소한 그 구간을 별도로 표시해야 한다.
• SO 는 공짜로 얻는다. 통행시간 함수를 $t_a + x_a t_a'$ 로 갈아 끼우고 같은 솔버를 돌리면 시스템 최적이 나온다. 그 비율이 무정부의 대가이고, 혼잡통행료 설계의 출발점이다.

11. 관련 문서[편집]

• 워드롭 균형 · 브라에스 역설 · 혼잡 게임 · 무정부의 대가
• 프랭크-울프 · 라인서치 · 볼록 최적화 · 선형계획법
• 다익스트라 알고리즘 · A* 알고리즘 · 벨만-포드 알고리즘 · 네트워크 흐름
• 변분부등식 · 카루시-쿤-터커 조건 · 민감도 해석
• 중력 모형 · 이산 선택 모형 · 몬테카를로 방법
• SUMO · 군중 시뮬레이션 · 경로 계획 · 셀룰러 오토마타

12. Footnotes[편집]

1. $\alpha=0.15$, $\beta=4$ 는 1960년대 미국 고속도로 자료에 맞춘 값이고, 그 뒤 60년 동안 전 세계 도시가 그대로 베껴 쓰고 있다. 도로 등급별로 다시 추정하면 도시 간선도로는 $\beta$ 가 훨씬 작게 나오는 것이 보통인데, 그럼에도 기본값이 안 바뀌는 이유는 “지난 보고서와 비교가 안 된다”는 실무적 압력 때문이다. 물리 상수가 아니라 관행 상수다. ↩

2. LeBlanc, L. J., Morlok, E. K., & Pierskalla, W. P. (1975). Transportation Research 9(5). 프랭크와 울프의 원논문(1956)은 이차계획법을 위한 것이었고 저자들은 도로망 생각을 전혀 안 했다. 20년 뒤 교통공학자들이 “부분문제가 최단경로로 분해된다”는 점을 발견하면서 이 알고리즘의 인생 2막이 열렸다. 요즘은 머신러닝 쪽에서 또 한 번 부활해 3막을 찍는 중이다. ↩

3. 상대격차 $10^{-2}$ 에서 멈춘 배정으로 도로 확장 편익을 계산하면, 잔차가 편익보다 클 수 있다. 미국 여러 주 교통국이 격차 기준을 명시적으로 규정하게 된 계기가 이런 사고들이었다. “수렴은 신에게 맡긴다”가 통하지 않는 몇 안 되는 분야. ↩