Intriguingly Simple and Fast Transit Routing
Intriguingly Simple and Fast Transit Routing
复制标题
DOI：
10.1007/978-3-642-38527-8_6
复制
发表时间：
2013-06
期刊：
影响因子：
--
通讯作者：
Julian Dibbelt;Thomas Pajor;Ben Strasser;D. Wagner
中科院分区：
文献类型：
--
作者：
Julian Dibbelt;Thomas Pajor;Ben Strasser;D. Wagner
本文研究动态公交网络中的最优行程计算问题。我们引入了一种新的算法框架，称为连接扫描算法（CSA），计算行程。它将数据组织为单个连接数组，每个查询扫描一次。尽管它的简单性，我们的算法是非常通用的。我们用它来解决最早到达和多标准配置文件查询。此外，我们将其扩展到处理最小预期到达时间（MEAT）问题，该问题包含车辆上的随机延迟，并要求一组（替代）行程，在其整体上最大限度地减少用户的预期到达时间在目的地。我们的实验密集的大都市网络的伦敦表明，CSA计算MEAT查询，我们最复杂的情况下，平均在272毫秒。
This paper studies the problem of computing optimal journeys in dynamic public transit networks. We introduce a novel algorithmic framework, called Connection Scan Algorithm (CSA), to compute journeys. It organizes data as a single array of connections, which it scans once per query. Despite its simplicity, our algorithm is very versatile. We use it to solve earliest arrival and multi-criteria profile queries. Moreover, we extend it to handle the minimum expected arrival time (MEAT) problem, which incorporates stochastic delays on the vehicles and asks for a set of (alternative) journeys that in its entirety minimizes the user’s expected arrival time at the destination. Our experiments on the dense metropolitan network of London show that CSA computes MEAT queries, our most complex scenario, in 272 ms on average.