如何存储公共交通数据

Question

我目前正在尝试实施我自己的公共交通路径查找器，通过电车/公共汽车等寻找与给定时间表的连接。所有数据都是由我生成的(只需在google地图上添加停止坐标)。多亏了它，我可以自由选择自己的存储和处理数据的方式。整个运输网络由一个加权图表示。因此，问题来了:如何将公共交通数据存储在标准SQL数据库中，以便某些选择的算法能够轻松地处理这些数据？如何容易地把它转换成时间扩展图的形式，这样简单的Dijkstra算法就足够了？

Answer 1

因为我写了一篇关于“只用公共交通工具你能在X分钟内走多远”的单身汉论文，我可以分享一些关于你的问题的见解。

问题

首先，忘掉传统的算法。去找有时间意识的人。对普通道路网络有效的方法，在时间限制图上完全失败。时间意识是一个问题，但还有更多你永远不会想到的乘客。

1. 有些火车保证要等其他火车。
2. 在换乘火车时(从a到b)，你有一些最短的停机时间。
3. 停机时间取决于站台(大站或小站)和站台(从1号站台切换到2号站台比1至20号月台快)。
4. 火车时刻表因日期不同而不同，数据表中有许多不适用于选定日期的条目。

解决方案

从你的绰号判断，我猜你会读德语。您可以在我的论文文件。页面49中阅读我对算法的分析和数据库设置，第49页显示数据库模型，第50页显示内存中的模型。也请看一下第55至57页的参考资料(主要是英文)。

即使是time-aware-dijkstra也是非常慢的。一个很好的算法是RAPTOR (以可以在这里找到为例进行科学描述)。猛禽利用时间表模式，而不是被它所阻碍。

猛禽如何工作：时间表主要由车站(地点)、乘车(一列火车的一次运行)、车站(骑行、时间、地点组合)组成。猛禽的诀窍是把所有的骑行都安排在航线上。一条路线可能只包含有相同的停车顺序的乘车，而且不会超过对方的。通过这种方式，您可以选择与您的时间相匹配的路线的第一次乘车，而不检查同一路线上的所有其他乘车情况(因为它们肯定会在稍后到达)。路线的数量比乘车的数量要小得多(我的数据中是1000因子)。此外，猛禽算法在“列车跳跃周期”中运行，使它能够准确地检查单个车站(dijkstra不能)并跟随。

事情是这样的：

reachableStations = (startStation,timeX)
for i=0; i < maxHops; i++ {
     if( reachableStations contains targetStation)
         finished!
     usableRoutes       = collect all routes leaving from reachableStations 
     reachableStations  = follow all usableRoutes to the end 
                          and collect stations for the next cycle.
                          keep station-time combos for each find.
}   

。

对于我的应用程序，我使用了一个改进型的RAPTOR，我把它命名为REAS。它是为获取完整网络的数据而优化的(而不是查找单个路由)。你应该坚持猛禽。关于公共交通算法的一个关键学习是，这个问题比它看上去要困难得多。

我的应用程序可以是在这里看到的。它使用瑞士铁路公司(SBB & ZVV)的HAFAS数据，但目前的数据仅为2014年。计算本身是快速的，需要很长时间才能生成图形叠加。

如果你有更多的问题，请直接联系我(ttm.ti8m.ch上有联系信息)