如何存储公共交通数据

Question

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

Answer 1

自从我写了一篇关于"只用公共交通工具可以在X分钟内获得多远"的学士论文,我可以分享一些关于你的问题的见解.

问题

首先,忘记传统算法.去追求时间的人.什么适用于常规道路网络,完全失败的时间限制图.时间意识是一个问题,但还有更多你永远不会想到的常客

1. 一些火车保证等待其他火车
2. 换乘火车时你有一些最小的停机时间(从火车a到b)
3. 停机时间取决于站(大站或小站)和平台(从平台1到2的切换速度快于1到20)
4. 列车时刻表因日期而异,您的数据表中有很多条目不适用于您选择的日期.

解决方案

从你的绰号来看,我认为你能读懂德语.您可以在我的论文文档中阅读我对算法和数据库设置的分析. 第49页显示了数据库模型,第50页显示了内存模型.另请参阅第55-57页的参考资料(它们大多是英文版).

即使是时间感知的dijkstra也很慢.一个好的算法是RAPTOR(可以在这里找到带有示例的科学描述).RAPTOR利用时间表模式而不是受其阻碍.

RAPTOR的工作原理: 时间表主要包括车站(位置),乘坐(一列火车),站点(乘坐,时间,地点).猛禽的伎俩是将所有游乐设施组织成路线.路线可能只包含具有相同停靠顺序并且不会相互超越的游乐设施.通过这种方式,您可以乘坐与您的时间相匹配的路线,并省略检查同一路线上的所有其他乘坐路线(因为它们保证稍后到达).路线的数量相当小(我的数据中的因数为1000),而不是游乐设施的数量.此外,RAPTOR算法在"列车跳跃周期"中运行,这使得它能够准确地检查一个站点(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.它针对获取有关整个网络的数据进行了优化(而不是查找单个路径).你应该坚持使用RAPTOR.关于公共交通算法的关键学习之一是问题比看起来要困难得多.

我的应用程序可以在这里看到.它使用瑞士铁路公司(SBB和ZVV)的HAFAS数据,但目前数据仅来自2014年.计算本身很快,需要花费大量时间才能生成图形叠加.

如果您有更多问题,请随时与我联系(联系信息可在ttm.ti8m.ch上找到)