按年被提到
20152024 · 4 次2026
社会、经济与科学研究›交通、出行与自动驾驶·arXiv:1504.05140 · cs.DS

Route Planning in Transportation Networks

交通网络中的路径规划
Hannah Bast, Daniel Delling, Andrew Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, Renato F. Werneck · 2015

综述路网与公共交通上快速路径规划算法

开始阅读 ↗PDFalphaXiv 讨论
被推荐 · 8 人首次 2016-04-03 · 最近 2024-10-20发表于 Lecture notes in computer science
8不同的人
8活跃月份
8讨论串
610被引(OpenAlex)

论文综述交通网络路径规划算法的近期进展。对道路网络,可在毫秒甚至更短时间内算出大陆尺度的驾车路线,不同技术在预处理开销、空间需求和查询时间之间提供不同权衡,有的算法查询只需不到一微秒,有的能高效处理实时交通。公共交通的行程规划概念上类似但因时间依赖和多准则而难得多,多式联运则更难,即使在城市规模也要依赖近似解。

HN 为什么提它

HN 上的人把它当作路径规划与最短路加速技术(如 contraction hierarchies)的最佳综述,称它能为各个方向的论文提供索引,适合入门。

综述难度 3 / 5约 240 分钟经得起时间
读之前最好知道
1图论与最短路径算法(Dijkstra)
2算法复杂度分析
3预处理与查询的权衡思想
4公共交通时刻表与多准则优化的概念

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
推荐danpat · 2016-10

“"Route Planning in Transportation Networks" gives an excellent overview of current search speedup techniques.”

称它是对当前搜索加速技术的出色综述
Show HN: Dijkstra’s algorithm in the web browser with OpenStreetMap原评论 ↗
推荐karussell · 2017-02

“If you want to have the best summary of routing algorithms currently available then read 'Route Planning in Transportation Networks' (2014) Route Planning in Transportation Networks”

推荐它为目前最好的路由算法综述
JPS+: Over 100x Faster than A* (2015) [video]原评论 ↗
推荐lorenzhs · 2018-03

“a great recent-ish survey paper at Route Planning in Transportation Networks which will give you pointers to papers in all directions”

推荐这篇较新的优秀综述,能指向各个方向的论文
B-Heap vs. Binary Heap (2010)原评论 ↗
推荐amitp · 2024-01

“But you might find these two papers useful:”

推荐它作为路网路径规划的有用参考
A* tricks for videogame path finding原评论 ↗
推荐payasr · 2024-01

“A bit more updated reference is Route Planning in Transportation Networks, and [LINK] is great!”

推荐它作为更新一些的参考文献
A* tricks for videogame path finding原评论 ↗
推荐joe_the_user · 2024-03

“See just for a start: Route Planning in Transportation Networks”

推荐作为入门概览,涵盖 hub 网络和 contraction hierarchies
Hexagons and Hilbert curves – The headaches of distributed spatial indices原评论 ↗
看全部 7 条 →
引用payasr · 2019-10

“And route planning in graphs (with static edge weights) has been studied to death.”

提到静态边权图上的路径规划已被研究透了
New pathfinding algorithm原评论 ↗
被提交为 story · 2 次