Ⅰ. 서 론

2017년 10월 기준으로 수도권통합대중교통요금체계에 참여하고 있는 철도역사는 총 588개, 이중 92개는 환승역이며 특히 복수노선이 집산하는 환승역은 86개이다. 평일기준 약 20,000,000(trip) 이상 발생하고 있으며 철도네트워크는 이중 약 8,000,000(trip) 이상 담당하고 있다. 개별승객에게 부과되는 요금은 年기준 약 8조로 추산되고 있으며 대부분 요금체계에 참여하고 있는 대중교통운송기관의 수입금으로 전환된다. 현행 5회까지 수단간 환승요금이 할인되는 체계에서 서울7개, 경기8개, 인천12개 버스운송기관에 日기준으로 수입금이 배 분된다. 한편 11개 철도운송기관에 대해서는 진입역사의 단말기운영기관에 임시로 보관되며 향후 3-5년 단위 로 수입금배분절차가 시행된다. 철도수입금배분은 승객이 이용한 경로를 추정하여 운송기관기여도를 판단하 여 결정된다. 따라서 교통카드단말기와 연관된 수도권철도수입금배분에서 최적경로선택알고리즘의 역할은 매우 중요하다. 철도수입금배분문제는 단순한 노드(역)간의 경로탐색이 아닌 교통카드단말기ID(이하 단말기 ID)간의 탐색문제로 인식되어야 한다.

단말기ID간 경로탐색문제는 민자철도운영기관(이하 민자기관)의 진입과 함께 새로운 해법의 적용이 필요 하게 되었다. 기존 3개 공사기관(서울교통공사, 인천교통공사, 한국철도공사)만 운영되던 상황에서는 환승역 에 대한 고려가 필요하지 않았다. 따라서 경로탐색은 출발역단말기ID와 도착역단말기ID OD간 최적경로를 발견하는 문제로서 링크표지확정알고리즘(Dijkstra, 1959;Kirby and Potts, 1969;Namgeung et al., 1998;Lee, 2004)의 적용이 가능했다. 그러나 민자기관은 요금배분에 대한 투명성을 확보하기 위해 환승단말기를 운영 하고 있다. 따라서 단말기ID로 나타나는 승객이동패턴이 연계통행(Chain Trip)으로 구성되어 Chain OD를 반 영하는 방안이 요구된다. <Fig. 1>에서 민자노선진입전(a)에 ‘2호선 사당’과 ‘5호선 충정로’는 ‘0226’과 ‘2532’ 의 OD 탐색문제에 해당한다. 그러나 민자노선진입후(b)는 ‘9호선 동작’과 ‘9호선 당산’의 환승단말기ID가 포 함되어 2개 이상의 단말기ID가 연쇄적으로 나타난 ‘0226’-‘0432’-‘4113’-‘2532’의 Chain OD 탐색문제로 전환 되었다. (b)의 상황에서 경로탐색은 9호선 ‘0432’-‘4113’을 부분경로(Partial Path)로서 반드시 통과하면서 ‘0226’-‘0432’의 경로탐색과 ‘4113’-‘2532’의 경로탐색을 함께 고려하는 문제로 확대된 것이다. 새로운 경로탐 색문제는 (복수)민자노선을 통과하면서 최초단말기ID와 최종단말기ID를 연결하는 최적조건(Optimality Condition)을 만족하는 최적경로를 구축하는 알고리즘을 정립하는 것이다.

본 연구는 수도권철도네트워크를 대상으로 단말기ID Chain OD를 순차적으로 연결하는 링크표지확정기반 최적경로탐색알고리즘을 제안하고 최적조건이 성립함을 증명한다. 알고리즘은 다음 3가지 최적경로탐색기법 –1) 최초단말기ID-민자노선출발링크(노드-링크), 2) 민자노선출발링크-민자노선도착링크(링크-링크), 3) 민자 노선도착링크-최종단말기ID–으로 이루어진다.

우선 2장은 민자노선진입전의 수도권철도네트워크를 가정하고 단말기ID로 구축된 철도네트워크와 진입단 말기ID와 진출단말기ID OD간 링크표지기반 최적경로탐색문제를 개관한다. 3장은 본 연구의 핵심주제로서 민자노선진입후 단말기ID로 구성된 Chain OD를 연속적으로 연결하는 3가지 알고리즘을 제안하고 가산성경 로비용(Additive Path Cost)에서 최적조건의 성립여부를 증명한다. 4장은 단말기ID를 적용하여 수도권철도네 트워크를 구축하고 민자노선진입 전후를 가정하여 사례연구를 시행한다. 마지막으로 5장은 수도권요금체계 의 상황변화에 따른 경로탐색알고리즘의 향후 발전방안을 검토한다.

Ⅱ. 이론적 배경

1. 개요

우선 복수의 교통카드단말기ID를 고려하여 ‘역사명’으로 단일화된 노드를 대상으로 수도권도시철도네트 워크를 구축하는 기법을 검토한다. 다음으로 환승분류를 두 링크가 만나는 노선환승과 출발역과 도착역에서 발생하는 역사환승의 개념을 소개한다. 마지막으로 기존의 링크표지기반 알고리즘이 역사환승을 반영하지 못하는 한계를 최소화하기 위하여 노선환승자료를 참조하는 알고리즘을 살펴본다.

2. 카드단말기ID와 철도네트워크

단말기ID는 철도역사의 승객이동을 의미한다. 2호선과 4호선이 환승하는 ‘사당’역의 단말기ID는 ‘0226’, ‘0433’이고, 2호선과 5호선이 환승하는 ‘충정로’역은 ‘0243’, ‘2532’이다. 따라서 역명은 복수의 단말기ID를 구 성하는 집합개념이다 <Fig. 2>.

<Fig. 3>과 같이 역명을 연결하면 링크자료가 구축된다. ‘사당’역을 중심으로 4호선의 ‘총신대입구’와 ‘남 태령’이 2호선의 ‘방배’와 ‘낙성대’의 양방향 링크가 연결되어 총 8개 링크가 생성된다. ‘충정로’역도 2호선의 ‘아현’과 ‘시청’ 및 5호선의 ‘애오개’와 ‘서대문’으로 총 8개 링크가 생성된다.

3. 철도통행: 직승직하, 노선환승, 역사환승

단말기ID로 구축된 철도네트워크 통행은 직승직하, 노선환승, 역사환승으로 나타난다. 직승은 <Fig. 4>의 ‘사당’역 사례와 같이 Tag-In 단말기ID와 초승열차의 탑승노선이 일치하며 계단, 에스컬레이터와 같이 수직 보행시설을 이용하여 승강장에 접근한다. 4호선 ‘사당’의 ‘0433’ 단말기ID와 섬식승강장(Island Platform)의 4 호선 플랫폼으로 직접 접근하며, 2호선 ‘사당’의 ‘0226’ 단말기ID와 상대식승강장(Side Platform)의 2호선 플랫 폼으로 직접 접근한다. 하차의 경우도 역으로 동일하게 적용된다. 직하는 직승과 반대로 하차열차노선과 Tag-Out 단말기ID가 동일하다.

노선환승은 열차하차 및 열차승차의 패턴을 보이며 승차역과 하차역이 아닌 중간환승역에서 발생한다. <Fig. 5>의 사례와 같이 2호선 ‘사당’에서 4호선 ‘사당’으로 노선환승은 2가지 방향으로 나타나며 이는 2호선 ‘사당’의 섬식승강장구조를 반영한 경로이다. 노선환승은 보행통로 및 계단, 에스컬레이터와 같이 수평 또는 수직보행시설을 이용하여 이동하나 수도권 환승역사의 상당부분은 환승거리가 이격되어 수평보행시설의 의 존도가 높다.

역사환승은 출발역과 도착역에서 단말기ID와 열차노선이 다른 경우에 발생한다. 출발역 Tag-In 단말기ID 와 초승열차노선이 다르면 출발역사환승(Departure Station Transfer), 최종하차열차와 도착역 Tag-Out 단말기 ID 노선이 다른 상황은 도착역사환승(Arrival Station Transfer)이다. <Fig. 6>의 ‘사당’은 2호선에서 4호선으로 의 출발역사환승을 보여주고 있다. 2호선 단말기ID ‘0226’을 Tag-In하고 4호선 열차를 타기위해 이동하며 노 선환승과의 차이는 Tag-In 단말기ID와 수직보행시설을 이용한 접근보행에 있다.

4. 노선환승 및 역사환승을 반영한 링크표지기반 최적경로탐색

‘역명’으로 구축된 철도네트워크에서 링크표지기반경로탐색기법은 직승페널티(T_rb = Acc T_r + H_b/2)와 직하 페널티(T_as = Egg T_s) 및 노선환승페널티(T_ab + H_b/2)에 대하여 적용이 가능하다. (식1)은 출발역 r과 도착역 s 에 대하여 링크표지기반최적경로탐색과정을 나타내고 있다. r과 s는 역명이 노드에 해당함으로 역사환승에 대한 페널티는 TagIn(TagOut)단말기ID와 초승(최종)열차노선에 대한 비교가 필요하다.

여기서

Lee(2018)는 환승역에서 단말기ID와 노선을 연결하기 위해서 가상링크를 통한 네트워크확장이 요구되지 않는 알고리즘을 제안했다. 알고리즘의 기본구조는 역사환승을 노선환승과 비교하여 접근/이탈시간에 차이 가 있고 환승이동경로는 노선환승과 일치한다. 따라서 출발역 및 도착역에서 나타나는 방향별 노선환승자료 와 일치하는 경우 노선환승페널티를 가감없이 적용하는 방안이다. (식2)는 역사환승페널티를 반영하는 링크 표지기반최적경로탐색을 나타내며 단말기ID와 링크의 노선정보를 나타내는 Φ ( r Z ) , Φ ( s Z ) , Φ ( a ) , Φ ( b ) 에 대하여 비교를 통해 역사환승페널티(T_ab)에 검색이 가능하다.

여기서

여기서 참고로 검토할 사항은 노드표지기반알고리즘이 역사환승 및 노선환승을 반영하는 한계에 대한 설 명이다. 크게 두 가지 문제점에서 노드표지기반알고리즘은 수도권철도네트워크 적용의 한계를 설명한다. 우 선 노드표지기반알고리즘은 3개의 노드사이에서 표현되는 환승페널티(회전)가 존재하는 경우 최적조건을 보 장하지 못한다. 따라서 이 알고리즘은 링크중간에 네트워크 확장을 위해 가상노드의 구축을 요구한다. Choi(1995)는 인접된 교차로에서 회전제약이 존재하는 상황을 가정하여 최적조건을 만족하지 못함을 증명하 였다. 다른 하나는 수도권철도네트워크 자체적으로 복사링크(Duplicate Link)를 포함하는 구조라는 측면이다. 노드표지는 두 개의 노드로 구성된 링크(노드→노드)에서 하나의 링크만 나타나야 하나, ‘을지로3가’→‘동대 문역사공원’에서 2호선과 5호선을 노드로 하여 2개의 링크가 나타난다. 따라서 수도권철도네트워크의 완결 성을 보전하기 위한 최선의 방법은 링크표지기반알고리즘이 최적조건을 만족하는 네트워크를 구축하는 방 안으로 귀결된다. Fig. 7, 8

Ⅲ. 단말기ID Chain OD를 고려한 링크표지기반 최적경로탐색

1. 개요

공사운영기관의 단말기ID는 출발역과 도착역에서 나타난다. 반면 민자운송기관의 단말기ID는 출발역과 도착역에 환승단말기ID를 별도로 운영한다. 따라서 두 기관에서 나타나는 통행유형을 정리하면 <Table 1>과 같이 7가지로 구성된다. 여기서는 단순하게 표현하기 위해 민자노선은 1회만 통행한 것으로 적용하였다. 그 러나 실제 수도권철도네트워크는 9호선-공항철도 등 조합이 매우 다양하게 나타난다.

2. 순차적 링크표지기반 경로탐색기법

링크표지기반경로탐색알고리즘은 가산성경로비용(Additive Path Cost)조건에서 최적조건(Optimality Condition) 을 만족한다. 따라서 순차적으로 환승 및 링크통행비용의 경로탐색과정이 진행되면서 합산되면 최적조건을 만족한다. 그러나 비가산성경로비용(Non Additive Path Cost)은 순차적으로 링크 및 환승비용이 합산되는 과 정에서 최적조건의 성립이 보장되지 않는다(Gabriel and Bernstein, 1997;Shin and Baek, 2016).

Lee(2018)가 제안한 링크표지기반최적경로알고리즘은 가산성경로비용을 조건으로 역사환승페널티를 노선 환승페널티로 대처하는 방안을 적용하였다. 여기서는 Lee(2018)가 제안한 알고리즘을 단말기ID Chain OD를 따라 환승페널티가 적정하게 반영되는지 여부가 알고리즘의 최적조건을 규명하는 핵심이다. 서론에서 제시 된 <Fig. 1-b>의 사례를 알고리즘에 적용하기 위해 9호선 민자노선에서(급행노선을 제외하고) 역별로 세분화 된 노선선택과정은 <Fig. 9>와 같다. <Fig. 10>은 <Fig. 9>를 역사환승페널티, 노선환승페널티, 링크시간으로 단순화한 네트워크이다.

<Fig. 10>에서 나타나는 역사환승페널티, 노선환승페널티, 링크비용(차내시간, 대기시간)을 모두 순차적으 로 합산하는 방법은 <Fig. 11>과 같이 3가지 링크표지기반최적경로탐색으로 분류된다.

<Fig. 11>은 민자노선 시작링크와 도착링크까지 경로탐색이 포함되므로 노드→노드문제로 표현하면 <Fig. 12>와 같다. 여기서 민자노선통과제약을 만족하면서 출발/도착역단말기ID로 전환된 최적경로비용은 π ( r Z ) π ( s Z ) = π ( r Z ) ( x ) + π − ( 1 ) ( 2 ) + π ( x ) ( s Z ) 이다. 여기서 π^-(1)(2) 민자노선구간을 탐색해서 얻은 최적통행비용을 의미 한다. 위의 문제는 2개의 가상링크와 하나의 가상노드(여기서는 Ⓧ)를 도입하여 네트워크를 간단하게 확대하 는 문제로 귀결된다.

<Fig. 13>은 민자노선이 2개로 나타나는 경우를 상정하는 것으로 개별민자노선에 각각 가상노드를 하나씩 (여기서는 Ⓧ, Ⓨ)를 도입하여 노드→노드문제로 표현한 것으로 2개의 민자노선통과제약을 만족하면서 최적 경로비용은 π ( r Z ) π ( s Z ) = π ( r Z ) ( x ) + π − ( 1 ) ( 2 ) + π ( x ) ( y ) + π − ( 3 ) ( 4 ) + π ( y ) ( s Z ) 이다.

Ⅳ. 사례연구

1. 개요

2017년 10월 기준 688개 단말기ID로 구축된 철도네트워크에 민자노선통과제약을 조건으로 사례연구를 시 행한다. 네트워크는 588개 역명노드, 86개 환승노드, 1,332개 링크로 구성되며, 노선환승은 824개로 구성된다. 사례연구는 두 가지 관점으로 시행된다. 첫 번째는 민자기관을 1회 통과하여 민자환승단말기 TagIn 및 TagOut이 각각 1회 나타나는 상황으로 2012년 공사 및 민자기관 카드자료를 합산하는 과정을 파악하여 도출 하였다. 두 번째는 민자기관을 2번 통과하는 상황으로 TagIn 및 TagOut의 민자환승단말기가 각각 2회가 나타 나는 상황으로 향후 민자기관의 진입으로 철도네트워크가 복잡해지는 경우를 가정하였다.

2. 공사 → 민자 → 공사

<Fig. 1>의 2호선 ‘사당’과 5호선 ‘충정로’ 사이에 9호선 제약(‘동작’-‘당산’)의 단말기ID순서(‘0226’, ‘0431’, ‘4113’, ‘2532’)에 대하여 순차적 링크표지기반 최적경로알고리즘 결과를 도출하였다.

3. 공사→민자→공사→민자→공사

여기서는 분당선 ‘미금’과 5호선 ‘목동’ 사이에 신분당선 제약(‘정자’→‘강남’)과 9호선 제약(‘고속터미널’ →‘여의도’)의 단말기ID순서(‘1858’, ‘4312’, ‘4307’, ‘4123’, ‘4115’, ‘2521’)에 대하여 순차적 링크표지기반 최 적경로알고리즘 결과를 도출하였다.

Ⅴ. 결 론

수도권철도수입금배분과 같이 첨예한 논쟁이 요구되는 상황에서 단말기ID간 경로탐색문제는 민자기관진 입과 함께 새로운 접근방법을 필요로 한다. 수입금배분의 핵심이 되는 경로탐색에서 출발/도착역단말기ID와 도착역단말기ID 경로탐색과 함께 민자노선제약을 반영하는 문제로 확대되었다. 본 연구는 단말기ID Tag에서 획득 가능한 정보를 바탕으로 역사환승페널티와 함께 민자제약을 극복하는 순차적 링크표지기반 최적경로 탐색기법을 제안했다. 가산성경로비용의 철도네트워크에서 알고리즘의 최적조건이 성립됨을 예시했다. 사례 연구를 통해 알고리즘의 적용성에 대해 논의했다.

철도수입금배분문제는 최적경로와 함께 유사경로를 탐색하는 문제로 해결책이 요구된다. 수입금배분문제 에 근본적인 적용은 단말기ID Chain OD로 구축된 네트워크에서 유사경로탐색기법으로 확대하는 방안이 검 토되어야 한다. 본 연구를 통해 기초적인 접근방법을 제시하는 측면에서 평가된다고 생각된다.

본 연구에서 제시한 링크표지기반알고리즘은 수도권통합요금체계의 수입금배분의 로직으로 탄생했으나 확장성에 대하여 논의하면 다음과 같다.

우선 본 연구에서 메트로9호선의 급행열차 혼용방식과 같이 완행 및 급행노선이 동시에 운행되는 상황은 고려하지 않았으나 네트워크 확장을 통한 기본로직은 유사하다. 다만 교통카드단말기ID가 동일하게 적용되 므로 경로선택에 의한 수입금정산에 미치는 영향은 없는 것으로 나타난다. 향후 GTX, KTX, 신교통수단의 진입에 의한 수도권철도네트워크 확장에 따른 다양한 운영체계에 대비하기 위하여 급행 및 완행철도네트워 크에 대한 알고리즘의 개발방안이 요구된다.

또한 연구에서 제시한 링크표지기반알고리즘은 수도권통합대중교통요금체계에서 실제로 통행한 승객의 경로정보가 민자환승자료를 통해 나타나는 현상을 최적조건으로 모사하기 때문에 승객의 철도경로선택행태 를 검증하는 방안으로서 가능성이 높다.

마지막으로 제시된 링크표지기반알고리즘은 역사에서 나타나는 승객의 이동패턴을 보행 및 열차로서 평 가가 가능하므로 역사내부의 입체적인 네트워크체계가 구축되면 화재승객대피, 열차스케쥴링, 보행인프라평 가방안의 시뮬레이션 모형으로 활용이 가능하다.

연구의 보완을 위해 추가적으로 고민할 문제는 민자기관의 자료공유이다. 현재 환승자료는 민자기관에서 보관하고 있고 수입금배분을 위한 용도로만 사용된다. 따라서 자료의 효과적인 접근을 위한 운영주체간 새 로운 협의가 필요할 것으로 판단된다.