Route Planning in Transportation Networks
Route Planning in Transportation Networks
复制标题
DOI：
10.1007/978-3-319-49487-6_2
复制
发表时间：
2016-01-01
期刊：
影响因子：
--
通讯作者：
Werneck, Renato F.
中科院分区：
文献类型：
--
作者：
Bast, Hannah;Delling, Daniel;Werneck, Renato F.
我们调查了交通网络中路线规划算法的最新进展。对于道路网络，我们表明即使在大陆范围内，人们也可以在几毫秒或更短的时间内计算出行驶方向。各种技术在预处理工作、空间要求和查询时间之间提供了不同的权衡。一些算法可以在不到一微秒的时间内回答查询，而另一些算法可以有效地处理实时流量。公共交通系统的行程规划虽然在概念上相似，但由于其固有的时间依赖性和多标准性质，是一个非常困难的问题。尽管精确算法对于都市交通系统上的交互式查询来说足够快，但处理大陆规模的实例需要简化或大量预处理。多式联运路线规划问题寻求将基于时间表的交通（公共汽车、火车）与不受限制的模式（步行、驾驶）相结合的旅程，这一问题甚至更加困难，即使对于大都市的输入也依赖于近似解决方案。
We survey recent advances in algorithms for route planning in transportation networks. For road networks, we show that one can compute driving directions in milliseconds or less even at continental scale. A variety of techniques provide different trade-offs between preprocessing effort, space requirements, and query time. Some algorithms can answer queries in a fraction of a microsecond, while others can deal efficiently with real-time traffic. Journey planning on public transportation systems, although conceptually similar, is a significantly harder problem due to its inherent time-dependent and multicriteria nature. Although exact algorithms are fast enough for interactive queries on metropolitan transit systems, dealing with continent-sized instances requires simplifications or heavy preprocessing. The multimodal route planning problem, which seeks journeys combining schedule-based transportation (buses, trains) with unrestricted modes (walking, driving), is even harder, relying on approximate solutions even for metropolitan inputs.