전량배정법

왜 배우는가: 전량배정법은 통행배정 기법 중 가장 단순한 기준선이다. 용량을 고려하는 반복배분법과 비교할 때 출발점이 되므로 기법 비교 문항의 바탕으로 자주 쓰인다. 최소경로 트리와 링크 교통량 합산 원리를 익히면 다른 배정 기법도 같은 틀로 이해할 수 있다.

출제 이력: 제122회 1교시 5번, 제89회 4교시 6번

1. 한 줄 정의와 핵심 키워드

전량배정법은 기종점 통행량 전체를 최소비용경로 하나에 배정하는 정태적 통행배정 기법이다.

답안 첫 줄에는 위 정의를 그대로 쓴다. 이 기법은 링크 용량을 고려하지 않으므로 통행배정 기법 가운데 가장 단순한 기준선이 된다. 다른 배정 기법과 결과를 비교할 때도 출발점으로 쓰인다.

핵심 키워드

• 전량배정법(All-or-Nothing Assignment)
• 최소비용경로(Minimum Cost Path)
• 최소경로 트리(Minimum Path Tree)
• 일반화 비용(Generalized Cost)
• 정태적 모형(Static Model)
• 링크 통행량(Link Flow)

2. 개념 풀이

쉬운 말로 하면 통행자 전원이 가장 싼 길 하나만 쓴다고 가정하고, 교통량을 그 길에 통째로 얹는 방법이다. 길을 고르는 일과 교통량을 길 위의 링크에 더하는 일, 두 단계로 나뉜다.

정식 정의는 다음과 같다. 기점존 i와 종점존 j 사이의 통행수요 전량을, 두 존을 잇는 여러 대안 경로 가운데 통행비용이 가장 작은 경로 하나에 배정한다. 링크 용량을 고려하지 않고 최소비용경로에 전량 배정함이 이 기법의 핵심이다.

이 기법에서 통행비용은 통행배정 초기에 각 링크에 부과한 통행시간이다. 교통량이 늘어나도 링크 비용은 바뀌지 않는다. 그래서 링크별 저항함수가 필요 없다.

최소비용경로는 구간별 비용을 합한 값이 가장 작은 경로다. 비용에는 통행시간뿐 아니라 요금 등 일반화 비용 요소를 함께 넣을 수 있다. 한 기종점 쌍의 경로는 이 최소비용경로 하나로 정해진다.

최소경로 트리는 한 출발 노드에서 나머지 모든 노드까지의 최소비용경로를 한 번에 나타낸 수형도다. 다익스트라 알고리즘으로 만들며, 비용이 확정된 노드를 하나씩 늘려 가는 방식이다. 같은 출발 존에서 출발하는 모든 목적지 경로가 이 트리 한 장에서 정해진다.

가상의 예로 A존에서 B존까지 세 경로가 있고 각 비용이 서로 다르다고 하자. 이 경우 통행비용이 가장 작은 경로 하나에 A-B 통행량 전체가 실린다. 나머지 두 경로에는 이 존 쌍의 교통량이 전혀 실리지 않는다.

처리 순서는 다음과 같이 정리된다. 링크에 초기 통행시간을 부과하고, 출발 존마다 최소경로 트리를 만든다. 이어서 기종점 통행량을 트리에서 목적지까지 거치는 모든 링크에 차례로 더한다. 여러 기종점 쌍이 같은 링크를 지나면 그 통행량은 링크마다 합산된다.

이 기법의 특성은 두 가지로 요약된다. 첫째, 한 기종점 쌍의 교통량이 여러 경로로 나뉘지 않으므로 특정 링크에 교통량이 집중된다. 둘째, 링크 용량이 없어 혼잡에 따른 통행시간 증가가 결과에 반영되지 않는다. 이 두 특성이 기법의 장점과 한계를 함께 만든다.

정태적 모형은 시간에 따른 수요 변화나 링크 비용 변화를 한 번의 배정 안에서 되풀이하지 않는 모형이다. 전량배정법은 이 점에서 정태적이며, 입력된 통행시간 하나에 대응하는 단 한 번의 결과를 낸다.

3. 등장 배경과 필요성

교통계획은 도로 투자 전에 장래 교통수요가 망에 어떻게 흐를지 예측해야 한다. 4단계 추정법에서 통행발생, 통행분포, 수단선택을 거친 뒤 마지막으로 수행하는 단계가 통행배정이다. 전량배정법은 이 마지막 단계의 가장 기본적인 기법으로 자리 잡았다.

계획 논리는 다음과 같다. 계획이 목표로 하는 서비스 수준을 링크 통행시간으로 두고 배정하면 링크별 교통량이 나온다. 그 교통량을 처리하도록 필요한 용량을 역으로 산정하면 투자 규모를 정할 수 있다. 이 순서 때문에 용량 제약을 빼고 배정하는 방식이 계획 단계에서 의미를 가진다.

계산상의 필요성도 있다. 존이 여러 개인 망에서는 한 존에서 다른 모든 존으로 가는 경로 수가 빠르게 늘어난다. 그러나 최종적으로 필요한 값은 경로가 아니라 링크 위의 교통량이다. 최소경로 트리로 경로를 한 번에 정하고 링크마다 통행량을 합산하는 방식은 이 목적에 맞는 계산 구조다.

전량배정법은 반复배분법(Iterative Assignment)의 출발점으로도 쓰인다. 반복배분법은 이 기법으로 얻은 교통량에 따라 링크 통행비용을 갱신하고 배정을 되풀이한다. 따라서 용량 효과를 반영한 모형이 나오기 전 단계의 기준이 된다.

이용자 최적 조건인 Wardrop 균형(Wardrop Equilibrium)도 같은 출발점을 갖는다. 이용자가 가장 짧은 경로를 찾고, 아무도 경로를 바꿔 이득을 볼 수 없는 상태가 균형이다. 최소비용경로 배정의 논리가 균형 배정의 가정과 맞닿아 있다.

이 기법은 계산이 간단하고 결과가 명확하다는 장점이 있다. 반면 현실의 혼잡 효과를 무시한다는 한계를 함께 가진다. 그 한계는 7절에서 다룬다.

4. 구성요소·원리·절차

전량배정법은 존(Zone), 노드(Node), 링크(Link), 통행표(O/D Table)로 구성된다. 존은 통행의 기점과 종점이 되는 공간 단위다. 노드는 교차점과 존의 연결점이고, 링크는 노드를 잇는 도로 구간이다. 통행표는 존 사이의 O/D 통행량을 행렬로 담는다.

통행표는 배정의 입력이고 링크별 통행량은 출력이다. 입력은 네트워크 비용과 통행표이며, 출력은 링크별 통행량 하나뿐이다.

전량배정법의 원리는 단순하다. 각 기점에서 모든 노드까지 최소경로 수형도를 만든다. 수형도에서 찾은 최소비용 경로를 따라 기종점 통행량의 전량을 그 경로의 모든 링크에 더하며, 이를 전량 부하라 한다. 용량을 고려하지 않으므로 링크 비용은 배정 중에 바뀌지 않는다.

링크 용량을 고려하지 않고 통행량 전량을 최소비용경로에 배정하는 정태적 기법이다.

수형도는 뿌리 노드에서 가지가 뻗어 나가는 나무 구조다. 각 노드에는 뿌리에서 그 노드까지의 최소비용과 직전 노드가 기록된다. 이 기록을 거꾸로 따라가면 최소경로가 나온다. 다익스트라(Dijkstra) 알고리즘은 이 수형도를 만드는 대표 방법이다.

배정 초기의 링크 비용 c_a는 자유통행시간 t_{0a}로 둔다. 이 비용은 부하된 교통량에 따라 다시 계산하지 않는다. 그래서 1회 배정으로 결과가 정해진다.

링크 a의 배정 통행량은 다음과 같이 쓴다.

$V_a = \sum_{i}\sum_{j} T_{ij}\,\delta_{ij}^{a}$

V_a는 링크 a의 통행량이며 단위는 통행표와 같다. T_{ij}는 기점 i에서 종점 j까지의 O/D 통행량이다. \delta_{ij}^{a}는 링크 a가 i에서 j로 가는 최소경로에 포함되면 1, 포함되지 않으면 0이다.

하나의 링크는 여러 기종점 쌍의 최소경로에 동시에 포함될 수 있다. 그래서 링크 통행량은 포함되는 모든 O/D 통행량의 합이다.

절차는 다음과 같다.

• 링크마다 초기 통행비용을 부여한다. 통행시간 기준이면 자유통행시간을 쓴다.
• 한 기점을 뿌리로 하여 다익스트라 알고리즘으로 최소경로 수형도를 작성한다.
• 수형도에서 각 종점까지의 경로를 따라 해당 O/D 통행량을 경로상 모든 링크에 누적한다.
• 모든 기점에 대해 2와 3을 반복하고 링크별 통행량을 합산한다.

배정은 순방향 흐름으로만 진행하며 되먹임 계산이 없다. 기점 하나당 수형도 하나를 만들면 되므로 존과 노드 수가 적은 네트워크에서는 표로 정리하면 계산이 빠르다.

5. 관련 법령·기준·표준

전량배정법을 직접 규정한 법령 조문은 없다. 이 기법의 기준은 교통공학의 통행배정 이론과 표준식이다. 아래 표는 배정 과정에서 함께 쓰는 기준값이다.

링크 용량 값은 문항이 준 가정이다. 전량배정법은 이 용량을 배정에 반영하지 않으므로 일부 링크의 통행량이 용량을 넘을 수 있다. 이 점이 용량 제약 배정과 비교되는 핵심이다.

BPR 함수는 다음과 같다.

$t_a = t_{0a}\left[1+\alpha\left(\frac{V_a}{C_a}\right)^{\beta}\right]$

t_a는 링크 a의 통행시간, t_{0a}는 자유통행시간, V_a는 링크 통행량, C_a는 링크 용량이다. BPR 함수에서 α는 0.15, β는 4를 쓴다. 이 함수는 V/C 비가 커질수록 통행시간이 빠르게 증가하는 비선형 함수다. 통행시간과 용량의 시간 단위는 서로 맞춘다.

평형 배정에서는 사용자 균형이 목표다. 사용자 균형은 어떤 통행자도 경로를 바꿔 통행시간을 줄일 수 없는 상태다. 사용자 균형은 Wardrop 조건으로 설명된다.

전량배정법의 결과는 이 조건을 만족하지 않을 수 있다. 용량이 작은 링크로 통행이 몰려도 비용이 바뀌지 않기 때문이다. 계획 단계에서는 목표 서비스 수준의 통행시간으로 통행량을 구하고, 그 통행량으로 필요한 용량을 산정하는 데 쓰인다는 주장이 있다. 법령 기준이 없으므로 답안에서는 이론 기준과 표준식으로 근거를 댄다.