Ⅰ서 론
대중교통 이용승객에게 통행시간이 많이 소요되 도 환승회수가 적은 통행경로를 선호하는 현상이 나타난다. 이러한 행태를 반영해서 수도권통합대중 교통체계에서 최소시간뿐만 아니라 최소환승경로 정보도 함께 제공하는 시도가 진행되고 있다. 대중 교통을 이용하는 승객행태의 뒷면에는 환승하기 불 편함과 같은 주관적인 요소의 반영이 필요함을 알 수 있다.
본 연구에서 제안하는 ‘누적환승함수’이라는 용 어는 환승에 대한 ‘느낌’을 정량화하는 개념이다. 누적환승함수는 환승회수가 늘어날수록 개별 환승 자체에서 발생하는 실제비용보다 더 많이(적게) 인 식되도록 한다. 간단하게는, 출발지부터 환승이 발 생하는 시점까지 환승의 영향을 파라메타로 반영하 는 방법이 있으며, 선형 및 비선형함수 등 다양한 형태로 적용도 가능하다.
그러나 누적환승함수가 포함된 통행비용에서 경로탐색문제의 최적조건이 성립하지 않을 가능 성이 존재한다. 누적환승함수가 포함되면 표지확 정(Label Setting)과정에서 통행비용을 출발지부터 표 지까지의 다시 산정해야한다. 따라서 기존의 동적계 획법(Dynamic Programming)의 최적원리(Optimality Principle) 조건인 현재 및 이전표지 관계조건[1]이 모두 성립한다고 볼 수 없다. 이 문제는 경로열거문 제를 발생시키는 비가산비용(Non Additive Cost)의 형 태가 될 가능성을 포함한다[2]. 따라서 최적경로탐색 이 완전한 해를 도출하는 방안으로서 경로열거와 함 께 최적해를 선정하는 적절한 방안이 필요하다. 이 러한 문제 때문에 비가산성비용을 포함하는 최적경 로탐색은 문제 유형별로 접근하는 방식을 채택하고 있다[3, 4].
본 연구는 한정된 경로집합의 생성을 통하여 최 적경로를 선정하는 효과적인 방안을 제안한다. 제 안된 기법은 세 가지 측면 - 1) 복수경로탐색의 적 용, 2) 최적해의 선정, 3) 실제 교통망에의 적용 - 에서 검토된다. 이를 위해 복수경로탐색을 위해서 는 제안된 K경로탐색 알고리즘은 유입링크기반 전
체경로삭제기법[5, 6]을 통하여 최적해의 포함을 위한 실제 교통망에서 상한(Upper Bound)에 대하여 논의한다.
이 연구는 다음과 같은 순서로 진행된다. Ⅱ장에 서 누적환승함수가 포함되는 상황에서 최적경로탐 색이 성립되지 않는 사례를 설명한다. Ⅲ장에서는 최적경로탐색을 위해 K경로탐색 알고리즘을 활용 하는 방안을 제안한다. Ⅳ장에서 결론과 연구과제 를 요약한다.
Ⅱ최적경로탐색과 누적환승함수
식(1)은 노드표지기반 최적비용을 탐색하는 과정 을 나타낸다. <Fig. 1>은 식(1)을 도식화한 내용이 다. 노드기반 최적경로탐색 알고리즘의 해를 도출 하는 알고리즘 노드표지갱신[7]과 표지확정[8] 알고 리즘이 알려져 있다. 표지갱신은 출발지부터 탐색 이 진행되는 순서대로 다음 탐색노드를 결정하는 방법 (First In First Out)이다. 표지확정은 출발지에 서 탐색된 노드 중에서 가장 비용이 적은 노드를 다음 탐색노드로 결정한다.
r :
출발노드
(i,j):(시작노드, 도착노드)로 구성된 링크
cij :링크(i,j)의 통행비용
:r에서 j까지 최적경로비용
식(2)은 환승비용(dab)을 포함하는 링크표지기반 최적비용을 탐색하는 과정을 나타낸다. <Fig. 2>은 식(2)을 도식화한 내용이다. 최적경로탐색에서 dab 가 상수인 경우에 대해서 최적의 해를 도출하는 방 안에 대해서는 연구되었다[9, 10].
주요개념은 탐색링크집합에서 가장 적은 비용의 링크를 선정하여 링크의 도착노드를 시작노드로 하 는 링크표지를 확정한다. 이 방법을 이용해서 표지 를 확정하는 과정은 기본적으로 노드표지 확정과정 과 동일하다. 단지 출발지와 연결된 링크표지를 링 크비용으로 확정표지화하고 출발 링크들에서 최소 비용링크를 다음탐색링크로 선정하는 것이 차이점 이다.
a, b :
2개 노드(시작, 도착)로 구성된 링크
:r에서 b의 도착노드까지 최적경로비용
dab :a에서 b로의 환승비용
cb :b로의 통행비용
:a의 도착노드가 시작노드인 링크집합
누적환승함수 사례로서 식(2)의 dab가 식(3)과 <Fig. 3>의 로 변경된 상황에 대하여 최적경로수 식이 성립을 검토한다. dab는 a에서 b로 진행하는 환 승비용을 의미한다. 그러나 는 a에서 b로 환승하 면서 출발지 r에서 누적되는 환승비용으로 적용된다.
:
r에서 출발하여 a에서 b로의 누적환승비용
우선 를 누적환승함수로 간단하게 적용하는 방안은 환승계수(Transfer Parameter)를 도입하는 것 이다. <Fig. 4>의 는 환승회수에 대하여 일정한 값으로 나타난다. 출발지부터 경로를 따라서 환승 이 발생하는 순간 환승회수를 계산해서 비용에 당 해 환승비용 dab 에 영향력을 나타내는 수치 를 반영하는 방안이다.
:
r에서 출발, a에서 b로 환승회수에 대한 계수
환승계수로 구축된 누적환승함수를 포함하여 토 이네트워크에 대하여 최적조건이 성립하지 않는 상 황을 검토한다. dab =2인 상황에 대하여 <Fig. 5>의 비용을 포함한 링크 8개, 노드 7개, 환승노드 5개로 구성된 토이네트워크에 최적경로탐색과정 적용한 다. 이때 는 <Fig. 6>와 같이 최대 4번까지 환승 파라메타 값으로 각각 1, 2, 4, 8 이다. r에서 b까지 경로는 3개 (A, B, C)이다.
위의 네트워크에서 최적조건이 성립하기 위해서 는 r에서 a까지의 최적경로는 반드시 r에서 b까지의 최적경로에서 b링크를 제외한 경로이어야 한다. <Fig. 7>에서 A, B, C 3개 경로에 대하여 a까지 비 용은 각각 39, 33, 43으로 B경로가 최적경로이다. 그러나 a에서 b로 환승이 발생하는 순간 비용이 48, 50, 46으로 C경로가 최적이 되는 역전현상이 발생 한다. 그럼에도 최적조건에 기반한 표지확정은 최 종적으로 B경로가 최적이 되도록 진행된다.
Ⅲ경험적 최적경로탐색방안
<Fig. 7>의 사례에서 볼 때, 누적환승함수 포함으 로 C경로가 최적경로로 올바르게 판단하는 방법은 A, B, C 세 경로를 열거하여 최적이 되는 경로선택 으로 가능하다. 일반적으로 경로의 열거는 K경로탐 색기법을 활용하나, 최적조건의 불일치로 인한 문 제는 표지확정 문제를 발생시키며, 이는 탐색오류 및 경로중복 등의 문제로 확산될 가능성이 존재한 다. 따라서 적합한 방안중 하나는 K경로탐색알고리 즘을 이용하여 적정한 대안경로집합을 구성하고 최 적경로를 확인하는 방법이다.
본 연구에서 제시하는 방법은 ‘최적경로집합조 건’의 개념이다. ‘최적경로집합조건’이란 하나의 출 발지에서 목적지까지 연결하는 복수의 경로로 구성 된 경로집합으로서 모두 다른 경로로 구성되며, 모 두 올바른 경로비용정보를 보유한다는 것이다. 최 적경로집합조건의 개념이 필요한 이유는 링크표지 확정과정에서 최적조건이 만족되지 않아도 적합한 경로집합만 구성되면 그 경로집합에서 최적경로를 도출한다는 확신을 구하고자 하는 필요성에 기인한 다. 다른 의미로서, 경로에 대한 적합한 통행비용이 도출되지 않더라도, 그 경로집합의 구성이 만족하 다면 새롭게 통행정보를 구성할 수 있다는 개념이 다. 이는 이미 도출된 경로를 따라서 비용을 재확인 하는 방법으로 적용이 가능하다.
본 연구에서 최적경로집합조건을 만족하도록 구 성하는 K경로탐색기법은 유입링크기반 전체경로삭 제기법[6, 7]을 변형한 것이다. 전체경로삭제기법은 출발지와 도착지가 정해진 두 지점에서 K개의 경 로를 구축하는 기법으로 이전 네트워크(N)에서 기 탐색된 경로를 모두 제거한 네트워크(N’)를 구축하 여 경로를 탐색하는 방안이다. N’에서는 기존에 탐 색된 경로가 삭제되었으므로 누적환승함수가 포함 되어도 표지확정 실패에 의한 경로중복문제는 발생 하지 않는 장점이 있다.
유입링크기반 전체경로삭제 알고리즘은 네트워 크 N에 대하여 2단계의 세부알고리즘을 수행한다 [5]. (1) 두 지점간 최적경로 p 발견을 위한 최적경 로알고리즘과, (2) 새로운 네트워크 N’을 생성시키 기 위한 경로삭제알고리즘이다.
개략적 개념은, 우선 최적경로 p가 탐색되면, 그 p경로를 네트워크 N에서 삭제하여 다시 최적경로 탐색을 수행한다는 것이다. 이때 새로운 노드와 링 크를 네트워크 N에 추가하여 구성된 확장된 네트 워크 N’은 경로 p를 제외한 모든 경로의 탐색이 가 능하게 구축된다. N1을 기본네트워크로 하여 순차 적인 K개의 경로를 탐색한다는 것은 {N1,N2, …,NK} 의 순차적인 네트워크를 구축함을 의미하며, 이 경 우 j번째 네트워크 Nj,로부터 j번째 경로 pj가 탐색 된다. 이 알고리즘의 경우 N의 링크 및 노드의 영 구표지는 N’에서 영구표지로 남아있으며, N에서 삭 제된 p의 부분경로가 N’의 최적경로설정에 포함된 다는 사실에 근거하여 (K-1)번의 최적경로알고리즘 수행을 절약할 수 있다.
경로삭제알고리즘의 수행과정을 나타내기 위한 표식(Notations)으로서 네트워크 N의 경로 p는 다음 과 같은 노드의 순서로 표현된다.
여기서 υ0 = r는 출발지, υm = s는 도착지 노드 이며 m ≥ 3. 어느 노드 u와 연결된 유입링크 (Incoming Links) 집합은 링크 및 노드집합 A 및 Ξ에 대하여 다음과 같이 정의한다.
경로 p를 삭제하여 네트워크 N’을 생성하기 위하 여 새로운 노드를 추가하고, 이들 노드에서 유입링크 를 연결하며, p의 첫 번째 경로를 삭제하는 것이다. 알고리즘의 수행과정은 다음과 같다.
단계1
단계2
단계3
<Fig. 8>은 유입링크기반 전체경로삭제기법을 나 타내며, N’에 대하여 최적경로를 탐색하지 않고 링 크 및 노드표지를 확정한다.
<Fig. 9>은 새롭게 제안된 전체경로삭제기법이 다. 일단 최적경로로 가정하고 표지확정을 진행한 다. 탐색된 경로에 대하여 비용 등 정보를 갱신한 다. 또한 현재까지 구축된 링크 및 노드표지 불확정 성을 가정하여 출발지와 도착지를 연결하는 새로운 경로를 경로탐색을 통하여 구축한다. 최종적으로 구축된 경로 K개에 대하여 최적경로를 선정한다.
<Fig. 10>은 <Fig. 5>의 네트워크 N에 대하여 N1 에 구축한 것이며, <Fig. 11>은 N1에 대하여 최적경 로를 탐색한 것이다.
<Fig. 12>은 <Fig. 11>의 네트워크 N1에 대하여 탐색된 B경로와 N1에 대하여 유입링크기반 네트워 크변형으로 N2을 구축한 것이다.
<Fig. 13>은 N2에 대한 최적경로탐색을 수행하여 경로 A가 도출됨을 보여준다.
마지막으로 남은 경로는 C이며 min(48, 50, 46)=46으로 C경로가 최적경로가 된다. 물론 C경로 도 A경로와 N2로 유입링크기반 네트워크변형을 통 하여 N3를 통하여 최적경로탐색으로 경로탐색이 가 능하다. 중요한 점은 B, A, C경로 모두 본 연구에서 제시하는 ‘최적경로집합조건’에 만족하며 최적경로 를 포함하는 집합으로 구성되어 있다는 점이다.
여기서 검토가 필요한 사항중 하나는 K 상한 (Upper Bound)에 관한 것이다. 실제 대규모 망에서 는 모든 경로를 열거하는 것은 불가능하다고 알려 져 있다. 그러나 본 연구는 환승을 포함하는 대중교 통 네트워크를 대상으로 복수경로를 탐색하는 것으 로서, 일반적으로 대중교통망에서 최적경로를 포함 하여 경로열거는 10개 미만으로 충분하며, 이는 현 재의 계산 시스템으로 연산이 가능하다. 비가산성 비용의 최적해법은 결국 문제 맞춤형적으로 K민감 도를 고려하는 방안이 적절하다.
Ⅳ결론
누적환승함수는 환승횟수가 늘어날수록 환승 자 체에서 발생하는 실제비용보다 더 많이(적게) 인식 되도록 한다.
본 연구는 출발지부터 환승이 발생하는 시점까 지 환승의 영향을 누적적으로 반영하는 최적경로탐 색 수식을 제시했다. 또한 누적환승함수의 사례로 서 파라메타로 반영하는 방법을 토이네트워크를 통 행 검증했다. 누적환승함수가 포함된 통행비용은 비가산성 문제로서 경로열거가 요구됨을 증명했다. 경로열거에서 표지확정 문제를 우회하는 방안으로 최적경로집합조건을 제시했다. 이 조건을 구축하는 K경로탐색기법으로서 유입링크기반 전체경로삭제 기법을 수정하여 제안했다.
본 연구는 토이네트워크를 대상으로 결과의 타 당성을 제시했으나, 대규모 현실 교통망에 대한 추 가적인 검증이 필요할 것으로 판단된다. 특히 표지 확정과정에서 발생하는 다양한 문제에 대해서는 향 후 구체적으로 확인하는 절차가 필요하다. 최적경 로탐색에 더하여 다수의 경로를 탐색하는 방안으로 서 활용성을 확대하는 방안도 요구된다.