Ⅰ. 연구의 배경 및 목적

전통적인 최단경로 문제(Shortest Path Problem)는 최적화 문제의 중요한 부분을 차지하며 비즈니스, 물류, 교통, 지리, 그리고 컴퓨터 분야에서 수십 년 동안 폭 넓게 연구되어 왔다. 최단경로 문제는 크게 하나의 출발노드에서 다른 모든 노드까지의(oneto- all) 최단경로를 구성하는 방법과 모든 노드 사이 의(all-to-all) 최단경로를 구성하는 방법으로 구분한 다. 또한, 전통적인 최단경로문제에서는 링크의 통 행속도와 통행시간은 일정한 것으로 가정한다. 그 러나 도시지역 내에서는 가로망의 일정부분에서의 혼잡에 의해 하루 중에도 수시로 링크의 통행속도 와 통행시간은 변하는 것이 사실이다. 따라서 매시 간간격 변동적인 링크 통행 속도와 통행시간을 고 려하기 위해서 최단경로 문제는 시간 종속적 최단 경로 문제(Time Dependent Shortest Path Problem)로 확장되었다. 또한, AVL(Automatic Vehicle Location), 디지털 통신, 컴퓨터, GPS(Global Positioning System) 그리고 GIS(Geographic Information System) 와 같은 첨단정보기술의 발달로 인하여 실생활의 폭넓은 분야에 시간 종속적 최단경로 문제의 적용 이 가능해지고 있다. 또한, 시간 종속적 가로망에 대한 보다 빠르고 효율적인 최단경로 탐색 알고리 즘의 개발은 교통, 물류, 그리고 ITS 분야에서 중요 한 과제임이 틀림없다. 특히, ITS 분야의 경로 일정 계획과 실시간 내비게이션 시스템에 적용하기 위해 서는 실시간으로 빠른 one-to-one최단경로 탐색이 가능해야만 한다. 시간 종속적 최단경로 문제에서 는 모형이 first-in first-out(FIFO) 특성을 만족시켜야 하는데 FIFO특성은 똑 같은 링크를 운행하는 두 차 량이 있을 경우, 링크내의 혼잡과 상관없이 출발시 점에서의 순서대로 목적지점에 도착해야만 한다는 것을 의미한다.

따라서 본 연구는 FIFO특성을 만족함과 동시에 실제 도시 가로망에 적용 가능한 시간간격에 따라 변동적인 링크 통행속도를 고려하는 빠르며 효율적 인 one-to-one 최단시간 경로 알고리즘을 개발하는데 목적이 있다. 이를 위해, 먼저 기존의 일반적인 최단 거리 경로 알고리즘 중에서 실제 도로망에서 비교적 빠르고 효율적인 알고리즘으로 알려져 있는 3가지 의 알고리즘들, 즉, two queues 구조를 가진 Graph growth 알고리즘(TWO_Q), approximate buckets 구조 를 가진 Dijkstra 알고리즘(DIKBA), double buckets 구조를 가진 Dijkstra 알고리즘(DIKBD)이 선택된 다. 선택된 알고리즘들은 FIFO특성을 만족하면서 시간 종속적 가로망에 대해 하나의 출발노드에서 하나의 도착노드로의(one-to-one) 최단시간 경로탐색 이 가능하도록 제안된다. 또한, 제안된 3가지의 시 간 종속적 최단경로 알고리즘들은 미국의 Anaheim, Baltimore, Chicago, Philadelphia 4개 도시의 실제 가 로망에 적용하여 검증·평가된다.

이 논문의 구성은 다음과 같다. 2장에서는 기존 의 개발된 전통적인 최단경로 알고리즘과 시간 종 속적 최단경로에 대한 연구를 검토한다. 3장에서는 전통적인 최단경로 알고리즘을 기초로 해서 개발된 3가지의 시간 종속적 최단경로 알고리즘들을 제안 한다. 또한, 4장에서는 제안된 시간 종속적 최단경 로 알고리즘들을 실제 도시부 가로망에 적용하여 그 결과를 비교한다. 마지막으로 5장에서 본 연구 에 대한 결론과 앞으로의 연구방향을 제시한다.

Ⅱ. 관련 연구

1. 전통적인 최단경로 알고리즘

One-to-all 최단경로 문제를 풀기 위한 알고리즘은 크게 표지고정(label-setting)과 표지수정(label-correcting) 기법으로 나누어진다.

전통적인 최단경로 문제에 대한 모형과 알고리 즘들은 Bellman(1958)와 Dijkstra(1959)의 연구에서 시작되었다[1,2]. 이후에 Dial 외(1979)는 리스트(list) 구조체와 표지(labeling) 기술의 최단경로 알고리즘 성능에 대한 영향을 평가하였다[3]. Pallottino(1984) 는 표지수정(label-correcting)기법의 하나인 graph growth 알고리즘을 개발하였으며, Gallo와 Pallottino (1988)는 다양한 자료구조를 적용한 8가지의 최단 경로 알고리즘을 소개하고 컴퓨터 실험을 통해서 비교 평가하였다[4,5].

Cherkassky 외(1993)의 연구는 최단거리 경로 알 고리즘들에 대한 가장 종합적인 평가 중의 하나로 서 무작위로 만들어진 다수의 네트워크에서 17가지 one-to-all 최단거리 경로 알고리즘들을 평가했다[6]. 결과적으로 비음(nonhegative)의 아크길이를 가진 네 트워크에 대해 표지고정(label-setting)기법의 하나인 DIKBD 알고리즘을 최적의 알고리즘으로 제안했다.

Zhan과 Noon(1998)은 앞서의 연구에서 평가된 17가 지 알고리즘들 중에서 15가지의 알고리즘들을 실제 네 트워크를 통해서 평가했다[7]. 결과적으로 one-to-all 최 단거리 경로탐색을 위해서 표지수정(label-correcting)기법 의 하나인 TWO_Q가 추천되었고, 표지고정(label-setting) 기법인 DIKBA와 DIKBD는 one-to-one 또는 one-to-some 최단거리 경로탐색을 위해서 추천되었다.

또한, Zhan과 Noon(2000)은 앞서 Zhan과 Noon (1998)의 연구에 기초해서 one-to-one 최단거리 경로 탐색에 대해 DIKBA와 TWO_Q를 비교하였다[8].

최근에, 이미영 외(2008)는 통행시간, 환승횟수, 환승시간과 같은 복수의 제약 또는 목적의 고려가 요구되는 대중교통망을 대상으로 한 경로 탐색 기 법을 제안했다[9].

2. 시간 종속적 최단경로 알고리즘

시간 종속적 최단경로 문제를 위한 모형과 알고 리즘에 대한 연구는 Cooke와 Halsey(1966)에 의해 시작되었다[10]. 이후에 Orda와 Rom(1990)은 링크 지연이 시간에 대한 함수로 정의되는 네트워크에서 의 최단경로 문제를 제안했다[11]. Ziliaskopoulos와 Mahmassani(1993)는 bellman의 최적화원리에 기초하 여 표지수정(label correction)의 횟수를 줄이기 위해 서 double-ended queue를 이용한 시간 종속적 최단 경로 알고리즘을 개발했다[12].

Sung 외(2000)와 Ichoua 외(2003)는 기존의 불연 속적인 통행시간과 비용함수에 기초한 모형들의 단 점으로 first-in first-out(FIFO)특성을 만족하지 못함 을 지적하고 통행시간 모형대신에 통행속도 모형을 제안했다[13,14].

3. 시사점

기존의 연구검토 결과, 비교적 큰 규모의 실제 가로망에 대한 one-to-all 최단거리 경로문제에서 표 지고정 기법의 알고리즘 중에서는 DIKBA와 DIKBD, 표지수정 기법의 알고리즘 중에서는 TWO_Q가 비교적 계산시간이 빠르며 메모리 사용도 효율적인 것으로 나타났다. 차량의 경로일정계획, 긴급구조출 동, 배송문제, 실시간 내비게이션 등을 포함하는 교 통과 ITS분야에서는 one-to-one 최단경로 탐색이 필 수적이며 one-to-all 최단경로 알고리즘은 one-to-one 최단경로 알고리즘으로 쉽게 변형이 가능하다.

시간 종속적 최단경로에 대한 연구에서는 개발 된 알고리즘의 FIFO 특성 만족이 중요시되고 있으 며 그동안 실제 가로망에 적용된 사례가 많지 않았 다. 따라서 본 연구에서는 one-to-all 최단거리 알고리 즘인 DIKBA, DIKBD, TWO_Q를 이용하여 oneto- one 시간 종속적 최단시간 경로 알고리즘을 개발 하고 실제 가로망에 적용하여 검증·평가하고자 한다.

Ⅲ. 시간 종속적 최단경로 알고리즘

1. 링크 통행속도 모형

본 연구에서 통행시간은 시간대에 따라 변동하 는 것으로 가정한다. 어느 한 지점과 다른 지점간의 통행시간은 양방향이 항상 같지는 않다. 링크 통행 속도는 교통 센터로부터 실시간으로 매 10분마다 주어진다고 가정하고 시간 종속적 최단경로 알고리 즘을 이용하여 출발지에서 목적지까지의 통행시간 을 계산할 수 있다. FIFO특성을 만족시키기 위해서, Sung 등(2000)에 의해 개발된 링크 통행속도 모형과 도착시간함수를 다음과 같이 본 연구에 적용했다. 여기서, Arrival_Time_TD(s_t, arc_ij)는 노드 i에서 시간 s_t에 출발했을 때 노드 j에 도착하는 시간, Link_Speed_Function(k, arc_ij)은 time interval이 k일 때 링크 ij의 링크통행속도, IntervalLegnth는 시간간 격의 길이, source는 출발노드, ending은 도착노드, f_node는 링크의 시작노드, t_node는 링크의 끝노드 를 말한다.

실제 환경에서는 교통 센터로부터 매시간간격 링크 통행속도를 실시간으로 수집이 가능하나 본 연구에서는 매시간간격으로 변동하는 링크 통행속 도를 다음과 같이 가정한다. 먼저 링크를 그들의 기 능에 따라서 3가지 유형으로 나눈다. 즉, 첫 번째 유형인 고속도로는 60mph, 두 번째 유형인 간선도 로는 40mph, 그리고 세 번째 유형인 집산도로는 30mph의 링크속도를 가진다. 첨두시간의 교통상황 에 덜 영향을 받는 집산도로를 제외한 고속도로와 간선도로는 시간대마다 통행시간이 변동하는 것으 로 간주한다. 매 시간간격은 10분으로, 하루는 144 개의 시간간격으로 나누어진다.

2. E-TWO_Q 알고리즘

앞에서 설명된 링크 통행속도 모형과 도착시간 함수를 이용하여 two queues 자료구조를 가진 one-to-all Graph growth 알고리즘(TWO_Q)은 one-toone 시간 종속적 최단경로 탐색 알고리즘(ETWO_ Q)으로 확장되었다. Two queues 자료구조를 가진 Graph growth 알고리즘(TWO_Q)은 Pallottino (1984)에 의해 최초로 소개되었다[3]. <그림 1>는 twoqueue 자료구조를 예시하고 있으며 Zhan(1997)에서 참 조하였다[15]. Two-queue 자료구조에서는 Q’와 Q”로 표 현되는 두 개의 queue를 가지고 있어서 Q’와 Q”의 end 에서 노드삽입, head에서 노드제거가 가능하다.

기존의 표지수정(label-correcting) 기법의 하나인 Graph growth 알고리즘은 one-to-all 방식으로 시작 노드에서 다른 모든 노드까지의 최단경로를 탐색한 다. 따라서 목적노드가 시작노드와 가깝다 하더라 도 최단경로를 찾아내기 위해서 모든 노드를 탐색 해야 하는 단점이 있다. 본 연구에서는 one-to-one 알고리즘을 위해 심충섭과 김진석(2002)의 연구에 서와 같은 방법으로 시작노드에서 목적노드까지의 경로 값을 threshold 값으로 정해 이 값 이상으로의 노드 탐색을 방지하여 경로탐색 시간을 줄였다[16].

3. E-DIKBA 알고리즘

Approximate buckets 자료구조를 가진 Dijkstra 알 고리즘(DIKBA)도 앞에서 설명된 링크통행속도 모 형과 도착시간함수를 이용하여 시간 종속적 최단경 로 탐색 알고리즘(E-DIKBA)으로 확장되었다. Dial (1969)은 처음으로 Dijkstra 알고리즘에 bucket 자료 구조를 적용했다[3]. 원래의 Dijkstra 알고리즘에서 는 표지된 노드들(labeled nodes)은 정렬되지 않은 상태의 목록(list)으로 관리되어 경로탐색의 반복과 정 중에 minimum distance label를 가진 노드를 선택 하기 위해 모든 표지된 노드들을 확인해야 하는 비 효율적인 과정을 거쳐야 한다. 이러한 문제점을 개 선하기 위해 bucket 자료구조를 적용하여 표지된 노 드들을 관리함으로써 표지된 노드들을 distance label에 따라 정확하게 또는 근사적으로 정렬할 수 있다[8]. Approximate buckets 자료구조를 적용할 경 우, 한 bucket내 distance label들의 값들은 정확하게 동 일하지 않고 대신에 일정한 범위 안에 속하게 된다. <그림 2>는 bucket 자료구조를 예시하고 있다[15].

표지고정(label-setting) 기법의 하나인 DIKBA에서 는 one-to-one 최단경로를 구할 경우, 일단 목적노드 가 찾아지면 알고리즘은 종료되며 네트워크내의 모 든 노드들을 검색할 필요가 없게 된다.

4. E-DIKBD 알고리즘

시간 종속적 최단경로 탐색을 위해 double buckets 자료구조를 가진 확장된 Dijkstra 알고리즘(EDIKBD) 은 E-DIKBA와 똑 같은 처리과정을 가지며 단지 다른 형태의 자료구조를 가진다. 즉, 상위레벨 과 하위레벨로 이루어진 2개 레벨의 buckets를 적용 한다. 검색과정에서 먼저 하위레벨의 bucket들내 모 든 노드들이 검색된 후 상위레벨의 비워있지 않는 bucket들내 노드들을 해당하는 하위레벨의 bucket들 로 이동시키고 다음 검색과정이 다시 시작된다.

Ⅳ. 제안된 알고리즘들의 비교

1. 실험대상 네트워크

본 연구에서 제안된 3가지의 시간 종속적 최단시 간 경로탐색 알고리즘들은 실제 도시부 가로망에 적용하여 검증 평가된다. 네트워크 자료는 미국의 Anaheim, Baltimore, Chicago, Philadelphia 4개 도시 의 실제 가로망 자료를 이용했으며, Anaheim, Chicago, Philadelphia의 자료는 Bargera(2011)로부터 Baltimore의 자료는 상용패키지인 ArcLogistics Route의 GIS data를 이용했다[17].

실험대상 네트워크의 주요특성들은 <표 1>과 같 으며 대상 네트워크 중에서 Anaheim은 노드와 링크 의 수가 상대적으로 가장 적으며, Baltimore는 노드 와 링크의 수가 가장 많다.

Zhan(1997)의 연구에서 실제 도로 네트워크의 중요 한 특성중의 하나로서 링크/노드 비율로 측정되는 연 결정도를 언급하고 있다[16]. 최단경로 트리를 구성하 는데 필요한 검색 수는 링크/노드 비율과 직접적으로 관련이 있기 때문에 실제 도로 네트워크와 가상 네트 워크 간 이러한 링크/노드 비율의 차이를 확인하는 것 이 중요하다. 본 연구의 실험대상 네트워크에서는 링 크/노드 비율은 2.20에서 3.01의 범위를 보이고 있다.

3가지의 알고리즘들은 C++ 프로그램 언어로 코 딩되었으며 Cherkassky 외(1993)의 연구에서 제공된 one-to-all 최단경로탐색을 위한 C 소스코드를 이용 하였다[6]. 입력 네트워크 자료는 forward star 형태 로 표현되었으며 모든 컴퓨터 작업은 Window XP환 경 내에서 2.0GHZ Intel Core 2 Duo CPU와 3GB 메 모리를 가진 컴퓨터에서 실행되었다.

제안된 3가지 시간 종속적 최단시간 경로 알고리 즘들의 성능비교를 위해서 실험대상 네트워크에서 무작위로 100쌍의 출발노드와 도착노드를 선택했다. 또한, 각 쌍의 출발노드와 도착노드에 대해 2개씩의 출발시간이 무작위로 선택되는데, 하나는 비첨두시간 대에, 다른 하나는 첨두시간대에 속한다.

2. 실험결과

일반적으로 표지고정 기법인 DIKBA, DIKBD 와 표지수정 기법인 TWO_Q 간의 계산시간 차이는 검 색횟수와 검색을 위한 노드들을 선택하는데 필요한 시간에 좌우된다. DIKBA와 DIKBD는 TWO_Q에 비 해서 상대적으로 노드 당 검색 수는 적은 편이지만 검색에 맞는 표지된 노드를 포함하는 하나의 bucket 을 찾을 때까지 모든 bucket들을 연속적으로 확인해 야 함으로 과도한 수의 빈 bucket들을 확인하는데 많은 시간을 소모할 수도 있다. 이에 비해, TWO_Q 에서는 검색을 위해 한 노드를 선택하는데 필요한 시간은 최소화된다.

<표 2>는 실험대상 네트워크에 대한 제안된 3가 지 시간 종속적 최단시간 경로 알고리즘들의 평균 계산시간에 대한 비교를 보여준다. 비교적 Anaheim 과 Chicago 네트워크에서는 E-TWO_Q이 E-DIKBA 와 E-DIKBD보다 4%~20% 더 빠르게 최단시간 경 로를 탐색했고 E-DIKBD가 E-DIKBA보다 약간 더 빠른 것으로 나타났다. 반면에 비교적 규모(노드와 링크 수)가 더 큰 Baltimore와 Philadelphia 네트워크 에서는 E-DIKBD가 E-TWO_Q와 E-DIKBA보다 6%~29% 빠른 것으로 나타났다. 즉, 소규모의 네트 워크에서는 E-TWO_Q가 좀 더 빠르며, 대규모의 네 트워크에서 E-DIKBD가 좀 더 빠른 것으로 판단할 수 있다. 이는 네트워크 규모가 커짐에 따라 E-DIKBD의 경우 상대적으로 적은 노드 당 검색수 로 인하여 빠른 계산시간의 결과를 보이는 것으로 해석된다.

계산시간의 max/mean 값을 비교했을 때, E-TWO_Q 의 max/mean 값이 E-DIKBA와 E-DIKBD의 값들보 다 2배~3배 정도 큰 것으로 나타났다. E-TWO_Q가 E-DIKBA와 E-DIKBD에 비해서 통행시간의 길이에 따른 계산시간의 변동이 큰 것으로 해석되며 이는 E-TWO_Q 알고리즘의 경우, 출발노드와 목적노드 간의 통행시간의 길이에 따라 계산시간이 좌우됨을 보여주는 것이다. 또한, max/mean 값은 알고리즘의 예측가능성에 대한 척도로서 max/mean 값이 클수 록 해당 알고리즘은 평균적인 노드 당 소요시간과 비교했을 때 어떤 출발노드들에서 상당히 긴 시간 을 필요로 할 수 있음을 의미한다. 따라서 E-DIKBA와 E-DIKBD는 출발노드에 상관없이 일률 적인 속도성능을 유지하는 것으로 나타났다.

첨두시간과 비첨두시간으로 구분하여 3가지 알 고리즘의 계산시간을 비교하였을 때 첨두시간과 비 첨두시간간의 계산시간의 차이는 거의 없었으며 <표 2>에서와 같은 결과를 보였다.

<그림 3>은 Baltimore 네트워크에 대한 계산시간 의 Box Plot을 보여 준다. 역시, E-TWO_Q 알고리즘 이 E-DIKBA와 E-DIKBD보다 통행시간의 길이에 따른 계산시간의 변동이 큰 것을 알 수 있다. 따라 서 전체적인 결과를 통해서 비교적 큰 규모의 도시 부 가로망을 대상으로 한 one-to-one 시간 종속적 최단경로 알고리즘으로 계산시간이 빠르며 출발노 드에 상관없이 일률적인 속도성능을 보이는 EDIKBD 알고리즘이 가장 적합한 것으로 판단된다.

Ⅴ. 결 론

본 연구에서 시간간격에 따라 변동하는 링크 통 행속도를 고려한 3가지의 one-to-one 시간 종속적 최단시간 경로 알고리즘들, 즉, two queues 자료구 조를 가진 확장된 Graph growth 알고리즘, App roximate buckets 자료구조를 가진 확장된 Dijkstra 알고리즘, double buckets 자료구조를 가진 확장된 Dijkstra 알고리즘이 제안되었고 4개의 실제 도시부 가로망에 적용하여 검증 평가되었다. 실험결과, 소 규모의 네트워크에서는 E-TWO_Q가 좀 더 빠르며, 대규모의 네트워크에서 E-DIKBD가 좀 더 빠른 것 으로 나타났다. 또한, E-DIKBD는 E-TWO_Q에 비해 서 출발노드에 상관없이 일률적인 속도성능을 유지 하는 것으로 나타났다. 따라서 전체적인 결과를 통 해서 도시부 가로망을 대상으로 한 one-to-one 시간 종속적 최단경로 알고리즘으로 비교적 계산시간이 빠르며 출발노드에 상관없이 일률적인 속도성능을 보이는 E-DIKBD 알고리즘이 추천된다.

본 연구에서 제안된 시간 종속적 최단경로 알고 리즘은 교통, 물류, 그리고 ITS분야의 경로 일정계 획과 실시간 내비게이션 시스템에 적용가능하다. 실제로 E-DIKBD는 Kim 외(2011)에 의해 제안된 다 수 차고지를 가진 dial-a-ride problem(교통약자 차량 의 경로와 일정문제)의 시간 종속적 최단경로 탐색 에 적용되어 시스템 전체 경로와 일정계획에 대한 총 계산시간을 절약할 수 있었다[18,19].