Journal Search Engine

to

Search Advanced Search Adode Reader(link)
View PDF Download PDF Export Citation Korean Bibliography PMC Previewer
The Journal of The Korea Institute of Intelligent Transport Systems Vol.18 No.5 pp.91-99
DOI : https://doi.org/10.12815/kits.2019.18.5.91

A Link-Label Based Node-to-Link Optimal Path Algorithm Considering Non Additive Path Cost

Mee Young Lee*, Doohee Nam**
*Korea Research Institute of Human Settlements
**School. of Social Science, Hansung University

† Corresponding author : Mee young Lee, mylee@krihs.re.kr
20191004 │ 20191016 │ 20191023

Abstract


Existing node-to-node based optimal path searching is built on the assumption that all destination nodes can be arrived at from an origin node. However, the recent appearance of the adaptive path search algorithm has meant that the optimal path solution cannot be derived in node-to-node path search. In order to reflect transportation data at the links in real-time, the necessity of the node-to-link (or link-to-node; NL) problem is being recognized. This research assumes existence of a network with link-label and non-additive path costs as a solution to the node-to-link optimal path problem. At the intersections in which the link-label has a turn penalty, the network retains its shape. Non-additive path cost requires that M-similar paths be enumerated so that the ideal path can be ascertained. In this, the research proposes direction deletion and turn restriction so that regulation of the loop in the link-label entry-link-based network transformation method will ensure that an optimal solution is derived up until the final link. Using this method on a case study shows that the proposed method derives the optimal solution through learning. The research concludes by bringing to light the necessity of verification in large-scale networks.


Link Label , Node-to-Link , Optimal Route Searching , Destination Node Based Arrival Condition , M-Similar Route

비가산성 경로비용을 반영한 링크표지기반 Node-to-Link 최적경로탐색

이 미 영*, 남 두 희**
*주저자 및 교신저자 : 국토연구원 국토환경·자원연구본부 책임연구원
**공저자 : 한성대학교 사회과학부 교수

초록


기존의 Node-to-Node기반 최적경로탐색은 기점노드에서 모든 종점노드도착조건이 성립되 는 가정으로 구축되었다. 최근 적응적 경로탐색의 등장으로 Node-to-Node 경로탐색은 최적해 를 도출하지 못하는 한계가 존재한다. 따라서 교통정보를 링크에서 실시간 반영하기 위한 Node-to-Link(또는 Link-to-Node; NL) 문제에 필요성이 대두되고 있다. 본 연구는 Node-to-Link의 최적 해법을 구축하는 방안으로서 링크표지와 비가산성경로비용이 존재하는 네트워크를 가정 한다. 링크표지는 회전페널티가 존재하는 교차지점에서 네트워크의 원형을 유지하게 한다. 비 가산성경로비용의 포함은 최적경로를 도출하기 위해서 M-유사경로의 열거를 필요로 한다. 본 연구는 진입링크기반 네트워크 변형기법에서 링크표지를 통하여 루프를 통제하며 최종링크까 지 최적해를 보장하기 위한 방향삭제와 회전금지를 제안하였다. 사례연구를 통해 제안된 방법 이 경험적 최적해를 도출하는 것으로 파악되었다. 향후 대규모 네트워크에서 검증작업의 필요 성을 언급하며 마무리 하였다.


링크표지 , Node-to-Link , 최적경로탐색 , 종점노드도착조건 , M-유사경로

    Ⅰ. 서 론

    일반적인 최적경로탐색의 기본가정은 기점노드에서 종점노드까지 최소비용경로를 경유하여 완전하게 도 착하였음을 의미하는 종점노드도착조건에 기반하고 있다. 이 조건에서 최적경로탐색문제는 Node-to-Node 문 제(이하 NN문제)로 정의될 수 있다. NN문제는 네트워크 속성이 변하지 않는 상황에서 유용하게 적용 가능 하다. NN문제의 해법으로 노드표지(Node Label; Moore, 1958;Dijkstra, 1959;Choi, 1995)와 링크표지(Link Label; Kirby and Potts, 1969;Lee, 2004)를 적용하는 최적경로탐색기법이 응용된다. 노드표지기반 최적경로알 고리즘은 기점노드에서 전체노드를 연결하는 최소노드비용트리(Minimum Node Cost Tree)를 구축하며 링크 표지기반 최적경로알고리즘은 기점노드에서 전체링크를 연결하는 최소링크비용트리(Minimum Link Cost Tree)를 구축하여 최적경로를 탐색한다.

    본 연구는 기점노드에서 종점노드까지 최소비용경로를 경유하나 완전하게 종점노드에 도착하지 않은 상황 에서의 경로탐색문제를 다루고자 한다. 이 문제는 종점노드도착조건이 적용되지 않는 최적경로탐색문제로서 특정 링크(자세하게는 링크의 도착지점)까지 경로를 탐색한다는 측면에서 Node-to-Link 문제(또는 Link-to-Node 문제와 동일; 이하 NL문제)로 정의한다. NL문제는 실시간 변화하는 현실의 교통네트워크에서 정확한 정보제공 을 위해서 보편적으로 고려해야 하는 개념이다. 예를 들면 실시간 교통상황 정보를 바탕으로 내비게이션이 갱신하는 통행정보를 수신하는 지점은 정확하게는 교차로가 아닌 교차로로 접근하는 링크인 경우가 대부분이 다. 본 연구자가 추측하건대 내비게이션의 경로탐색알고리즘은 링크의 도착지점인 교차로를 기점노드로 재산 정하여 NN문제에 적합한 해법으로 변환하여 종점노드까지 최적경로를 탐색하는 것으로 판단된다.

    그러나 NN으로 재정산된 해법은 노드에서 회전페널티가 존재하는 상황- 링크표지기반 최적경로탐색의 적 용이 요구되는 –에서 최적해를 도출하지 못하는 문제가 발생한다. <Fig. 1>은 노드①에서 회전 ⓡ①② 방향 으로 페널티 1 ⓡ①③ 방향으로 페널티 10이 존재하는 기하구조에서 차량이 링크(ⓡ①)에서 갱신된 정보를 수집하는 상황을 나타낸 것이다. 이때 종점노드(④)까지 최적경로는 비용8의 ⓡ①②④이다. 노드에서 재산정 된 경로를 나타내는 <Fig. 2>는 노드(①)에서 최적경로는 비용6의 ①③②④로서 보여준다. 따라서 링크(ⓡ ①)에서 연결된 경로비용 16의 경로 ⓡ①③②④로 고려할 때 최적해의 도출에 실패했음을 예시한다.

    최근 교통정보를 실시간 갱신하는 ‘적응적 경로탐색(Adaptive, Progressive, Variable Path Search)’의 필요성 이 대두되면서 이러한 NL기반 최적경로탐색에 대한 정확한 해법이 요구되고 있다. 그러나 지금까지 NL문제 에 대한 해법을 검토한 사례가 매우 부족하다.

    본 연구는 NL문제에 대한 최적경로탐색기법을 제안하기 위하여 One-to-One K-경로탐색기법(Martins, 1984;Azevedo et al., 1993;Shin, 2004;Lee, 2017)을 활용하는 방안을 강구한다. K경로탐색은 Lee(2017)이 제안한 M-유사경로탐색(M-Similar Path Search)과 같이 비가산성경로비용(Non Additive Path Cost)이 발생하는 네트워 크에서 M개의 경로열거를 통하여 최적경로(M=1)를 선택하는 경험적 방법론으로 적용이 가능하다. 이를 위 해 본 연구는 One-to-One K-경로탐색기법에서 진입링크기반 전체경로삭제기법(Incoming Link Based Entire Path Deletion Method; Azevedo et al., 1993;Shin, 2004;Lee, 2017)을 중심으로 네트워크변형을 통해서 최적경 로를 탐색하는 알고리즘을 제안한다.

    Ⅱ. 이론적 배경

    회전페널티가 있는 노드속성이 존재하는 네트워크에서 링크표지기반 최적경로탐색은 네트워크를 확장하 지 않고 최적조건(Optimality Condition; Bellman, 1957)이 보장되어 최적경로가 탐색된다. 본 장은 링크표지를 도입하여 최적경로탐색과 진입링크기반 전체경로삭제기법에 적용되는 과정을 설명한다.

    1. 링크표지기반 최적경로탐색

    노드표지기반 경로탐색(Moore, 1968; Dijkstra, 1969)은 기점에서 모든 노드까지 최적노드트리를 구축하여 경 로를 탐색한다. 링크표지기반 경로탐색(Kirby and Potts, 1969;Lee, 2004)은 기점에서 모든 링크까지 최적링크트 리를 구축하여 경로를 탐색한다. <Fig. 3>은 최적경로트리의 구축사례를 보여주고 있다. 기점노드①에서 모든 노드를 1회만 방문하는 나무(Tree)를 구축한다. (식1)은 노드표지갱신(Node Label Correcting ; Moore, 1958) 또는 노드표지확정(Node Label Setting ; Dijkstra, 1959)으로 탐색되는 재귀수식(Recursive Equation)을 나타내고 있다.

    π r j = min ( π r i + c i j , π r j )   ∀ i j ∈ Γ j −
    (식1)

    여기서

    • π r j 는 기점노드 r부터 노드j까지 최적통행비용;

    • cij는 링크(ij)의 통행비용;

    • Γ j − 는 도착노드가 j인 링크집합;

    <Fig. 4>는 <Fig. 3>의 동일한 네트워크에 노드②를 중심으로 ①②④ 방향으로 회전페널티 5, ①③②④ 방 향으로 회전페널티 10에 해당하는 네트워크에 대하여 최적링크트리를 구축한 사례이다. 모든 링크의 도착노 드에 근접되는 지점까지 산정된 최적링크비용을 보여주고 있다. 노드②는 링크(①②)와 링크(③②)가 동시에 근접되어 있어 노드②까지의 최적통행비용은 두 링크의 비교를 통하여 5로 결정된다.

    π r b = min ( π r a + d a b + c b , π r b )   ∀ a ∈ Γ b −
    (식2)

    여기서

    • πrb는 기점노드 r부터 링크b까지 최적통행비용;

    • dab는 링크(a)에서 링크(b)로의 회전비용;

    • cb는 링크(b)의 통행비용;

    • Γ b − 는 도착노드가 링크b의 출발노드인 링크집합;

    식(2)가 모든 노드에서 종점노드도착조건을 달성하기 위해서는 NL문제에서 NN문제로의 전환을 선언할 필요가 있다. (식3)은 노드j에 종점노드도착조건은 j를 도착노드로 연결된 모든 링크( ∀ a ( i j ) ∈ Γ j − 를 검토 하는 상황이 요구됨을 의미한다. 따라서 최적링크트리로 구축된 NL문제는 링크 상의 진행을 의미하기 때문 에 최적노드트리로 전환(선언)하기 위한 별도의 작업이 필요하다. (식3)은 최적링크트리가 최적노드트리에 근접하는 조건을 표현하는 적응적 경로탐색에 요구되는 적정한 조건으로 파악된다.

    π r j = min ( π r a )   ∀ a ( i j ) ∈ Γ j −
    (식3)

    2. 진입링크기반 전체경로삭제기법

    One-to-One K경로탐색기법으로 부분경로삭제기법(Yen, 1963)과 전체경로삭제기법(Martins, 1984;Avezedo et al, 1993;Shin, 2004;Lee, 2017)으로 구분된다. 부분경로삭제기법은 링크단위의 경로를 단절(삭제)하여 K개 의 경로를 탐색하는 방법이다. 전체경로삭제기법은 K-1번째 전체경로를 삭제해서 K번째 경로를 탐색하는 방 법이다. 전체경로삭제기법은 구현하기는 어려우나 성능은 부분경로삭제기법에 비하여 월등한 것으로 평가된 다(Shin, 2004). 전체경로삭제기법은 유출링크기반 네트워크변형기법(Outgoing Link Based Network Transformation: OLBNT; Martins, 1984)과 유입링크기반 네트워크변형기법(Incoming Link Based Network Transformation: ILBNT; Avezedo et al., 19993;Shin, 2004;Lee, 2017)으로 대별된다.

    Avezedo et al.(1993)은 경로의 루프를 허용하는 ILBNT기법을 제안했다. ILBNT의 과정을 설명하기 위하여 표식을 정의하면 다음과 같다. 네트워크 N 의 경로 p를 노드순서로 표현하면 p = { υ 0 , υ 1 , ⋯ , υ m − 1 , υ m } ,   υ 0 = r 로서 기점노드, υm = s 로서 종점노드, m ≥ 3, 특정 노드 υ 와 연결된 유입링크집합(Incoming Links Set)은 I ( υ ) = { ( υ , u ) ∈ A | υ , u ∈ N } 이다. 경로p를 삭제하여 네트워크 N’ 을 생성하기 위하여 새로운 노드 를 추가하고 이들 노드에서 유입링크를 연결하여 N 의 최적경로를 삭제하는 것으로 다음의 3단계 과정을 수 행한다.

    • 단계1 : N = N ∪ { υ 1 , ⋯ , υ m − 1 }

    • 단계2 : I ( υ ′ 1 ) = { ( u , υ ′ 1 ) | ( u , υ 1 ) ∈ I ( υ 1 ) ; u ≠ υ 0 } I ( υ ′ j ) = { ( u , υ ′ j ) | ( u , υ j ) ∈ I ( υ j ) ; u ≠ υ j − 1 } ∪ { ( υ ′ j − 1 , υ ′ j ) } ,   ∀ j ∈ { 2 , ⋯ , m − 1 }

    • 단계3 : I ( υ m ) = I ( υ m ) − { ( υ m − 1 , υ m ) } ∪ { ( υ ′ m − 1 , υ m ) }

    Avezedo et al(1993)의 ILBNT기법은 루프를 생성하는 문제가 발생한다. <Fig. 5>의 2-노드 2-링크로 구성된 기본네트워크(Fig. 5-a)를 초기네트워크변형을 통하여 네트워크 N 은 <Fig. 5-b>와 같다. 이때 최적경로는 ⓡ ①②ⓢ이다. 네트워크 N’ 을 구축하는 과정에서 진입링크를 연결하면 ⓡ①②①②ⓢ로 노드 및 링크루프가 생성된다(Fig. 5-c). Shin(2004)는 링크표지를 도입하여 노드 및 경로루프를 선택적 탐색과정에서 삭제하여 교 통망에서 적합한 알고리즘으로 변형하였다. Shin(2004)이 제안한 알고리즘은 <Fig. 5-(b)>에서 종료된다. Lee(2017)는 Shin(2004)이 제안한 링크표지기반 알고리즘을 대상으로 비가산성경로비용이 존재하는 네트워크 에 대하여 M개의 유사경로를 선택하는 기법을 제안하였다.

    3. 비가산성경로비용과 M-유사경로탐색기법

    M-유사경로는 최적경로비용과 차이가 오차범위 내의 M개의 경로를 말한다. 이 가정을 도입하면 2번째 경 로비용이 최적경로비용과 비교하여 차이가 크면 M=1의 최적경로가 유사경로가 된다. 대규모 네트워크에서 경로비용을 정확하게 산출하는 것이 용이하지 않기 때문에 경로비용이 차이가 나지 않다고 판단되는 경로를 유사경로집합(Similar Path Set)으로 정의한다.

    Lee(2017)가 도입한 M-유사경로의 기본가정은 K-경로탐색을 비용 순차적으로 나열하여 충분하게 큰 K개 의 경로에서 M개의 유사경로를 선출하는 과정이다. 우선 K-경로는 네트워크의 경로비용가정이 가산성 (Additivity)을 기본으로 동적계획법(Dynamic Programming)의 적용을 위한 최적조건이 만족되는 상황에서 적 용 가능하다(Bellman, 1957). 이 판단근거는 경로를 구성하는 링크와 회전에서 발생하는 비용의 합이 경로비 용과 동일하다는 가정 하에서 적용된다. 그러나 Bellman(1957)의 최적조건이 성립되지 않는 상황의 하나인 비가산성경로비용(Gabriel and Bernstein, 1997;Shin et al, 2016)이 포함되는 네트워크는 K-경로로 인해 도출된 비용이 경로비용과 일치하지 않는 문제가 발생한다. Lee(2017)는 K개의 개별적 경로비용을 비가산성경로비 용으로 환산하는 과정을 도입하여 최종적으로 M-개의 유사경로를 선출하는 방법론을 도입하였다. LBNT기 법에서는 탐색된 전체경로의 원형이 보존되는 장점이 있기 때문에 방법론의 구축과정이 단순하게 진행된다. <Fig. 6>는 Lee(2017)가 제안한 M-유사경로의 도출과정을 보여주고 있다.

    Ⅲ. Node-to-Link 최적경로탐색

    본 연구에서 도입하는 기본가정은 Lee(2017)는 제안한 M-유사경로에서 1st로 선택된 경로를 최적경로로 인 정하는 것이다. Lee(2017)는 M-유사경로에서 경로를 선택하는 과정에서 NN문제 기반의 해법을 적용하였다. 따라서 본 연구는 Lee(2017)의 알고리즘에서 NL문제 기반의 해법으로 전환하는 과정이 요구된다. NL은 종점 노드도착조건을 만족하지 않으면서 링크도착노드까지 최적경로를 탐색하는 것이다. 본 장에서는 Azevedo et al.(1993)과 Shin(2004)의 네트워크변형 및 링크표지기반 경로탐색을 2가지 방법론에서 검토하는 방안을 도출 한다. 첫 번째는 종점노드와 연계되는 방향을 삭제하는 방안이고 두 번째는 종점노드와 연계되는 방향에 회 전금지를 도입하는 방안이다.

    1. 종점링크 연계방향 삭제방안

    이 기법은 종점링크로 연결된 방향을 제외하고 모든 방향을 삭제하는 방법을 적용한다. <Fig. 7>은 기점노 드①에서 종점링크②④의 경로탐색을 위한 방향이 삭제된 네트워크변형을 보여주고 있다. 링크②④를 포함 하지 않은 방향 ⑤④ⓢ로 통행이 단절된 네트워크(N)를 구축한다. <Fig. 8>은 NL기반 알고리즘의 수행과정 을 예시하는 결과로서 <Fig. 8-(a)>는 종점링크②④로 1st 경로선택이 ⓡ➀➂➁➃ⓢ로 진행되었으며 ➁➃ⓢ로 의 방향을 유지하여 종점링크➁➃의 통행비용이 도출됨을 나타낸다. <Fig. 8-(b)>는 1st 경로가 삭제된 네트워 크(N’)에 대하여 2nd 경로탐색의 결과를 나타내고 있으며 경로가 ⓡ➀➁➃ⓢ로 도출되어 종점링크➁➃의 통 행이 경로에 포함되었음을 예시하고 있다.

    2. 종점링크 연계방향 회전금지방안

    이 기법은 종점링크로 연결된 방향을 제외하고 모든 방향에 회전을 금지하는 방법을 적용한다. <Fig. 8>은 기점노드①에서 종점링크②④의 경로탐색을 위한 회전금지가 포함된 네트워크변형을 보여주고 있다. 링크② ④를 포함하지 않은 방향 ⑤④ⓢ로 통행이 회전금지로 처리되도록 네트워크(N)를 구축한다. <Fig. 9>는 NL 기반 알고리즘의 수행과정을 예시하는 결과로서 <Fig. 9-(a)>는 종점링크②④로 1st 경로선택이 ⓡ①③②④ⓢ 로 ②④ⓢ로의 방향을 유지하여 종점링크➁➃의 통행비용이 도출됨을 나타낸다. <Fig. 9-(b)>는 1st 경로가 삭 제된 네트워크(N’)에 대하여 2nd 경로탐색의 결과를 나타내고 있는 경로가 ⓡ①②④ⓢ로 도출되어 종점링크 ②④의 통행이 경로에 포함되었음을 예시하고 있다. 네트워크변형과정에서 회전금지정보가 계속 갱신되는 과정을 나타내고 있다. Fig. 10

    Ⅳ. 결 론

    기존의 Node-to-Node기반 최적경로탐색은 기점노드에서 모든 노드에 종점노드도착조건이 성립되는 가정 으로 구축되었다. 최근 적응적 경로탐색의 필요에 따라 Node-to-Node의 경로탐색이 최적해를 도출하지 못하 는 한계가 존재한다. 따라서 Node-to-Link(또는 Link-to-Node)의 경로탐색기법에 대한 검토를 통해 실시간 정 보를 갱신하는 적합한 경로탐색기법이 요구된다.

    본 연구는 Node-to-Link의 정확한 해법을 구축하는 방안으로서 링크표지를 도입하고 비가산성경로비용이 존재하는 네트워크를 가정하여 M-유사경로기법에 적용하기 위한 네트워크 변형기법으로 종점링크 연계방향 삭제기법과 회전금지방안을 제안하였다.

    본 연구는 이론적 배경에 한정되어 있으나 다양한 사례연구의 적용이 가능할 것으로 기대된다.

    ACKNOWLEDGEMENTS

    이 논문은 ‘수도권 통행인구의 공간이동 실태분석 및 시사점-대중교통카드자료를 중심으로(2015, 국토연 구원)’연구를 바탕으로 확대한 것임

    Figure

    KITS-18-5-91_F1.gif

    Optimal Path from Node ④ to Link ⓡ①

    KITS-18-5-91_F2.gif

    Optimal Path from Node ④ to Node ①

    KITS-18-5-91_F3.gif

    Network and Optimal Node Tree

    KITS-18-5-91_F4.gif

    Network and Optimal Link Tree

    KITS-18-5-91_F5.gif

    Base Network, Initial Network Transformation, Path Finding

    KITS-18-5-91_F6.gif

    Path Cost Update and Selection of M-Similar Path

    KITS-18-5-91_F7.gif

    Direction Deletion to Destination Node

    KITS-18-5-91_F8.gif

    Optimal Path Finding of Direction Deletion Method

    KITS-18-5-91_F9.gif

    Direction Prohibition to Destination Node

    KITS-18-5-91_F10.gif

    Optimal Path Finding of Direction Prohibition Method

    Table

    Reference

    1. Azevedo J. A. , Costa M. E. O. S. , Madeira J. J. E. R. S. and Martins E. Q. V. (1993), “An Algorithm from the Ranking of Shortest Paths,” European Journal of Operational Research, vol. 69, pp.97-106.
    2. Bellman R. (1957), Dynamic Programming, Princeton University Press, Princeton, New Jersey.
    3. Choi K. (1995), “Network Representation Schemes for U-TURN and Implementation in the Vine-Based Dijkstra Shortest Path Algorithm,” Journal of Korean Society of Transportation, vol. 13, no. 3, pp.35-52.
    4. Dijkstra E. W. (1959), “A Note on Two Problems in Connexion with Graphs,” Numerische Mathematik, vol. 1, pp.269-271.
    5. Gabriel S. and Bernstein D. (1997), “The Traffic Equilibrium Problem With Nonadditive Path Costs,” Transportation Science, vol. 20, no. 5, pp.337-348.
    6. Kirby R. F. and Potts R. B. (1969), “The Minimum Route Problem for Networks with Turn Penalties and Prohibitions,” Transportation Research, vol. 3, pp.397-408.
    7. Lee M. (2004), Transportation Network Models and Algorithms Considering Directional Delay and Prohibitions for Intersection Movement, Ph.D. Thesis, University of Wisconsin at Madison.
    8. Lee M. (2017), “Transportation Card Based Optimal M-Similar Paths Searching for Estimating Passengers’ Route Choice in Seoul Metropolitan Railway Network,” The Journal of The Korea Institute of Intelligent Transport Systems, vol. 16, no. 2, pp.1-12.
    9. Martins E. Q. V. (1984), “An Algorithm for Ranking paths THat May Contain Cycles,” European Journal of Operational Research, vol. 18, pp.123-130.
    10. Moore E. F. (1957), “The Shortest Path Through A Maze,” Proceedings of An International . Conference of Symposium on the Theory of Switching, Harvard University, Cambridge, MA.
    11. Shin S. and Baek N. (2016), “A Logit Type of Public Transit Trip Assignment Model Considering Stepwise Transfer Coefficients,” Journal of Korean Society of Transportation, vol. 34, no. 6, pp.570-579.
    12. Shin S. (2004), “Finding the First K Loopless Paths in A Transportation Network,” Journal of Korean Society of Transportation, vol. 22, no. 6, pp.121-131.
    13. Shin S. , Baek N. and Nam D. (2016), “A Heuristic Optimal Path Search Considering Cumulative Transfer Functions,” The Journal of The Korea Institute of Intelligent Transport Systems, vol. 15, no. 3, pp.60-67.
    14. Yen J. Y. (1971), “Finding the K Shortest Loopless Paths in A Network,” Management Science, vol. 17, pp.711-715.

    저자소개

    Footnote