Fast Routing in Very Large Public Transportation Networks Using Transfer Patterns
Fast Routing in Very Large Public Transportation Networks Using Transfer Patterns
复制标题
DOI：
10.1007/978-3-642-15775-2_25
复制
发表时间：
2010-09
期刊：
影响因子：
--
通讯作者：
Hannah Bast;Erik Carlsson;Arno Eigenwillig;R. Geisberger;Chris Harrelson;Veselin Raychev;Fabien Viger
中科院分区：
文献类型：
--
作者：
Hannah Bast;Erik Carlsson;Arno Eigenwillig;R. Geisberger;Chris Harrelson;Veselin Raychev;Fabien Viger
我们展示了如何在非常大的公共交通网络(多达5亿条弧线)上进行布线，平均查询时间为几毫秒。我们考虑了许多现实的特征，如：交通天数，站之间的步行，在地理位置而不是源和目标站之间的查询，以及多准则成本函数。我们的算法基于两个关键观察：(1)许多最短路径共享相同的换乘模式，即车辆发生变化的站点序列；(2)不改变车辆的直接连接可以快速查找。我们预先计算各自的数据；在实践中，这可以以牺牲一小部分非最优结果为代价，在时间上与网络规模成线性关系。我们已经在谷歌地图上用一个基于我们想法的系统加快了公共交通路线的速度。我们报告了三个不同类型和大小的数据集的实验结果。
We show how to route on very large public transportation networks (up to half a billion arcs) with average query times of a few milliseconds. We take into account many realistic features like: traffic days, walking between stations, queries between geographic locations instead of a source and a target station, and multi-criteria cost functions. Our algorithm is based on two key observations: (1) many shortest paths share the sametransfer pattern, i.e., the sequence of stations where a change of vehicle occurs; (2)direct connectionswithout change of vehicle can be looked up quickly. We precompute the respective data; in practice, this can be done in time linear in the network size, at the expense of a small fraction of non-optimal results. We have accelerated public transportation routing on Google Maps with a system based on our ideas. We report experimental results for three data sets of various kinds and sizes.