比较三种路径搜索算法在交通导航中的表现，找出最优选择。
Traffic-Aware Navigation in Road Networks
- 结合预处理与实时搜索，平衡速度与交通感知能力。
- Dijkstra和A*在实时导航中效果最好，只需少量预处理。
- 适合需要快速响应且重视交通信息的智能导航系统。
本项目对比了三种图搜索方法在金斯顿市道路网络中实现交通感知导航的效果。包括单次预处理多查询算法（Floyd-Warshall-Ingerman）、连续单查询实时搜索（Dijkstra和A*），以及结合两者优势的混合算法（Yen's）——先计算前K条最短路径，再实时迭代。Dijkstra和A*在实时性与交通感知优化方面表现最佳，预处理开销最小。Floyd-Warshall-Ingerman虽运行最快，但仅提供基于距离的路径，无交通感知。Yen's需大量预处理，但在运行速度与路径最优性间取得良好平衡。不同方法各有优劣，需根据具体部署场景权衡选择。
原文摘要 · Abstract (English)
This project compares three graph search approaches for the task of traffic-aware navigation in Kingston's road network. These approaches include a single-run multi-query preprocessing algorithm (Floyd-Warshall-Ingerman), continuous single-query real-time search (Dijkstra's and A*), and an algorithm combining both approaches to balance between their trade-offs by first finding the top K shortest paths then iterating over them in real time (Yen's). Dijkstra's and A* resulted in the most traffic-aware optimal solutions with minimal preprocessing required. Floyd-Warshall-Ingerman was the fastest in real time but provided distance based paths with no traffic awareness. Yen's algorithm required significant preprocessing but balanced between the other two approaches in terms of runtime speed and optimality. Each approach presents advantages and disadvantages that need to be weighed depending on the circumstances of specific deployment contexts to select the best custom solution. *This project was completed as part of ELEC 844 (Search and Planning Algorithms for Robotics) in the Fall 2025 term.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。