이철기 김대휘 2011-02 11301 https://aurora.ajou.ac.kr/handle/2018.oak/8519 학위논문(석사)--아주대학교 ITS대학원 :ITS학과,2011. 2 ITS(Intelligent Transportation Systems)의 한 분야인 첨단여행자정보체계(ATIS : Advanced Traveler Information System)의 주요목적은 여행자가 원하는 목적지에 대한 최적의 경로정보를 제공하는 것이다. 여행자에게 최적 경로정보란 최단거리 정보뿐만 아니라 최단시간, 최소비용 등 여행자의 상황과 기호에 맞는 경로정보이며, 이를 위해서는 여행자가 인지적으로 경로를 결정할 수 있도록 선택의 폭이 다양한 다수의 경로정보를 제공하는 것이 바람직하다. 이러한 다수의 경로정보 제공을 위해서는 (K)개의 경로를 탐색하는 알고리즘이 활용되고 있으며, 이를 K경로탐색 알고리즘(K Shortest paths Algorithm)이라 하며, 현재 K경로탐색 알고리즘에 관한 연구는 교통 분야뿐만 아니라 Computer Science 분야에서도 활발히 진행되고 있는 중이다. 본 연구에서는 현재까지의 소개된 K최단경로탐색 알고리즘들 중 수행속도가 가장 빠른 Eppstein 알고리즘을 고찰하고, 프로그래밍하고, 알고리즘의 문제점을 분석한 후 Computer Science가 아닌 일반 단일수단 교통망에서 활용이 가능하도록 기존 Eppstein 알고리즘 개선한 K경로탐색 알고리즘을 제시하고자 한다. Eppstein 알고리즘을 현실교통망에 적용할 수 없는 이유는 링크루프, 회전제약 문제가 가장 크다. 본 연구에서는 이들 문제점을 해결하여, K경로 열거 시 링크반복을 제어한 링크 비루프(No Link Repeated Path)와 회전제약이 가능한 개선된 Eppstein K경로탐색 알고리즘을 제시한다. 사례연구에서는 본 연구에서 제시한 개선된 Eppstein K최단경로탐색 알고리즘은 기존의 알고리즘을 곧바로 현실 교통망에 적용할 때 문제시 되는 링크루프문제와 회전제약문제를 해결하였고, 모형네트워크를 활용하여 그 가능성을 검증하였다. 마지막으로, 결론에서는 본 연구의 성과와 실용화에 있어 향후 지속적으로 수행되어야할 한계를 향후연구과제로 제시하였다. 제I장 서론 1 제1절 연구의 배경 및 목적 1 제1항 연구의 배경 1 제2항 연구의 목적 1 제2절 연구의 방법 및 구성 3 제1항 연구의 방법 3 제2항 연구의 구성 4 제II장 선행 연구의 고찰 5 제1절 경로삭제기반 K shortest paths 알고리즘 5 제1항 Yen 알고리즘 5 제2항 Martins 알고리즘 6 제3항 Azevedo et al 알고리즘 9 제2절 Heap-Ordered Tree기반 K shortest paths 알고리즘 11 제1항 Heap 정렬의 고찰 11 제2항 Eppstein 알고리즘 15 제III장 알고리즘의 문제점 24 제1절 현실교통망과 링크 비루프 경로 24 제2절 현실교통망과 회전제약 문제 24 제3절 Eppstein 알고리즘의 문제점 25 제1항 의 무한생성 문제 25 제2항 링크루프 발생 문제 25 제IV장 알고리즘 개선방안 29 제1절 알고리즘 속도 개선방안 29 제2절 링크루프의 개선방안 33 제1항 링크루프의 발생원인 33 제2항 Link Loop의 제어방안 34 제3절 회전제약을 고려한 개선방안 37 제4절 링크 비루프 및 회전제약이 고려된 알고리즘 39 제5절 속도 추정 40 제V장 사례연구 41 제VI장 결론 및 향후과제 45 제1절 결론 45 제2절 문제점 및 향후 연구과제 46 kor The Graduate School, Ajou University 아주대학교 논문은 저작권에 의해 보호받습니다. 단일수단 교통망에서의 K경로탐색 알고리즘에 관한 연구 A Study on the K Shortest Paths Algorithm in a Single Modal Transportation Network Thesis 아주대학교 교통ITS대학원 교통ITS대학원 ITS학과 2011. 2 Master http://dcoll.ajou.ac.kr:9080/dcollection/jsp/common/DcLoOrgPer.jsp?sItemId=000000011301 단일수단 교통망 K경로탐색 알고리즘