기존의 최단경로 탐색모형들은 주로 경로의 단일 속성만을 고려한다. 그러나 실제로 통행자가 단일 속성만을 고려하여 경로를 선택하는 경우는 드물며, 대부분의 경로는 통행시간이나 경로길이 또는 통행자의 개인적인 선호 등과 같은 다양한 속성들이 종합적으로 고려되어 선택되어진다. 따라서 최적경로를 탐색하기 위해서는 이와 같은 다양한 속성들을 종합적으로 고려하여야 한다. 본 논문에서는 다양한 경로속성들을 고려하기 위하여 이산선택모형을 사용하여 네트워크의 노드별 효용을 산출하고, 이를 이용하여 최대의 효용을 가지는 경로를 탐색한다. 경로선택모형을 구축하기 위하여 경로선택에 영향을 미치는 요소들을 통행시간, 지체시간, 경로길이, 신호교차로수, 회전수, 전용도로의 포함비율 6가지로 선정하고, 모형의 모수를 추정하기 위한 현시선호자료를 구하기 위하여 서울시와 인접 신도시 간의 기종점 5개에 대한 경로를 선정하여 설문조사를 실시하였다. 경로선택모형의 함수형태로는 다항로짓모형을 사용하였으며, 모수추정 결과 통행시간과 신호 교차로수, 전용도로의 포함비율을 제외한 경로길이, 지체시간, 회전수를 가지고 모수를 추정한 결과가 통계적 유의성이 가장 높은 모형으로 도출되었다. 경로탐색 알고리즘으로는 도심부에서 U-turn과 회전제한의 반영이 가능한 기존의 수정형 덩굴망 알고리즘을 사용하였으며, 이를 구현하여 실제 네트워크에 적용하였다.
기존의 최단경로 탐색모형들은 주로 경로의 단일 속성만을 고려한다. 그러나 실제로 통행자가 단일 속성만을 고려하여 경로를 선택하는 경우는 드물며, 대부분의 경로는 통행시간이나 경로길이 또는 통행자의 개인적인 선호 등과 같은 다양한 속성들이 종합적으로 고려되어 선택되어진다. 따라서 최적경로를 탐색하기 위해서는 이와 같은 다양한 속성들을 종합적으로 고려하여야 한다. 본 논문에서는 다양한 경로속성들을 고려하기 위하여 이산선택모형을 사용하여 네트워크의 노드별 효용을 산출하고, 이를 이용하여 최대의 효용을 가지는 경로를 탐색한다. 경로선택모형을 구축하기 위하여 경로선택에 영향을 미치는 요소들을 통행시간, 지체시간, 경로길이, 신호교차로수, 회전수, 전용도로의 포함비율 6가지로 선정하고, 모형의 모수를 추정하기 위한 현시선호자료를 구하기 위하여 서울시와 인접 신도시 간의 기종점 5개에 대한 경로를 선정하여 설문조사를 실시하였다. 경로선택모형의 함수형태로는 다항로짓모형을 사용하였으며, 모수추정 결과 통행시간과 신호 교차로수, 전용도로의 포함비율을 제외한 경로길이, 지체시간, 회전수를 가지고 모수를 추정한 결과가 통계적 유의성이 가장 높은 모형으로 도출되었다. 경로탐색 알고리즘으로는 도심부에서 U-turn과 회전제한의 반영이 가능한 기존의 수정형 덩굴망 알고리즘을 사용하였으며, 이를 구현하여 실제 네트워크에 적용하였다.
Existing shortest-path algorithms mainly consider a single attribute. But traveler actually chooses a route considering not single attribute but various attributes which are synthesized travel time, route length, personal preference, etc. Therefore, to search the optimal path, these attributes are c...
Existing shortest-path algorithms mainly consider a single attribute. But traveler actually chooses a route considering not single attribute but various attributes which are synthesized travel time, route length, personal preference, etc. Therefore, to search the optimal path, these attributes are considered synthetically. In this study route searching algorithm which selects the maximum utility route using discrete choice model has developed in order to consider various attributes. Six elements which affect route choice are chosen for the route choice model and parameters of the models are estimated using survey data. A multinomial logit models are developed to design the function of route choice model. As a result, the model which has route length, delay time, the number of turning as parameter is selected based on the significance test. We use existing shortest path algorithm, which can reflect urban transportation network such as u-turn or p-turn, and apply it to the real network.
Existing shortest-path algorithms mainly consider a single attribute. But traveler actually chooses a route considering not single attribute but various attributes which are synthesized travel time, route length, personal preference, etc. Therefore, to search the optimal path, these attributes are considered synthetically. In this study route searching algorithm which selects the maximum utility route using discrete choice model has developed in order to consider various attributes. Six elements which affect route choice are chosen for the route choice model and parameters of the models are estimated using survey data. A multinomial logit models are developed to design the function of route choice model. As a result, the model which has route length, delay time, the number of turning as parameter is selected based on the significance test. We use existing shortest path algorithm, which can reflect urban transportation network such as u-turn or p-turn, and apply it to the real network.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
그러나 가상 네트워크는 실제 네트워크와 달리 상당히 간략화되어 있기 때문에, 현실상황을 정확하게 반영하지 못하는 한계를 가지고 있으며, 본 연구에서는 이를 보완하기 위하여 구현한 알고리즘을 검토하는 과정에서 반드시 필요한 현실상황인 U-turn과 회전제한을 가상 네트워크에 표현하여 경로탐색 과정을 검토하였다.
또한 기존의 수정형 덩굴망 알고리즘의 가정을 충실히 반영하여 유고발생시 다른 경로를 탐색이 가능하고, 특정 경유지를 포함하는 경로의 탐색을 가능하도록 구현하였다.
본 연구에서는 다양한 경로속성들을 고려하기 위하여 다항로짓모형을 사용하여 노드별 효용을 산출하였으며, 이를 이용하여 최적경로를 탐색하였다. 경로탐색 알고리즘으로는 기존의 수정형 덩굴망 알고리즘을 사용하였으며, 이를 기반으로 실제 네트워크에 적용이 가능하도록 구현하여 사례분석을 수행하였다.
본 연구에서는 다양한 경로속성을 고려하기 위하여 이산선택모형을 사용하여 네트워크의 노드별 효용을 산출하였으며, 그 결과를 이용하여 최대 효용을 가지는 경로를 탐색하였다. 경로선택에 영향을 미치는 요소들은 통행시간, 지체시간, 경로길이, 신호교차로수, 회전수, 전용도로의 포함비율 6가지로 선정한다.
가설 설정
프로그램 진행 중 U-turn 또는 P-turn에서 순환이 발생하는 경우에는 한번만 순환을 하고 다른 경로를 탐색하도록 설정하였으며, 이는 순환의 통행비용이 다른 경로를 선택하는 비용보다 적다고 하더라도 계속적인 순환은 현실적으로 발생하지 않으며, 회전비용이 없는 일반적인 회전에서 아무리 회전비용이 크다고 하더라도 U-turn과 P-turn의 비용보다 적다고 생각할 수 있기 때문에, 이와 같은 계속적인 순환을 탐색하는 것은 의미가 없다고 가정하였다.
제안 방법
U-turn 또는 P-turn 과 같은 회전제한이 존재하는 도심부의 실제 도로망을 대상으로, 본 연구에서 구현한 경로탐색 알고리즘을 적용하였다. 실험에 사용되는 도로망은 경로 간 비교가 가능하도록 간선도로와 일반도로를 적절하게 포함하여 대안 경로가 명확한 지역을 고려하였다.
가상 네트워크에서 U-turn이 허용되는 노드는 2번, 7번, 8번, 11번으로 모두 4개이며, 노드 2-노드 6-노드 2, 노드 8-노드 7-노드 11, 노드 9-노드 10-노드11의 경로에서는 회전비용을 부여하여 회전을 제한하도록 하였다.
경로 1의 경우 다양한 경로속성을 반영하는 효용을 산출하기 위하여 실제 네트워크를 간략화한 분석 네트워크의 총 186개 링크에 대한 실제 지체시간과 회전수, 경로 길이 자료를 기반으로 본 연구에서 구축한 경로선택 모형을 사용하여 각 링크에 대한 일반화비용으로 산출하였으며, 이를 기반으로 경로를 탐색하였다. 경로 2의 경우는 각 링크에 대한 실제 통행시간 자료를 기준으로 탐색하였으며, 경로 3과 경로 4의 경우는 각각 실제 통행속도 자료와 통행거리 자료를 기반으로 경로를 탐색하였다.
경로 1의 경우 다양한 경로속성을 반영하는 효용을 산출하기 위하여 실제 네트워크를 간략화한 분석 네트워크의 총 186개 링크에 대한 실제 지체시간과 회전수, 경로 길이 자료를 기반으로 본 연구에서 구축한 경로선택 모형을 사용하여 각 링크에 대한 일반화비용으로 산출하였으며, 이를 기반으로 경로를 탐색하였다. 경로 2의 경우는 각 링크에 대한 실제 통행시간 자료를 기준으로 탐색하였으며, 경로 3과 경로 4의 경우는 각각 실제 통행속도 자료와 통행거리 자료를 기반으로 경로를 탐색하였다.
경로선택 모형으로는 다항로짓모형을 사용하였으며, 모형의 모수를 추정하기 위한 현시선호자료를 구하기 위하여 서울시 및 인접 신도시의 기종점 5개(김포공항∼당산역, 김포공항∼서울대, 서울대∼국회의사당, 시청앞∼일산백석역앞, 대치역∼분당구청)에 대한 경로를 선정하여 설문조사를 실시하였다.
경로선택에 영향을 미치는 요소들은 여러 가지가 있을 수 있으나, 이들 가운데 계량화가 어렵거나 현실적으로 자료수집 가능성이 적은 요소들을 제외한 다음의 6가지 요소들을 독립변수로 선정하였다.
본 연구에서는 다양한 경로속성들을 고려하기 위하여 다항로짓모형을 사용하여 노드별 효용을 산출하였으며, 이를 이용하여 최적경로를 탐색하였다. 경로탐색 알고리즘으로는 기존의 수정형 덩굴망 알고리즘을 사용하였으며, 이를 기반으로 실제 네트워크에 적용이 가능하도록 구현하여 사례분석을 수행하였다.
기종점이 김포공항에서 당산역인 강서구 지역은 올림픽대로와 남부순환도로 등의 간선도로와 공항로, 노들길 등과 같은 주요도로를 적절하게 포함하여 뚜렷한 대안 경로를 가지므로, 본 논문에서 실제 네트워크로 사용하였으며, 실제 네트워크의 모든 도로를 고려하는 것은 어렵기 때문에 본 연구에서는 실험목적에 알맞도록 도로망을 최소한으로 간략화한 네트워크를 설계하였다.
또한 실제로 통행자들이 어떠한 경로를 선호하는지 알아보기 위하여 다양한 경로속성을 고려한 최적경로와 단일 속성을 고려한 경로에 대해 설문조사를 실시하였다.
모형의 구축과정으로는 우선 6개 독립변수 모두에 대한 모수를 추정한 후 t-통계량이 낮게 산출된 변수인 통행시간, 전용도로비율, 경로길이를 선정하고 이후의 모형에서는 이들 세 변수를 동시에 사용하지 않고 모형들을 구축하였다. 검토된 모형들 중에서 지체시간과 회전수, 경로길이를 독립변수로 하는 모형의 조정우도비지표가 가장 높게 나타났으며 모수추정 결과1)는 <표 2>와 같다.
본 논문에서는 이러한 기존 덩굴망 알고리즘의 문제점과 도시부의 합리적인 회전제약을 고려할 수 있는 기존의 수정형 덩굴망 최단경로 탐색 알고리즘(김익기, 1998)을 사용하였으며, 이를 기반으로 Microsoft Visual Basic 6.5를 사용하여 실제 네트워크에 적용이 가능하도록 구현하였다.
본 연구에서는 네트워크를 구성하는 각 노드(node)의 효용을 경로선택 모형으로 계산하고, 기존의 최적경로 탐색 알고리즘(김익기, 1998)을 사용하여 다음과 같은 최대의 효용을 가지는 경로를 탐색한다.
실제 네트워크에 적용하기에 앞서, 본 연구에서 구현한 경로탐색 알고리즘이 최적경로를 올바르게 탐색하는지 검토하기 위하여 회전제한이 존재하는 가상 네트워크에 적용하였다. 가상 네트워크는 총 12개의 노드와 20개의 링크를 가지며, 각 링크의 통행비용과 U-turn 및 회전제한은 <그림 2>와 같다.
U-turn 또는 P-turn 과 같은 회전제한이 존재하는 도심부의 실제 도로망을 대상으로, 본 연구에서 구현한 경로탐색 알고리즘을 적용하였다. 실험에 사용되는 도로망은 경로 간 비교가 가능하도록 간선도로와 일반도로를 적절하게 포함하여 대안 경로가 명확한 지역을 고려하였다.
통행시간은 각 통행자가 인지하고 있는 통행시간을 의미하며, 지체시간은 인지한 통행시간에서 자유류 통행시간(free-flow travel time)을 뺀 값을 사용하였다. 여기서 자유류 통행시간은 운전자의 희망속도가 아닌 제한속도로 주행했을 때의 통행시간으로 간주하였으며, 정지나 지체없이 교차로를 통과하는 경우도 자유류 통행시간으로 보았다.
이상의 경로속성들과 결과로 나타나는 운전자의 선택 간의 관계를 규명할 수 있도록, 선정된 속성들이 다양하게 분포하고 운전자들의 인지도가 높으며, 주요하게 경합되는 경로가 존재하는 기종점을 선정하여 현시선호자료를 구득하였다.
첫 번째 방법은 도로망의 표현방식에 의한 것으로 기존의 알고리즘을 그대로 사용하면서 도로망에 가상노드와 링크(link)를 추가하는 방법이다. 그러나 이는 노드와 링크가 현저하게 증가하기 때문에 탐색 속도의 저하를 야기한다.
대상 데이터
가상 네트워크는 총 12개의 노드와 20개의 링크를 가지며, 각 링크의 통행비용과 U-turn 및 회전제한은 와 같다.
가상 네트워크에 대한 최적경로는 노드 1-노드 2-노드 6-노드 7-노드 11-노드 12이고, 최종 노선비용은 10으로 검토되었다.
설문은 총 300명에게 실시하였으며, 이 가운데 분석에 유의하지 않은 16부는 제외하였다. 설문조사의 대상자는 선정된 경로상황에 대해 답변이 가능하도록 해당 지역의 경로에 대한 지식이 풍부하고 경력이 오래된 강서구 지역에 거주하는 개인 운전자를 대상으로 하였으며, 설문결과는 <표6>과 같다.
설문조사의 대상자는 선정된 경로상황에 대해 답변이 가능하도록 해당 지역의 경로에 대한 지식이 풍부하고 경력이 오래된 강서구 지역에 거주하는 개인 운전자를 대상으로 하였으며, 설문결과는 과 같다.
실험에 사용된 네트워크는 교차로와 U-turn 지점을 포함하여 총 91개의 노드를 가지며, 양방향과 일방통행을 포함하여 총 186개의 링크를 가진다. 이중 U-turn이 가능한 지점은 36개이고, 회전제한이 있는 지점은 총 64개이다.
이론/모형
경로선택 모형의 함수형태는 다항로짓모형을 사용하였으며, 다항로짓모형의 모수를 추정하기 위하여 최우추정법(maximum likelihood method)을 사용한다. 또한 추정된 모형이 관측된 자료를 얼마나 잘 설명하는가를 나타내는 지표인 모형의 적합도(goodness of fit)를 검정하기 위하여 우도비 지표(likelihood ratio index, ρ2)와 유사한 통계량인 조정우도비지표(adjusted likelihood ratio index, #)를 사용하였다.
경로선택 모형으로는 다항로짓모형을 사용하였으며, 모형의 모수를 추정하기 위한 현시선호자료를 구하기 위하여 서울시 및 인접 신도시의 기종점 5개(김포공항∼당산역, 김포공항∼서울대, 서울대∼국회의사당, 시청앞∼일산백석역앞, 대치역∼분당구청)에 대한 경로를 선정하여 설문조사를 실시하였다. 또한 경로탐색 알고리즘으로는 도심부에서 유-턴(U-turn)과 회전제한의 반영이 가능한 기존의 수정형 덩굴망 최단경로 탐색 알고리즘(김익기, 1998)을 사용하였으며, 이를 기반으로 실제 네트워크에 적용이 가능하도록 구현하였다.
또한 추정된 모형이 관측된 자료를 얼마나 잘 설명하는가를 나타내는 지표인 모형의 적합도(goodness of fit)를 검정하기 위하여 우도비 지표(likelihood ratio index, ρ2)와 유사한 통계량인 조정우도비지표(adjusted likelihood ratio index, #)를 사용하였다.
통행시간은 각 통행자가 인지하고 있는 통행시간을 의미하며, 지체시간은 인지한 통행시간에서 자유류 통행시간(free-flow travel time)을 뺀 값을 사용하였다. 여기서 자유류 통행시간은 운전자의 희망속도가 아닌 제한속도로 주행했을 때의 통행시간으로 간주하였으며, 정지나 지체없이 교차로를 통과하는 경우도 자유류 통행시간으로 보았다.
성능/효과
또한 경로선택 모형의 결과를 고려하면 통행자는 회전수가 적고 거리가 짧은 경로를 선호하므로, 최적경로도 거의 직선과 같은 경로 1이 탐색되었다.
본 연구에서는 경로의 탐색기준이 다름에도 불구하고, 실제 도로망에서 조사된 공항로(경로 1)의 지체시간이 올림픽대로(경로 2)나 남부순환도로(경로 3)의 지체시간과 큰 차이가 없었기 때문에, 최적경로는 통행거리가 가장 짧은 경로 4와 유사하게 탐색되었다.
설문결과 다양한 경로속성을 고려한 최적경로가 단일 속성을 고려한 경로보다 통행자의 선택이 많은 것으로 나타났다. 이는 경로 2와 경로 3의 경우 간선도로를 포함하고 있어 통행속도가 다른 경로에 비하여 높을 것으로 예상되지만, 실제로는 간선도로를 포함하지 않는 경로 1의 평균통행속도와 큰 차이가 없고, 통행거리는 상대적으로 길기 때문에 통행자들의 선호도가 높지 않은 것으로 생각된다.
즉, 본 연구에서는 통행자들이 경로선택 과정에서 고려하는 변수로 지체시간과 회전수, 경로길이를 제시하였으나, 실제 도로망에서 각 경로의 지체시간이 서로 유사하게 산출되었기 때문에 모형에 대한 지체시간 변수의 설명력이 다소 감소하였다.
추정결과 모수의 부호와 t-통계량이 모두 만족스러운 것으로 나타났으며, 경로길이의 t-통계량이 다소 낮기는 하지만 경로길이 변수를 제외할 경우 경로선택모형의 구성상 문제가 될 소지가 있어 이를 제외하지 않는다. 이는 경로길이 변수가 제외되는 경우 지체시간은 짧지만, 통행시간은 상당히 큰 경로가 선택될 우려가 있기 때문이다.
후속연구
구현된 알고리즘을 이용하여 다양한 속성을 고려한 최적경로를 탐색한 결과, 단일속성을 고려한 경로보다 통행자의 선택이 많은 것으로 나타났으며, 이를 통하여 통행자의 행태를 좀 더 정확하게 반영하기 위해서는 경로탐색시 다양한 경로속성을 검토해야 함을 알 수 있다.
또한 경로탐색 알고리즘을 구현하여 실제 네트워크에 적용해 본 결과 간선도로와 같은 주요도로들의 속성차이가 크지 않을 경우, 경로의 중첩도가 높아져 최적경로의 선택이 어려워지는 문제점을 가진다. 따라서 경로상의 속성차이가 비슷할 경우 최적경로를 제외한 대안경로의 정의가 필요하며, 네트워크를 확장할 경우 탐색시간을 줄이는 방안 등에 대한 보완이 필요할 것으로 판단된다.
따라서 실험에 사용된 실제 네트워크와 다른 기종점을 가지는 도로망, 즉 모형의 독립변수인 지체함수와 회전수, 경로길이를 적절하게 비교할 수 있는 도로망을 새롭게 선정하여 본 연구에서 구현한 알고리즘을 적용해 볼 필요가 있을 것으로 판단된다.
질의응답
핵심어
질문
논문에서 추출한 답변
최적경로 문제는 어느 분야에서 효율적인 경로정보를 제공하기 위하여 필수적인 기법인가?
최적경로 문제는 네트워크 이론에서 가장 기본적이고 중요한 문제 중의 하나이며, 최근에 연구가 활발한 지능형 교통체계(Intelligent Transportation System : ITS)분야 중 첨단 여행자 정보체계(Advanced Traveler Information System : ATIS)에서 효율적인 경로정보를 제공하기 위하여 필수적인 기법이다.
최적경로란 무엇인가?
최적경로는 정해진 기점과 종점을 연결하는 다수의 경로들 중 통행자의 목적을 최적으로 하는 경로이다. 일반적으로 최적경로를 탐색하는 기준으로 통행시간, 통행비용 또는 경로길이 등 하나의 속성만을 고려하며, 통행자는 자신의 목적에 맞는 경로를 최적경로로 선택한다.
최적경로를 탐색하기 위해서는 통행자들이 경로선택시 중요하게 고려하는 속성들을 파악하여야 하는 이유는?
일반적으로 최적경로를 탐색하는 기준으로 통행시간, 통행비용 또는 경로길이 등 하나의 속성만을 고려하며, 통행자는 자신의 목적에 맞는 경로를 최적경로로 선택한다. 그러나 실제로 통행자가 단일 속성만을 고려하여 경로를 선택하는 경우는 드물며, 통행시간이나 경로길이 또는 통행자의 개인적인 선호 등과 같은 다양한 속성들을 종합적으로 고려하여 선택한다. 그러므로 최적경로를 탐색하기 위해서는 통행자들이 경로선택시 중요하게 고려하는 속성들을 파악하여야 하며, 경로탐색 과정에서 이들 속성이 고려되는 경로가 탐색되어야 한다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.