Adapting Dijkstra for Buffers and Unlimited Transfers
Author
- Haebom
Category
Empty
저자
Denys Katkalo, Andrii Rohovyi, Toby Walsh
💡 개요
본 연구는 사전 처리 없이 무제한 환승이 가능한 대중교통 경로 탐색 문제를 다룹니다. 기존의 RAPTOR 알고리즘이 우위에 있다고 여겨졌으나, 본 연구는 Time-Dependent Dijkstra (TD-Dijkstra)가 MR보다 우수함을 입증합니다. 그러나 TD-Dijkstra는 버퍼 시간을 고려할 때 발생하는 문제점을 가지고 있으며, 이를 해결하기 위해 Trip Sequence 기반의 Transfer Aware Dijkstra (TAD)를 제안하여 버퍼 시간의 영향을 정확히 반영하면서도 MR보다 2배 이상의 속도 향상을 달성했습니다.
🔑 시사점 및 한계
•
무제한 환승 대중교통 경로 탐색에서 Time-Dependent Dijkstra (TD-Dijkstra)가 기존 알고리즘보다 성능이 우수함을 제시합니다.
•
정류장의 버퍼 시간을 고려하지 않는 기존 TD-Dijkstra의 한계를 지적하고, 이를 해결하기 위한 Transfer Aware Dijkstra (TAD) 알고리즘을 개발했습니다.
•
TAD 알고리즘은 버퍼 시간을 정확하게 반영하면서도 MR 알고리즘 대비 2배 이상의 속도 향상을 보여주어 실제 적용 가능성을 높였습니다.
•
TAD 알고리즘의 다양한 네트워크 규모 및 복잡도에 대한 추가적인 성능 검증이 필요할 수 있습니다.
