시간 종속적 가로망에 대한 최단경로 탐색은 ITS분야의 경로 일정계획과 실시간 내비게이션 시스템에서 중요한 부분을 차지한다. 본 연구에서는 매시간간격 변동적인 링크 통행속도를 고려하는 one-to-one 시간 종속적 최단시간 경로 알고리즘을 제시한다. 이를 위해, 먼저 기존의 일반적인 최단거리 경로 알고리즘 중에서 실제 도로망에서 비교적 빠르고 효율적인 알고리즘으로 알려져 있는 3가지의 알고리즘들, 즉, two queues 구조를 가진 Graph growth 알고리즘, approximate buckets 구조를 가진 Dijkstra 알고리즘, double buckets 구조를 가진 Dijkstra 알고리즘이 선택되었다. 이 알고리즘들은 모두 네트워크 내 하나의 노드에서 모든 노드(one-to-all)로의 최단거리 경로를 빠르게 탐색하기위해 개발되었다. 선택된 알고리즘들은 시간 종속적 도로망에 대해 하나의 출발노드에서 하나의 목적노드(one-to-one)로의 최단시간 경로 탐색이 가능하도록 확장된다. 또한, 제안된 3가지의 시간 종속적 최단시간 경로탐색 알고리즘들은 미국의 Anaheim, Baltimore, Chicago, Philadelphia 4개 도시의 실제 가로망에 적용하여 검증 평가된다. 결과적으로, 도시부 가로망을 대상으로 한 시간 종속적 최단시간 경로탐색 알고리즘으로 double buckets 구조를 가진 확장된 Dijkstra 알고리즘이 추천된다.
시간 종속적 가로망에 대한 최단경로 탐색은 ITS분야의 경로 일정계획과 실시간 내비게이션 시스템에서 중요한 부분을 차지한다. 본 연구에서는 매시간간격 변동적인 링크 통행속도를 고려하는 one-to-one 시간 종속적 최단시간 경로 알고리즘을 제시한다. 이를 위해, 먼저 기존의 일반적인 최단거리 경로 알고리즘 중에서 실제 도로망에서 비교적 빠르고 효율적인 알고리즘으로 알려져 있는 3가지의 알고리즘들, 즉, two queues 구조를 가진 Graph growth 알고리즘, approximate buckets 구조를 가진 Dijkstra 알고리즘, double buckets 구조를 가진 Dijkstra 알고리즘이 선택되었다. 이 알고리즘들은 모두 네트워크 내 하나의 노드에서 모든 노드(one-to-all)로의 최단거리 경로를 빠르게 탐색하기위해 개발되었다. 선택된 알고리즘들은 시간 종속적 도로망에 대해 하나의 출발노드에서 하나의 목적노드(one-to-one)로의 최단시간 경로 탐색이 가능하도록 확장된다. 또한, 제안된 3가지의 시간 종속적 최단시간 경로탐색 알고리즘들은 미국의 Anaheim, Baltimore, Chicago, Philadelphia 4개 도시의 실제 가로망에 적용하여 검증 평가된다. 결과적으로, 도시부 가로망을 대상으로 한 시간 종속적 최단시간 경로탐색 알고리즘으로 double buckets 구조를 가진 확장된 Dijkstra 알고리즘이 추천된다.
Finding shortest paths on time dependent networks is an important task for scheduling and routing plan and real-time navigation system in ITS. In this research, one-to-one time dependent shortest path algorithms based on link flow speeds on urban networks are proposed. For this work, first we select...
Finding shortest paths on time dependent networks is an important task for scheduling and routing plan and real-time navigation system in ITS. In this research, one-to-one time dependent shortest path algorithms based on link flow speeds on urban networks are proposed. For this work, first we select three general shortest path algorithms such as Graph growth algorithm with two queues, Dijkstra's algorithm with approximate buckets and Dijkstra's algorithm with double buckets. These algorithms were developed to compute shortest distance paths from one node to all nodes in a network and have proven to be fast and efficient algorithms in real networks. These algorithms are extended to compute a time dependent shortest path from an origin node to a destination node in real urban networks. Three extended algorithms are implemented on a data set from real urban networks to test and evaluate three algorithms. A data set consists of 4 urban street networks for Anaheim, CA, Baltimore, MD, Chicago, IL, and Philadelphia, PA. Based on the computational results, among the three algorithms for TDSP, the extended Dijkstra's algorithm with double buckets is recommended to solve one-to-one time dependent shortest path for urban street networks.
Finding shortest paths on time dependent networks is an important task for scheduling and routing plan and real-time navigation system in ITS. In this research, one-to-one time dependent shortest path algorithms based on link flow speeds on urban networks are proposed. For this work, first we select three general shortest path algorithms such as Graph growth algorithm with two queues, Dijkstra's algorithm with approximate buckets and Dijkstra's algorithm with double buckets. These algorithms were developed to compute shortest distance paths from one node to all nodes in a network and have proven to be fast and efficient algorithms in real networks. These algorithms are extended to compute a time dependent shortest path from an origin node to a destination node in real urban networks. Three extended algorithms are implemented on a data set from real urban networks to test and evaluate three algorithms. A data set consists of 4 urban street networks for Anaheim, CA, Baltimore, MD, Chicago, IL, and Philadelphia, PA. Based on the computational results, among the three algorithms for TDSP, the extended Dijkstra's algorithm with double buckets is recommended to solve one-to-one time dependent shortest path for urban street networks.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
따라서 본 연구는 FIFO특성을 만족함과 동시에 실제 도시 가로망에 적용 가능한 시간간격에 따라 변동적인 링크 통행속도를 고려하는 빠르며 효율적인 one-to-one 최단시간 경로 알고리즘을 개발하는데 목적이 있다. 이를 위해, 먼저 기존의 일반적인 최단 거리 경로 알고리즘 중에서 실제 도로망에서 비교적 빠르고 효율적인 알고리즘으로 알려져 있는 3가지의 알고리즘들, 즉, two queues 구조를 가진 Graph growth 알고리즘(TWO_Q), approximate buckets 구조를 가진 Dijkstra 알고리즘(DIKBA), double buckets 구조를 가진 Dijkstra 알고리즘(DIKBD)이 선택된다.
따라서 본 연구에서는 one-to-all 최단거리 알고리즘인 DIKBA, DIKBD, TWO_Q를 이용하여 one-to-one 시간 종속적 최단시간 경로 알고리즘을 개발하고 실제 가로망에 적용하여 검증·평가하고자 한다.
가설 설정
최단경로 문제는 크게 하나의 출발노드에서 다른 모든 노드까지의(one-to-all) 최단경로를 구성하는 방법과 모든 노드 사이의(all-to-all) 최단경로를 구성하는 방법으로 구분한다. 또한, 전통적인 최단경로문제에서는 링크의 통행속도와 통행시간은 일정한 것으로 가정한다. 그러나 도시지역 내에서는 가로망의 일정부분에서의 혼잡에 의해 하루 중에도 수시로 링크의 통행속도와 통행시간은 변하는 것이 사실이다.
어느 한 지점과 다른 지점간의 통행시간은 양방향이 항상 같지는 않다. 링크 통행속도는 교통 센터로부터 실시간으로 매 10분마다 주어진다고 가정하고 시간 종속적 최단경로 알고리즘을 이용하여 출발지에서 목적지까지의 통행시간을 계산할 수 있다. FIFO특성을 만족시키기 위해서, Sung 등(2000)에 의해 개발된 링크 통행속도 모형과 도착시간함수를 다음과 같이 본 연구에 적용했다.
본 연구에서 통행시간은 시간대에 따라 변동하는 것으로 가정한다. 어느 한 지점과 다른 지점간의 통행시간은 양방향이 항상 같지는 않다.
실제 환경에서는 교통 센터로부터 매시간간격 링크 통행속도를 실시간으로 수집이 가능하나 본 연구에서는 매시간간격으로 변동하는 링크 통행속도를 다음과 같이 가정한다. 먼저 링크를 그들의 기능에 따라서 3가지 유형으로 나눈다.
제안 방법
Cherkassky 외(1993)의 연구는 최단거리 경로 알고리즘들에 대한 가장 종합적인 평가 중의 하나로서 무작위로 만들어진 다수의 네트워크에서 17가지 one-to-all 최단거리 경로 알고리즘들을 평가했다[6]. 결과적으로 비음(nonhegative)의 아크길이를 가진 네트워크에 대해 표지고정(label-setting)기법의 하나인 DIKBD 알고리즘을 최적의 알고리즘으로 제안했다.
또한, Zhan과 Noon(2000)은 앞서 Zhan과 Noon(1998)의 연구에 기초해서 one-to-one 최단거리 경로탐색에 대해 DIKBA와 TWO_Q를 비교하였다[8].
또한, 제안된 3가지의 시간 종속적 최단경로 알고리즘들은 미국의 Anaheim, Baltimore, Chicago, Philadelphia 4개 도시의 실제 가로망에 적용하여 검증·평가된다.
본 연구에서 시간간격에 따라 변동하는 링크 통행속도를 고려한 3가지의 one-to-one 시간 종속적 최단시간 경로 알고리즘들, 즉, two queues 자료구조를 가진 확장된 Graph growth 알고리즘, Approximate buckets 자료구조를 가진 확장된 Dijkstra 알고리즘, double buckets 자료구조를 가진 확장된 Dijkstra 알고리즘이 제안되었고 4개의 실제 도시부 가로망에 적용하여 검증 평가되었다. 실험결과, 소규모의 네트워크에서는 E-TWO_Q가 좀 더 빠르며, 대규모의 네트워크에서 E-DIKBD가 좀 더 빠른 것으로 나타났다.
본 연구에서 제안된 3가지의 시간 종속적 최단시간 경로탐색 알고리즘들은 실제 도시부 가로망에 적용하여 검증 평가된다. 네트워크 자료는 미국의 Anaheim, Baltimore, Chicago, Philadelphia 4개 도시의 실제 가로망 자료를 이용했으며, Anaheim, Chicago, Philadelphia의 자료는 Bargera(2011)로부터 Baltimore의 자료는 상용패키지인 ArcLogistics Route의 GIS data를 이용했다[17].
본 연구에서 제안된 시간 종속적 최단경로 알고리즘은 교통, 물류, 그리고 ITS분야의 경로 일정계획과 실시간 내비게이션 시스템에 적용가능하다. 실제로 E-DIKBD는 Kim 외(2011)에 의해 제안된 다수 차고지를 가진 dial-a-ride problem(교통약자 차량의 경로와 일정문제)의 시간 종속적 최단경로 탐색에 적용되어 시스템 전체 경로와 일정계획에 대한 총 계산시간을 절약할 수 있었다[18,19].
이를 위해, 먼저 기존의 일반적인 최단 거리 경로 알고리즘 중에서 실제 도로망에서 비교적 빠르고 효율적인 알고리즘으로 알려져 있는 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개 도시의 실제 가로망에 적용하여 검증·평가된다.
대상 데이터
본 연구에서 제안된 3가지의 시간 종속적 최단시간 경로탐색 알고리즘들은 실제 도시부 가로망에 적용하여 검증 평가된다. 네트워크 자료는 미국의 Anaheim, Baltimore, Chicago, Philadelphia 4개 도시의 실제 가로망 자료를 이용했으며, Anaheim, Chicago, Philadelphia의 자료는 Bargera(2011)로부터 Baltimore의 자료는 상용패키지인 ArcLogistics Route의 GIS data를 이용했다[17].
제안된 3가지 시간 종속적 최단시간 경로 알고리즘들의 성능비교를 위해서 실험대상 네트워크에서 무작위로 100쌍의 출발노드와 도착노드를 선택했다. 또한, 각 쌍의 출발노드와 도착노드에 대해 2개씩의 출발시간이 무작위로 선택되는데, 하나는 비첨두시간 대에, 다른 하나는 첨두시간대에 속한다.
이론/모형
3가지의 알고리즘들은 C++ 프로그램 언어로 코딩되었으며 Cherkassky 외(1993)의 연구에서 제공된 one-to-all 최단경로탐색을 위한 C 소스코드를 이용하였다[6]. 입력 네트워크 자료는 forward star 형태로 표현되었으며 모든 컴퓨터 작업은 Window XP환경 내에서 2.
링크 통행속도는 교통 센터로부터 실시간으로 매 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는 링크의 끝노드를 말한다.
따라서 목적노드가 시작노드와 가깝다 하더라도 최단경로를 찾아내기 위해서 모든 노드를 탐색해야 하는 단점이 있다. 본 연구에서는 one-to-one 알고리즘을 위해 심충섭과 김진석(2002)의 연구에서와 같은 방법으로 시작노드에서 목적노드까지의 경로 값을 threshold 값으로 정해 이 값 이상으로의 노드 탐색을 방지하여 경로탐색 시간을 줄였다[16].
따라서 본 연구는 FIFO특성을 만족함과 동시에 실제 도시 가로망에 적용 가능한 시간간격에 따라 변동적인 링크 통행속도를 고려하는 빠르며 효율적인 one-to-one 최단시간 경로 알고리즘을 개발하는데 목적이 있다. 이를 위해, 먼저 기존의 일반적인 최단 거리 경로 알고리즘 중에서 실제 도로망에서 비교적 빠르고 효율적인 알고리즘으로 알려져 있는 3가지의 알고리즘들, 즉, two queues 구조를 가진 Graph growth 알고리즘(TWO_Q), approximate buckets 구조를 가진 Dijkstra 알고리즘(DIKBA), double buckets 구조를 가진 Dijkstra 알고리즘(DIKBD)이 선택된다. 선택된 알고리즘들은 FIFO특성을 만족하면서 시간 종속적 가로망에 대해 하나의 출발노드에서 하나의 도착노드로의(one-to-one) 최단시간 경로탐색이 가능하도록 제안된다.
성능/효과
Zhan과 Noon(1998)은 앞서의 연구에서 평가된 17가지 알고리즘들 중에서 15가지의 알고리즘들을 실제 네트워크를 통해서 평가했다[7]. 결과적으로 one-to-all 최단거리 경로탐색을 위해서 표지수정(label-correcting)기법의 하나인 TWO_Q가 추천되었고, 표지고정(label-setting) 기법인 DIKBA와 DIKBD는 one-to-one 또는 one-to-some 최단거리 경로탐색을 위해서 추천되었다.
계산시간의 max/mean 값을 비교했을 때, E-TWO_Q의 max/mean 값이 E-DIKBA와 E-DIKBD의 값들보다 2배~3배 정도 큰 것으로 나타났다. E-TWO_Q가 E-DIKBA와 E-DIKBD에 비해서 통행시간의 길이에 따른 계산시간의 변동이 큰 것으로 해석되며 이는 E-TWO_Q 알고리즘의 경우, 출발노드와 목적노드 간의 통행시간의 길이에 따라 계산시간이 좌우됨을 보여주는 것이다.
기존의 연구검토 결과, 비교적 큰 규모의 실제 가로망에 대한 one-to-all 최단거리 경로문제에서 표지고정 기법의 알고리즘 중에서는 DIKBA와 DIKBD, 표지수정 기법의 알고리즘 중에서는 TWO_Q가 비교적 계산시간이 빠르며 메모리 사용도 효율적인 것으로 나타났다. 차량의 경로일정계획, 긴급구조출동, 배송문제, 실시간 내비게이션 등을 포함하는 교통과 ITS분야에서는 one-to-one 최단경로 탐색이 필수적이며 one-to-all 최단경로 알고리즘은 one-to-one 최단경로 알고리즘으로 쉽게 변형이 가능하다.
또한, max/mean 값은 알고리즘의 예측가능성에 대한 척도로서 max/mean 값이 클수록 해당 알고리즘은 평균적인 노드 당 소요시간과 비교했을 때 어떤 출발노드들에서 상당히 긴 시간을 필요로 할 수 있음을 의미한다. 따라서 E-DIKBA와 E-DIKBD는 출발노드에 상관없이 일률적인 속도성능을 유지하는 것으로 나타났다.
또한, E-DIKBD는 E-TWO_Q에 비해서 출발노드에 상관없이 일률적인 속도성능을 유지하는 것으로 나타났다. 따라서 전체적인 결과를 통해서 도시부 가로망을 대상으로 한 one-to-one 시간 종속적 최단경로 알고리즘으로 비교적 계산시간이 빠르며 출발노드에 상관없이 일률적인 속도성능을 보이는 E-DIKBD 알고리즘이 추천된다.
역시, E-TWO_Q 알고리즘이 E-DIKBA와 E-DIKBD보다 통행시간의 길이에 따른 계산시간의 변동이 큰 것을 알 수 있다. 따라서 전체적인 결과를 통해서 비교적 큰 규모의 도시부 가로망을 대상으로 한 one-to-one 시간 종속적 최단경로 알고리즘으로 계산시간이 빠르며 출발노드에 상관없이 일률적인 속도성능을 보이는 EDIKBD 알고리즘이 가장 적합한 것으로 판단된다.
실험결과, 소규모의 네트워크에서는 E-TWO_Q가 좀 더 빠르며, 대규모의 네트워크에서 E-DIKBD가 좀 더 빠른 것으로 나타났다. 또한, E-DIKBD는 E-TWO_Q에 비해서 출발노드에 상관없이 일률적인 속도성능을 유지하는 것으로 나타났다. 따라서 전체적인 결과를 통해서 도시부 가로망을 대상으로 한 one-to-one 시간 종속적 최단경로 알고리즘으로 비교적 계산시간이 빠르며 출발노드에 상관없이 일률적인 속도성능을 보이는 E-DIKBD 알고리즘이 추천된다.
비교적 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가 좀 더 빠른 것으로 판단할 수 있다.
<표 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% 빠른 것으로 나타났다.
본 연구에서 시간간격에 따라 변동하는 링크 통행속도를 고려한 3가지의 one-to-one 시간 종속적 최단시간 경로 알고리즘들, 즉, two queues 자료구조를 가진 확장된 Graph growth 알고리즘, Approximate buckets 자료구조를 가진 확장된 Dijkstra 알고리즘, double buckets 자료구조를 가진 확장된 Dijkstra 알고리즘이 제안되었고 4개의 실제 도시부 가로망에 적용하여 검증 평가되었다. 실험결과, 소규모의 네트워크에서는 E-TWO_Q가 좀 더 빠르며, 대규모의 네트워크에서 E-DIKBD가 좀 더 빠른 것으로 나타났다. 또한, E-DIKBD는 E-TWO_Q에 비해서 출발노드에 상관없이 일률적인 속도성능을 유지하는 것으로 나타났다.
첨두시간과 비첨두시간으로 구분하여 3가지 알고리즘의 계산시간을 비교하였을 때 첨두시간과 비첨두시간간의 계산시간의 차이는 거의 없었으며에서와 같은 결과를 보였다.
질의응답
핵심어
질문
논문에서 추출한 답변
One-to-all 최단경로 문제를 풀기 위한 알고리즘은 무엇이 있는가?
One-to-all 최단경로 문제를 풀기 위한 알고리즘은 크게 표지고정(label-setting)과 표지수정(label-correcting) 기법으로 나누어진다.
one-to-all 최단거리 알고리즘을 통해 one-to-one 시간 종속적 최단 시간 경로 알고리즘을 개발하고 실제 가로망에 적용하여 검증·평가하고자 하는 배경은 무엇인가?
시간 종속적 최단경로에 대한 연구에서는 개발된 알고리즘의 FIFO 특성 만족이 중요시되고 있으며 그동안 실제 가로망에 적용된 사례가 많지 않았다. 따라서 본 연구에서는 one-to-all 최단거리 알고리즘인 DIKBA, DIKBD, TWO_Q를 이용하여 one-to-one 시간 종속적 최단시간 경로 알고리즘을 개발하고 실제 가로망에 적용하여 검증·평가하고자 한다.
최단경로 문제는 어떻게 구분되는가?
전통적인 최단경로 문제(Shortest Path Problem)는 최적화 문제의 중요한 부분을 차지하며 비즈니스, 물류, 교통, 지리, 그리고 컴퓨터 분야에서 수십 년동안 폭 넓게 연구되어 왔다. 최단경로 문제는 크게 하나의 출발노드에서 다른 모든 노드까지의(one-to-all) 최단경로를 구성하는 방법과 모든 노드 사이의(all-to-all) 최단경로를 구성하는 방법으로 구분한다. 또한, 전통적인 최단경로문제에서는 링크의 통행속도와 통행시간은 일정한 것으로 가정한다.
참고문헌 (19)
R. E. Bellman, "On a Routing Problem", Quart. Applied. Math., vol. 16, pp.87-90, 1958.
R. B. Dial, F. Glover, D. Karney, and D. Klingman, "A Computational Analysis of Alternative Algorithms and Labeling Techniques for Finding Shortest Path Trees", Networks, vol. 9, pp.215-248, 1979.
G. Gallo, and S. Pallottino, "Shortest Path Algorithms", Annals of Operations Research, vol. 13, pp.3-79, 1988.
B. V. Cherkassky, A. V. Goldberg, and T. Radzik, Shortest Paths Algorithms: Theory and Experimental Evaluation, Technical Report 93-1480, Computer Science Department, Stanford University, 1993.
F. B. Zhan, and C. E. Noon, "Shortest Path Algorithms: An Evaluation Using Real Road Networks", Transportation Science, vol. 32, no. 1, pp.65-73, 1998.
F. B. Zhan, and C. E. Noon, "A Comparison Between Label-Setting and Label-Correcting Algorithms for Computing One-to-One Shortest Paths", Journal of Geographic Information and Decision Analysis, vol. 4, no. 2, pp.1-11, 2000.
이미영, 박제진, 정점례, 박동주, "사용자 맞춤형 대중교통 경로정보제공을 위한 다계층의 다목적 경로탐색기법 연구", 한국ITS학회논문지, 제7권, 제3호, pp.1-4, 2008. 6.
K. L. Cooke, and E. Halsey, "The shortest route through a network with time-dependent inter-nodal transit times", Journal of Mathematical Analysis and Applications, vol. 14, pp.493-498, 1966.
A. Orda and R. Rom, "Shortest-Path and Minimum- Delay Algorithms in Networks with Time-Dependent Edge-Length", Journal of the ACM, vol. 37, pp.607-625, 1990.
A. K. Ziliaskopoulos, and H. S. Mahmassani, "Time-Dependent Shortest Path Algorithm for Real-Time Intelligent Vehicle Highway System Applications", Transportation Research Record no. 1408, pp.94-104, 1993.
K. Sung, M. G. H. Bell, M. Seong, and S. Park, "Shortest Paths in a Network with Time-Dependent Flow Speeds", European Journal of Operational Research, vol. 121, no. 1, pp.32-39, 2000.
S. Ichoua, M. Gendreau, and J.-Y. Potvin, "Vehicle Dispatching with Time-Dependent Travel Times", European Journal of Operational Research, vol. 144, no. 2, pp.379-396, 2003.
F. B. Zhan, "Three Fastest Shortest Path Algorithms on Real Road Networks: Data Structures and Procedures", Journal of Geo-graphic Information and Decision Analysis, vol. 1, no. 1, pp.69-82, 1997.
심충섭, 김진석, "One-to-One 최단경로 알고리즘의 성능 평가", 정보과학회논문지: 시스템 및 이론, 제29권 제11호, pp.634-639, 2002. 12.
Bar-gera, H., http://www.bgu.ac.il/-bargera/tntp/, Accessed, 2011년 8월 접속.
T. Kim and A. Haghani, "Model and Algorithm Considering Time-Varying Travel Times to Solve Static Multidepot Dial-a-Ride Problem", Transportation Research Record, no. 2218, pp.68-77, 2011.
T. Kim, Model and Algorithm for Solving Real Time Dial-a-Ride Problem, Ph. D. Dissertation, University of Maryland, 2011.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.