원문정보
A schedule-based Public Transit Routing Algorithm for Finding K-shortest Paths Considering Transfer Penalties
초록
영어
Schedule-based public transit routing algorithm computes a single route that calculated minimum travel time using the departure and arrival times for each stop according to vehicle operation plan. However, additional factors such as transfer resistance and alternative route choice are not reflected in the path finding process. Therefore, this paper proposes a improved RAPTOR that reflected transfer resistance and multi-path searching. Transfer resistance is applied at the time of transfer and different values can be set according to type of transit mode. In this study, we analyzed the algorithm's before and after results compared with actual route of passengers. It is confirmed that the proposed algorithm reflects the various route selection criteria of passengers.
한국어
운행시간표 기반 대중교통 경로 탐색 알고리즘은 운행계획에 따른 정류장별 출·도착 시각 을 이용하여 최소 이동 시간이 소요되는 단일 경로를 산출한다. 다만, 경로 계산 과정에서 환승 저항, 대안 경로 선택 등의 추가 요소들을 반영하는데 한계가 있다. 본 연구는 환승 저 항 및 다중 경로 탐색이 반영된 개선된 RAPTOR 알고리즘을 제안한다. 환승 저항은 환승 시 점에 적용되며, 교통수단 유형을 구분하여 적용하였다. 본 연구에서는 수도권 대중교통 이용 승객의 실제 이동 경로를 기준으로 개선 전·후의 알고리즘 결과를 분석하였다. 이를 통해 제 시한 알고리즘이 승객의 다양한 경로 선택 기준을 반영한다는 것을 확인하였다.
목차
ABSTRACT
Ⅰ. 서론
1. 개요
Ⅱ. 관련 연구
1. 관련 연구 분석
2. 기존 연구와의 차별성
3. RAPTOR 알고리즘
Ⅲ. 개선된 RAPTOR 알고리즘
1. 유사 경로를 제외한 다중 경로 탐색
2. 환승 저항 적용 및 도보 이동 시간 조정
3. 개선된 RAPTOR 알고리즘을 이용한 경로 탐색 과정
4. 개선된 알고리즘 구현 예시
Ⅳ. 실험 및 결과 분석
1. 실험 개요
2. 실험 결과
Ⅴ. 결론
ACKNOWLEDGEMENTS
REFERENCES