최근, ITS(Intelligent Transportation Systems)의 개발과 함께 차량용 내비게이션의 실시간 교통 정보를 이용하는 수요가 급증하면서, 경로탐색의 중요성이 더욱 가속화되고 있다. 그러나 기존의 경로탐색 알고리즘의 대부분은 최단경로 탐색을 위한 알고리즘으로, 정적인 거리 및 운행 시간정보를 사용하여 최적 경로를 계산하여 운전자에게 제공하기 때문에 교통량에 따라 동적으로 변하는 현 시점에서의 최적의 경로를 제공하지 못하는 문제가 있다. 따라서 본 논문에서는 이를 해결하기 위해 감속률과 거리에 기반한 동적 경로 선정을 위한 의미적 최단거리 알고리즘(Semantic Shortest Path algorithm with Reduction ratio & Distance, SSP_RD)과 감속률과 거리에 기반한 이동 경로 예측 모형화 및 동적 이동 경로 링크 맵을 제안한다.
최근, ITS(Intelligent Transportation Systems)의 개발과 함께 차량용 내비게이션의 실시간 교통 정보를 이용하는 수요가 급증하면서, 경로탐색의 중요성이 더욱 가속화되고 있다. 그러나 기존의 경로탐색 알고리즘의 대부분은 최단경로 탐색을 위한 알고리즘으로, 정적인 거리 및 운행 시간정보를 사용하여 최적 경로를 계산하여 운전자에게 제공하기 때문에 교통량에 따라 동적으로 변하는 현 시점에서의 최적의 경로를 제공하지 못하는 문제가 있다. 따라서 본 논문에서는 이를 해결하기 위해 감속률과 거리에 기반한 동적 경로 선정을 위한 의미적 최단거리 알고리즘(Semantic Shortest Path algorithm with Reduction ratio & Distance, SSP_RD)과 감속률과 거리에 기반한 이동 경로 예측 모형화 및 동적 이동 경로 링크 맵을 제안한다.
Recently, as the use of real time traffic information of a car navigation system increases rapidly with the development of Intelligent Transportation Systems (ITS), path search is getting more important. Previous algorithms, however, are mostly for the shortest distance searching and provide route i...
Recently, as the use of real time traffic information of a car navigation system increases rapidly with the development of Intelligent Transportation Systems (ITS), path search is getting more important. Previous algorithms, however, are mostly for the shortest distance searching and provide route information using static distance and time information. Thus they could not provide the most optimal route at the moment which changes dynamically according to traffic. Accordingly, in this study, Semantic Shortest Path algorithm with Reduction ratio & Distance(SSP_RD) is proposed to solve this problem. Additionally, a routing model based on velocity reduction ratio and distance and a dynamic route link map are proposed.
Recently, as the use of real time traffic information of a car navigation system increases rapidly with the development of Intelligent Transportation Systems (ITS), path search is getting more important. Previous algorithms, however, are mostly for the shortest distance searching and provide route information using static distance and time information. Thus they could not provide the most optimal route at the moment which changes dynamically according to traffic. Accordingly, in this study, Semantic Shortest Path algorithm with Reduction ratio & Distance(SSP_RD) is proposed to solve this problem. Additionally, a routing model based on velocity reduction ratio and distance and a dynamic route link map are proposed.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
따라서 본 논문에서는 이러한 문제점을 해결하기 위해, 감속률과 거리에 기반한 동적 경로 선정을 위한 의미적 최단거리 알고리즘(Semantic Shortest Path algorithm with Reduction ratio & Distance, SSP_RD)을 제안한다.
본 논문에서는 감속률과 거리에 기반한 이동 경로 예측 모형과 이동 경로 링크 맵을 제안하였다. 또한, 제안한 알고리즘이 감속률과 거리에 기반한 동적으로 경로를 찾아가는 알고리즘이라는 것을 증명하기 위해 SSP_RD 알고리즘을 실험하였다.
본 논문에서는 감속률과 거리에 기반한 이동 경로 예측 모형과 이동 경로 링크 맵을 제안한다. 본 논문의 공헌은 다음과 같다.
본 논문에서는 도로혼잡의 상황정보를 기반해 이를 활용하여 최단 시간 및 최소 비용의 변화를 동적으로 반영하는 것이 가능하므로, 감속률과 거리에 기반한 동적 경로 선정을 위한 의미적 최단거리 알고리즘(Semantic Shortest Path algorithm with Reduction ratio & Distance, SSP_RD)을 제안한다.
본 절에서는 감속률과 거리에 기반한 동적 경로 선정을 위한 의미적 최단거리 알고리즘 (Semantic Shortest Path algorithm with Reduction ratio & Distance, SSP_RD)을 제안한다.
본 절에서는 감속률과 거리에 기반한 동적 이동 경로 링크 맵에 대해 설명한다.
본 절에서는 감속률과 거리에 기반한 이동 경로 예측 모형에 대해 설명한다.
본 절에서는 본 논문에서 제안한 감속률과 거리에 기반한 동적 경로 선정을 위한 의미적 최단거리(SSP_RD) 알고리즘의 경로 선정에 있어 중요한 감속률 구하는 식에 대한 설명 및 감속률과 거리에 기반한 동적 경로 선정하는 식에 대해 설명한다.
제안 방법
첫째, 감속률과 거리에 기반한 이동 경로 예측을 모형화하였다. 둘째, 감속률과 거리에 기반한 동적 이동 경로 링크 맵을 제안하였다. 셋째, 감속률과 거리에 기반한 동적 경로 선정을 위한 의미적 최단거리 알고리즘(Semantic Shortest Path algorithm with Reduction ratio & Distance, SSP_RD)을 제안하고, 구현하였다.
목표노드까지의 가장 좋은 경로를 추정하기 위해 각 노드에 랭킹을 부여하는 “Heuristic Estimate”를 사용하고 그 순서대로 노드를 방문한다.
본 논문에서 제안한 감속률과 거리에 기반한 이동 경로 예측 모형은 현재의 눈에 보이는 속도가 아니라 향후 펼쳐질 속도 변화의 트렌드를 반영한 모형을 제안한다.
셋째, 감속률과 거리에 기반한 동적 경로 선정을 위한 의미적 최단거리 알고리즘(Semantic Shortest Path algorithm with Reduction ratio & Distance, SSP_RD)을 제안하고, 구현하였다.
제안하는 감속률과 거리에 기반한 동적 이동 경로 링크 맵은 감속률을 0∼1까지 단계별로 랜덤 비율을 사용하였다.
첫째, 감속률과 거리에 기반한 이동 경로 예측을 모형화하였다. 둘째, 감속률과 거리에 기반한 동적 이동 경로 링크 맵을 제안하였다.
본 논문은 여러 가지 요소들을 확장성 있게 적용할 수 있다. 현재는 감속률과 거리를 적용하여 실험하였다. 그렇지만, 추후에 어떤 요소(연비, 성별, 기후, 관습)을 본 논문에서 제안하는 공식에 넣을 때, 공식에 Weight의 총합이 1이 되도록 조정하면 확장성 있는 방법이 된다.
대상 데이터
본 실험은 노드 21개, 경로 31개로 실험하였고, 감속률은 0∼1까지 랜덤을 사용하였다.
데이터처리
본 논문에서는 감속률과 거리에 기반한 이동 경로 예측 모형과 이동 경로 링크 맵을 제안하였다. 또한, 제안한 알고리즘이 감속률과 거리에 기반한 동적으로 경로를 찾아가는 알고리즘이라는 것을 증명하기 위해 SSP_RD 알고리즘을 실험하였다.
본 장에서는 실험 결과에 대해 설명하고, 본 논문에서 제안하는 SSP_RD 알고리즘을 시간 측정하여 비교하였다.
성능/효과
감속률 W1 0%, 거리 W2 100% 일 경우 시간 측정결과 0.374초, 감속률 W1 30%, 거리 W2 70% 일 경우 0.364초, 감속률 W1 50%, 거리 W2 50%일 경우 0.370초가 나왔다.
결과적으로 노드 경로(0 → 2 → 10 → 13 → 20)가 나왔다.
이때, 감속률 Weight 0%, 거리 Weight 100%는 거리만을 적용한 결과이므로, 본 논문에서 제안한 SSP_RD 알고리즘과 Dijkstra 알고리즘의 결과가 동일한 노드 경로(0 → 3 → 6 → 14 → 20)가 나왔다.
후속연구
감속률과 거리에 기반한 동적 경로 선정 방법을 제안함으로서, 최단 시간 및 최소 비용의 정보를 제공해 줄 뿐만 아니라 일부분의 교통 정체 완화 및 긴 이동 시간으로 인한 사회적 비용 감소의 효과를 가져다 줄 것으로 기대된다.
향후 연구 과제로는 현재 눈에 보이는 속도를 따라갔을 경우와 감속률로 따라갔을 경우의 실험이 필요하겠고, 출발지 노드에서 목적지 노드까지 차선별로 감속률과 거리를 적용하여 동적으로 경로를 선정하는 연구를 진행하고자 한다.
질의응답
핵심어
질문
논문에서 추출한 답변
Dijkstra 알고리즘의 단점은 무엇인가?
하지만, Dijkstra 알고리즘은 Polynomial Time의 시간 복잡도를 가지는 최단경로 알고리즘으로 노드의 수가 증가함에 따라 경로 탐색 시간이 오래 걸린다는 단점이 있다.
경로탐색 알고리즘은 어떠한 분야에서 사용되고 있는가?
최근 ITS(Intelligent Transportation Systems)의 개발과 함께 차량용 내비게이션의 사용이 급증하면서 경로탐색의 중요성이 더욱 가속화되고 있다. 경로탐색 알고리즘은 교통시스템, 통신 네트워크, 운송시스템, 이동 로봇의 경로 설정 등 다양한 분야에 사용되고 있다[1]
개미 집단 최적화 알고리즘은 어떠한 문제에서 최적의 해를 구하기 위해 사용되고 있는가?
개미들은 각 경로에 있는 페로몬 양을 기반으로 서로 간의 정보교환을 통해 최적의 경로를 찾아가고 이러한 개미들의 행동양식을 그대로 적용한 휴리스틱 탐색 방법으로 조합 최적화 문제인 순회 판매원 문제(Traveling Salesman Problem), 순서 문제(Sequential Ordering Problem), 차량 경로 문제(Vehicle Routing Problem), 이차 배정 문제(Quadratic Assignment Problem), 일정 계획 문제(Job-shop Scheduling Problem), 그래프 착색 문제(Graph Coloring Problem), Telecommunications Networks 등에서 최적의 해를 구하기 위해 사용되고 있다[10].
참고문헌 (10)
옥승호, 안진호, 강성호, 문병인, "선호도 기반 최단경로 탐색을 위한 휴리스틱 융합 알고리즘," 전자공학회 논문지, 제47권, TC 제8호, 2010.
Lyytinen, K. and Yoo, Y., "Research Commentary: the Next Wave of Nomadic Computing," Information Systems Research, Vol. 13, No. 4, pp. 377-388. 2002.
Oh. S.H., "KRIHS FOCUS_ITS: Intelligent Transpor tation Systems," Korea Research Institute for Human Settlements, Vol. 268, 2004.
위키피아, "http://www.wikipedia.org"
조태환, 김지원, 김병조, 윤완오, 최상방, "동적 라우팅 알고리즘의 신뢰성 향상을 위한 최단 경로 설정 알고리즘," 정보과학회논문지 제38권 제6호. 2011.
Bin Xiao, Jiannong Cao, Zili Shao, and Edwin H.-m.sha, "An Efficient Algorithm for Dynamic Shortest Path Tree Update in Network Routing," Journal of Communication and Networks, Vol. 9, No. 4, pp. 499-510, Dec. 2007.
A. Colorni, M. Dorigo, and V. Maniezzo, "An investiation of some properties of an ant algorithm," In Proceediings of the Parallel Parallel Problem Solving from Nature Conference(PPSn 92), Elsevier Publishing, pp.509-520, 1992.
A. Colorni, M. Dorigo, and V. Maniezzo, "Distributed optimization by ant colonies," In Proceedings of ECAL91-European Conference of Artificial Life, Paris, France, F.Varela and P.Bourgine(Eds.), Elsevier Publishing, pp134-144, 1991.
M. Dorigo, V. Maniezzo, and A. Colorni, "The Ant System: Optimization by a colony of cooperation agents," IEEE Transactions on Systems, Man, and Cybernetics-Part B, Vol. 26, No. 1, pp.1-13, 1996.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.