paper · 2026
도로명주소 계층 위 Dual Graph 기반 제약 효율 라우팅
표준 라우팅 그래프는 회전 금지·시간대·차량 종류 같은 제약마다 교차로 노드를 쪼갠다. 노드 수가 곱셈으로 늘어난다. Dual Graph는 제약을 엣지 속성으로 인코딩한다 — 노드 수는 고정. 서울에서 구 내부 라우팅 0.9ms, 구 간 계층 라우팅 3.84ms — 평면 Dijkstra 대비 5.3배.
이 논문이 한 일
회전 금지·시간대 규정·차량 종류 같은 실세계 제약이 가해지면, 기존 Primal Graph 표현에서 노드 폭증이 일어난다. 제약이 걸린 교차로마다 via-node로 분리해야 하고, 그래프가 제약 수에 대해 초선형으로 부푼다. 결합 제약(자율주행의 표준 환경)에서는 실시간 지연 예산을 일상적으로 위반한다.
이 논문은 한국 도로명주소 3계층(대로 / 로 / 길) 위에 Dual Graph를 구성한다. 도로가 노드, 교차로가 엣지. 제약은 엣지 속성으로 들어간다 — 노드 수 |V_D|는 어떤 제약을 추가해도 변하지 않는다.
정리
Dual Graph: 모든 k ≥ 0에 대해 |V_D(k)| = |V_D|.
Primal Graph (노드 분리 시): |V_P(k)| ≈ |V_P| · d̄^(k/d̄). (d̄ = 평균 교차로 차수, k = 제약 종류 수.)
강남구의 경우 (평균 차수 12.6, Primal 158, Dual 876), Dual이 Primal보다 작아지는 임계점은 약 2.1개 제약 — 실세계 도시 환경에서는 일상적으로 초과된다.
| 회전 금지 비율 | Primal 노드 | Dual 노드 | Dual 우위 |
|---|---|---|---|
| 0% | 158 | 876 | — |
| 1% | 203 | 876 | 4.3× |
| 5% | 561 | 876 | 1.6× |
| 10% | 1,997 | 876 | 2.3× |
| 20% | 25,243 | 876 | 28.8× |
실측 결과 — 서울 (25개 자치구)
서울 전체 Dual Graph: 13,633 노드, 3,378 backbone 엣지(road_conn), 18,995 terminal 엣지(intrsct_index).
| 범위 | 노드 | p50 | p95 | 평균 pop |
|---|---|---|---|---|
| 강남구 (구 내부) | 876 | 0.90ms | 1.58ms | 558 |
| 서울 — 단일 평면 그래프 | 16,107 | 20.41ms | 43.92ms | 5,991 |
| 서울 — 계층 구조 | 3,355 | 3.84ms | 9.38ms | 219 |
계층 구조는 사전 계산된 boundary shortcut(sig_paths)와 구간 엣지(sig_exit)를 사용한다. 구 간 라우팅이 16,107개가 아닌 3,355개의 boundary 노드에 대한 Dijkstra로 환원된다. 5.3배 가속은 RNADDR 체계의 행정 분할에서 직접 온다 — 자치구 경계가 사전 계산의 자연스러운 분해점을 제공한다.
위상학적 재구성
부수적 관찰이지만 어쩌면 가장 큰 함의가 있는 부분: 기존 RNADDR 체계는 점(건물 주소)을 일차 관리 객체로 다룬다. 도로와 자치구는 식별자일 뿐 관리 entity가 아니다.
이 작업은 도로를 line attribute A_1(r)을 갖는 1-셀로, 자치구를 face attribute A_2(f)를 갖는 2-셀로 형식화한다. PostGIS나 GIS 서버를 요구하던 쿼리들 — 이 자치구에서 정체 임계치를 넘은 도로는?, 이 구역의 접근성 점수는?, 이 실내 입구에서 도보 10분 안에 도달 가능한 모든 건물 — 이 attributed cell complex 위의 일급 연산이 된다.
상태
3편 시리즈 중 둘째. 한국 특허출원 번호 10-2026-0039486 (2026-03-05 출원). PCT 국제 출원은 우선권 기간 내 예정.