복합대중교통망의 링크표지갱신 다목적 경로탐색

이미영,김형철,박동주,신성일 대한교통학회 2008 대한교통학회지 Vol.26 No.1

Generally, optimum shortest path algorithms adopt single attribute objective among several attributes such as travel time, travel cost, travel fare and travel distance. On the other hand, multi-objective shortest path algorithms find the shortest paths in consideration with multi-objectives. Up to recently, the most of all researches about multi-objective shortest paths are proceeded only in single transportation mode networks. Although, there are some papers about multi-objective shortest paths with multi-modal transportation networks, they did not consider transfer problems in the optimal solution level. In particular, dynamic programming method was not dealt in multi-objective shortest path problems in multi-modal transportation networks. In this study, we propose a multi-objective shortest path algorithm including dynamic programming in order to find optimal solution in multi-modal transportation networks. That algorithm is based on two-objective node-based label correcting algorithm proposed by Skriver and Andersen in 2000 and transfer can be reflected without network expansion in this paper. In addition, we use non-dominated paths and tree sets as labels in order to improve effectiveness of searching non-dominated paths. We also classifies path finding attributes into transfer and link travel attribute in limited transit networks. Lastly, the calculation process of proposed algorithm is checked by computer programming in a small-scaled multi-modal transportation network. 교통망에서 출발지와 도착지를 연결하는 최적경로탐색(Optimum Shortest Path)의 기준은 통행시간, 통행비용, 통행요금, 통행거리 등 복수의 기준에서 단일기준(Single Attribute Objective)을 선정하여 선정된 기준에 대하여 최소화되는 경로를 탐색하는 것을 의미하며 최적경로 탐색기법으로 탐색이 가능하다. 다목적 경로탐색(Multi-Objective Shortest Paths)에서는 이들 복수의 기준(Multi-Objective)을 고려하여 경로를 탐색한다. 최근까지 다목적경로탐색에 대한 연구는 대부분 단일의 교통수단만으로 구성된 교통망에 대한 가정을 기반으로 이루어졌으며, 다수의 교통수단이 혼재된 교통망(Multi-Modal Transportation Network)에서 다목적경로탐색에 대한 연구는 환승에 대한 문제를 최적해법 차원에서 고려하지 않았으며, 교통정보 분야에서 일반적으로 적용되는 동적계획법(Dynamic Programming)에 기반한 알고리즘에 대한 연구는 다수단교통망에서 다목적경로탐색 문제에서 검토되지 않았다. 본 연구는 다수단교통망에서 다목적경로탐색 문제에서 최적 해를 도출하기 위한 동적계획법 알고리즘을 제안한다. 제안된 알고리즘은 Skriver & Andersen (2000)이 제시한 2기준 노드표지갱신 알고리즘을 기반으로 네트워크의 확장 없이 수단 간의 환승이 반영되도록 2기준 이상의 다기준 링크표지갱신 알고리즘으로 개발하는 방안으로 확대한다. 본 연구는 다기준 링크표지가 다수단 교통망에 적용했다는 점 이외에, 출발지에서 모든 링크까지 비지배경로를 탐색하는 과정이 효율적으로 이루어지도록 출발지에서 개별 링크까지의 비지배경로/트리(Path/Tree) 집합을 표지처럼 활용하였다. 다수단교통망에서 다목적경로탐색문제에 적합한 도시부의 대중교통망에 한정하여 경로탐색속성을 환승과 링크주행속성으로 구분하였다. 본 연구에서 제안된 알고리즘의 계산과정을 소규모 복합대중교통망을 통해 검증하였다.

선호도 기반 최단경로 탐색을 위한 휴리스틱 융합 알고리즘

옥승호(Seung-Ho Ok),안진호(Jin-Ho Ahn),강성호(Sungho Kang),문병인(Byungin Moon) 大韓電子工學會 2010 電子工學會論文誌-TC (Telecommunications) Vol.47 No.8

본 논문에서는 개미 군집 최적화 (Ant Colony Optimization; ACO) 및 A* 휴리스틱 알고리즘이 융합된 선호도 기반 경로탐색 알고리즘을 제안한다. 최근 ITS (Intelligent Transportation Systems)의 개발과 함께 차량용 내비게이션의 사용이 증가하면서 경로탐색 알고리즘의 중요성이 더욱 높아지고 있다. 기존의 Dijkstra 및 A*와 같은 대부분의 최단경로 탐색 알고리즘은 최단거리 또는 최단시간 경로 탐색을 목표로 한다. 하지만 이러한 경로 탐색 결과는 더 안전하고 특정 경로를 선호하는 운전자를 위한 최적의 경로가 아니다. 따라서 본 논문에서는 선호도 기반 최단 경로 탐색 알고리즘을 제안한다. 제안된 알고리즘은 주어진 맵의 링크 속성 정보를 이용하며, 각 링크에 대한 사용자 선호도는 내비게이션 사용자에 의해 설정되어 진다. 제안된 알고리즘은 C로 구현하였으며, 64노드 및 118링크로 구성된 맵에서 다양한 파라미터를 통해 성능을 측정한 결과 본 논문에서 제안한 휴리스틱 융합 알고리즘은 선호도 기반 경로뿐만 아니라 최단 경로 탐색에도 적합함을 알 수 있었다. In this paper, we propose a preference-based shortest path algorithm which is combined with Ant Colony Optimization (ACO) and A* heuristic algorithm. In recent years, with the development of ITS (Intelligent Transportation Systems), there has been a resurgence of interest in a shortest path search algorithm for use in car navigation systems. Most of the shortest path search algorithms such as Dijkstra and A* aim at finding the distance or time shortest paths. However, the shortest path is not always an optimum path for the drivers who prefer choosing a less short, but more reliable or flexible path. For this reason, we propose a preference-based shortest path search algorithm which uses the properties of the links of the map. The preferences of the links are specified by the user of the car navigation system. The proposed algorithm was implemented in C and experiments were performed upon the map that includes 64 nodes with 118 links. The experimental results show that the proposed algorithm is suitable to find preference-based shortest paths as well as distance shortest paths.

센서 네트워크 환경에서 멀티 레이어 그리드 라우팅 알고리즘을 이용한 최단 경로 탐색 기법

추명진,이선형,조지용,조용환 한국엔터테인먼트산업학회 2012 한국엔터테인먼트산업학회논문지 Vol.6 No.2

본 논문에서는 TTDD 알고리즘의 우회문제를 해결하기 위해 멀티 레이어 그리드를 활용하는 MLGR(Multi Layer Grid Routing) 라우팅 알고리즘을 제안한다. MLGR 알고리즘은 기존의 사각형 그리드를 기반으로 대각선 방향에 위치한 센서노드간의 위치 정보 등록을 통해 멀티 레이어 그리드를 구성한다. 또한 라우팅 경로를 선정하기 위해 최단 경로 선정 알고리즘(Path Selection Algorithm)을 활용하여 사각형 그리드와 멀티 레이어 그리드의 라우팅 경로를 탐색하고 데이터 이동이 가능한 최단 경로를 선정해준다. 만약 센서 네트워크에서 노드의 에너지 고갈이나 통신 대역폭 증가로 인해 통신상에 문제가 발생할 경우, 이를 해결하기 위해 경로 상태 점검 알고리즘(Link State Check Algorithm)을 활용하여 인접 경로들의 노드상태와 통신 대역폭을 점검한다. 통신상태 점검을 마친 인접 경로들은 최단 경로 선정 알고리즘을 활용해 문제가 발생한 지점을 우회할 수 있는 경로를 선택해준다. In this paper, MLGR(Multi Layer Grid Routing) routing algorithm by using multi layer grid was suggested for resolving detour problem of the TTDD algorithm. For selecting routing path, the MLGR routing algorithm uses the shortest path selection algorithm, and this can select shortest path and investigate routing path of square and multi layer grids. In the case of communication problem caused by bandwidth increasing or energy shortage of node in sensor network, link state check algorithm will be used for solving the problem. The adjacent paths that finished state check select detour path that bypasses the node which is in trouble by using the shortest path selction algorithm. MLGR algorithm solves the detour problem of conventional TTDD algorhithm through diagonal communication between sensor nodes, and provides energy efficient sensor network environment by using the shortest path selection algorithm and link state check algorithm.

최소신장트리를 이용한 무방향 그래프의 점대점 최단경로 탐색 알고리즘

이상운(Sang-Un Lee) 한국컴퓨터정보학회 2014 韓國컴퓨터情報學會論文誌 Vol.19 No.7

본 논문은 실시간 GPS 항법시스템에서 최단경로 탐색에 일반적으로 적용되고 있는 Dijkstra 알고리즘을 양방향 통행로(무방향그래프)로만 구성된 도로에 적용하고 문제점을 개선한 알고리즘을 제안하였다. Dijkstra 알고리즘은 방향 그래프에서 출발 노드부터 시작하여 그래프의 모든 노드에 대한 최단경로를 결정하기 때문에 알고리즘 수행에 많은 메모리가 요구되어 실시간으로 정보를 제공하지 못할 수도 있다. 이러한 문제점을 해결하고자, 본 논문에서는 무방향 그래프에 적합하도록 출발과 목적지 정점을 제외한 경로 정점들에 대해 최단경로를 설정하고, 출발 정점부터 시작하여 정점 유출 간선들에 대해 최단경로 설정 간선들과 일치하는 간선들을 모두 선택하는 방식으로 한 번에 다수의 정점들을 탐색하는 방법을 택하였다. 9개의 다양한 무방향 그래프에 제안된 알고리즘을 적용한 결과 모두 최단경로를 탐색하는데 성공하였다. 또한, 수행 속도 측면에서 Dijkstra 알고리즘보다 약 60%를 단축시키는 효과를 얻었으며, 알고리즘 수행에 필요한 메모리도 월등히 적게 요구되었다. This paper proposes a modified algorithm that improves on Dijkstra's algorithm by applying it to purely two-way traffic paths, given that a road where bi-directional traffic is made possible shall be considered as an undirected graph. Dijkstra's algorithm is the most generally utilized form of shortest-path search mechanism in GPS navigation system. However, it requires a large amount of memory for execution for it selects the shortest path by calculating distance between the starting node and every other node in a given directed graph. Dijkstra's algorithm, therefore, may occasionally fail to provide real-time information on the shortest path. To rectify the aforementioned shortcomings of Dijkstra's algorithm, the proposed algorithm creates conditions favorable to the undirected graph. It firstly selects the shortest path from all path vertices except for the starting and destination vertices. It later chooses all vertex-outgoing edges that coincide with the shortest path setting edges so as to simultaneously explore various vertices. When tested on 9 different undirected graphs, the proposed algorithm has not only successfully found the shortest path in all, but did so by reducing the time by 60% and requiring less memory.

방향그래프의 점대점 최단경로 탐색 알고리즘

이상운(Sang-Un Lee) 한국지능시스템학회 2007 한국지능시스템학회논문지 Vol.17 No.7

본 논문은 실시간 GPS 항법시스템에서 최단 경로를 탐색하는데 일반적으로 적용되고 있는 Dijkstra 알고리즘의 문제점을 개선한 알고리즘을 제안하였다. Dijkstra 알고리즘은 출발 노드부터 시작하여 그래프의 모든 노드에 대한 최단 경로를 결정하기 때문에 일반적으로 노드의 수 - 1회를 수행해야 하며, 알고리즘 수행에 많은 메모리가 요구된다. 따라서 Dijkstra 알고리즘은 복잡한 도시의 도로에서 목적지 까지 최단 경로를 탐색하여 실시간으로 정보를 제공하지 못할 수도 있다. 이러한 문제점을 해결하고자, 본 논문에서는 먼저 출발과 목적지 노드를 제외한 경로 노드들의 최단 경로 (유입과 유출 최소 가중치 호 선택)를 결정하고, 출발 노드부터 시작하여 노드 유출 호들에 대해 경로 노드의 최단 경로와 일치하는 호들을 모두 선택하는 방식으로 한번에 다수의 노드들을 탐색하는 방법을 택하였다. 14개의 다양한 방향 그래프에 제안된 알고리즘을 적용한 결과 모두 최단 경로를 탐색하는데 성공하였다. 또한, 수행 속도 측면에서 Dijkstra 알고리즘보다 2배에서 3배 정도 빠른 결과를 얻었으며, 알고리즘 수행에 필요한 메모리도 적게 요구되었다. This paper suggests an algorithm that improves the disadvantages of the Dijkstra algorithm that is commonly used in GPS navigation system, searching for the shortest path. Dijkstra algorithm, first of all, requires much memory for the performance of the algorithm. It has to carry out number of node minus 1, since it determines the shortest path from all the nodes in the graph, starting from the first node. Therefore, Dijkstra algorithm might not be able to provide the information on every second, searching for the shortest path between the roads of the congested city and the destination. In order to solve these problems, this paper chooses a method of searching a number of nodes at once by means of choosing the shortest path of all the path nodes (select of minimum weight arc in-degree and out-degree), excluding the departure and destination nodes, and of choosing all the arcs that coincide with the shortest path of the path nodes, from all the node outgoing arcs starting from the departure node. On applying the suggested algorithm to 14 various digraphs, we succeeded to search the shortest path. In addition, the result was obtained at the speed of 2 to 3 times faster than that of Dijkstra algorithm, and the memory required was less than that of Dijkstra algorithm.

동적 라우팅 알고리즘의 신뢰성 향상을 위한 최단 경로 설정 알고리즘

조태환(Tae Hwan Cho),김지원(Ji Won Kim),김병조(Byoung Jo Kim),윤완오(Wan Oh Yoon),최상방(Sang Bang Choi) 한국정보과학회 2011 정보과학회논문지 : 정보통신 Vol.38 No.6

네트워크 토폴로지의 일부분에 변화가 생겼을 때, 효율적으로 최단경로를 설정 할 수 있는 대표적인 알고리즘으로 DSPT(Dynamic Shortest Path Tree)가 있다. 그러나 링크 비용이 증가하는 경우 DSPT 증가 알고리즘은 잘못된 최단경로를 계산한다. 따라서 본 논문에서는 DSPT 증가 알고리즘을 개선하여 신뢰성 있는 최단경로를 계산하는 P-DSPT(Precise-Dynamic Shortest Path Tree) 알고리즘과 RDSP(Reliable Dynamic Shortest Path) 알고리즘을 제안한다. 제안된 알고리즘의 성능을 평가하기 위해서 DSPT, 다익스트라 알고리즘 등과 성능을 비교하였으며, 최대 17%의 성능 향상이 있었다. DSPT algorithm is well known for searching altered SPT efficiently as a cost of link is changed. But DSPT algorithm is wrong for some cases. So we will show this with an example, and propose P-DSPT(Precise-Dynamic Shortest Path Tree) and RDSP(Reliable Dynamic Shortest Path) that is a new DSPT algorithm. The result of an evaluation shows that overall performance of the proposed algorithm is improved a maximum of 17% compared with DSPT and well-known Dijkstra algorithm.

Shortest Path Search Scheme with a Graph of Multiple Attributes

Jongwan Kim(김종완),KwangJin Choi(최광진),Dukshin Oh(오덕신) 한국컴퓨터정보학회 2020 韓國컴퓨터情報學會論文誌 Vol.25 No.12

그래프 이론에서 최소비용 경로는 시작 노드와 도착 노드 사이의 최단 경로를 탐색하여 구한다. 최소비용은 두 노드 사이의 거리나 가격의 차이를 1차원 값으로 계산하며 연결된 노드 사이의 최소비용의 합을 구성하는 노드와 간선이 최단 경로다. 그러나 각 노드가 다중속성을 갖는 경우에는 경로에서 나타날 수 있는 비용의 종류 또한 속성의 개수만큼이므로 최단 경로를 판단하기에는 어려움이 있다. 본 논문에서는 사용자의 다양한 요구사항을 만족할 수 있도록 유클리드 거리를 사용하여 다중속성을 반영한 최단 경로 탐색 기법을 제안한다. 실험에서는 1차원 값에 대한 최단 경로와 2차원 속성에 대한 유클리드 거리를 이용한 최단 경로가 다르게 탐색 되었다. 다중속성에서도 단일 속성과 차별화된 사용자의 선호 속성이 반영된 것으로 나타났다. 결과적으로 다중속성이 반영됨으로써 사용자의 다양한 요구사항을 만족시킬 수 있게 되었다. In graph theory, the least-cost path is discovered by searching the shortest path between a start node and destination node. The least cost is calculated as a one-dimensional value that represents the difference in distance or price between two nodes, and the nodes and edges that comprise the lowest sum of costs between the linked nodes is the shortest path. However, it is difficult to determine the shortest path if each node has multiple attributes because the number of cost types that can appear is equal to the number of attributes. In this paper, a shortest path search scheme is proposed that considers multiple attributes using the Euclidean distance to satisfy various user requirements. In simulation, we discovered that the shortest path calculated using one-dimensional values differs from that calculated using the Euclidean distance for two-dimensional attributes. The user’s preferences are reflected in multi attributes and it was different from one-dimensional attribute. Consequently, user requirements could be satisfied simultaneously by considering multiple attributes.

관계형 데이터베이스 상에서 사용하는 최단 경로 탐색 알고리즘(ALT) 설계와 구현

이용현,임동혁,구해모,김형주 한국정보과학회 2019 정보과학회 컴퓨팅의 실제 논문지 Vol.25 No.4

Shortest path search is a major topic in various domains that can be represented by graphs such as traffic information, navigation and computer network. As we approach the age of big data, these graph data and information are getting larger and larger in size compared to the past. Therefore, there is the need to effectively search and analyze large graph data. In order to solve this problem, there have been several researches on graph analysis directly in the database. In this study, an In-RDBMS ALT algorithm(A* algorithm, Landmark, Triangle Inequality) that heuristically searches the shortest paths directly in relational database is proposed. The efficiency of In-RDBMS ALT algorithm is also discussed through comparison with existing In-RDBMS shortest path search algorithm. 최단 경로 탐색은 교통 정보, 네비게이션, 컴퓨터 네트워크 등 그래프로 표현될 수 있는 다양한 도메인에서 사용되는 주제이다. 빅데이터 시대가 도래함에 따라 이러한 그래프 데이터들은 과거에 비해 그 정보와 크기가 비교 불가능할 정도로 커지고 있다. 이에 따라 보다 큰 그래프를 효과적으로 탐색 및 분석할 필요성이 대두되었다. 이를 해결하고자 데이터베이스 내부에서 직접 그래프 분석을 하는 여러 연구들이 진행되어 왔다. 본 논문에서는 최단 경로를 관계형 데이터베이스 내부에서 직접 휴리스틱하게 탐색하는 In-RDBMS ALT 알고리즘(A* 알고리즘, Landmark, Triangle Inequality)을 제안한다. 또한 기존의 In-RDBMS 최단 경로 탐색 기법과의 성능 비교를 통하여 In-RDBMS ALT 알고리즘의 효율성에 대해서도 논의해보고자 한다.

A New Link-Based Single Tree Building Algorithm for Shortest Path Searching in an Urban Road Transportation Network

Suhng, Byung Munn,Lee, Wangheon The Korean Institute of Electrical Engineers 2013 Journal of Electrical Engineering & Technology Vol.8 No.4

The shortest-path searching algorithm must not only find a global solution to the destination, but also solve a turn penalty problem (TPP) in an urban road transportation network (URTN). Although the Dijkstra algorithm (DA) as a representative node-based algorithm secures a global solution to the shortest path search (SPS) in the URTN by visiting all the possible paths to the destination, the DA does not solve the TPP and the slow execution speed problem (SEP) because it must search for the temporary minimum cost node. Potts and Oliver solved the TPP by modifying the visiting unit from a node to the link type of a tree-building algorithm like the DA. The Multi Tree Building Algorithm (MTBA), classified as a representative Link Based Algorithm (LBA), does not extricate the SEP because the MTBA must search many of the origin and destination links as well as the candidate links in order to find the SPS. In this paper, we propose a new Link-Based Single Tree Building Algorithm in order to reduce the SEP of the MTBA by applying the breaking rule to the LBA and also prove its usefulness by comparing the proposed with other algorithms such as the node-based DA and the link-based MTBA for the error rates and execution speeds.

A New Link-Based Single Tree Building Algorithm for Shortest Path Searching in an Urban Road Transportation Network

Byung Munn Suhng,Wangheon Lee 대한전기학회 2013 Journal of Electrical Engineering & Technology Vol.8 No.4

The shortest-path searching algorithm must not only find a global solution to the destination, but also solve a turn penalty problem (TPP) in an urban road transportation network (URTN). Although the Dijkstra algorithm (DA) as a representative node-based algorithm secures a global solution to the shortest path search (SPS) in the URTN by visiting all the possible paths to the destination, the DA does not solve the TPP and the slow execution speed problem (SEP) because it must search for the temporary minimum cost node. Potts and Oliver solved the TPP by modifying the visiting unit from a node to the link type of a tree-building algorithm like the DA. The Multi Tree Building Algorithm (MTBA), classified as a representative Link Based Algorithm (LBA), does not extricate the SEP because the MTBA must search many of the origin and destination links as well as the candidate links in order to find the SPS. In this paper, we propose a new Link-Based Single Tree Building Algorithm in order to reduce the SEP of the MTBA by applying the breaking rule to the LBA and also prove its usefulness by comparing the proposed with other algorithms such as the node-based DA and the link-based MTBA for the error rates and execution speeds.