단일수단 교통망에서의 K경로탐색 알고리즘에 관한 연구
A Study on the K Shortest Paths Algorithm in a Single Modal Transportation Network
- 주제(키워드) 단일수단 교통망 , 알고리즘
- 발행기관 亞州大學敎 大學院
- 지도교수 이철기
- 발행년도 2011
- 학위수여년월 2011. 2
- 학위명 석사
- 학과 및 전공 ITS대학원 ITS학과
- 실제URI http://www.dcollection.net/handler/ajou/000000011301
- 본문언어 한국어
- 저작권 아주대학교 논문은 저작권에 의해 보호받습니다.
초록/요약
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최단경로탐색 알고리즘은 기존의 알고리즘을 곧바로 현실 교통망에 적용할 때 문제시 되는 링크루프문제와 회전제약문제를 해결하였고, 모형네트워크를 활용하여 그 가능성을 검증하였다. 마지막으로, 결론에서는 본 연구의 성과와 실용화에 있어 향후 지속적으로 수행되어야할 한계를 향후연구과제로 제시하였다.
more목차
제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
