如何存储公共交通数据

Question

如何存储公共交通数据

databasealgorithmgraphpath-finding

3

我目前正在尝试实现自己的公共交通路径查找器，以便通过电车/公交等与给定的时间表相结合来寻找连接。所有数据由我生成（通过从Google地图中添加停靠点坐标）。由于这一点，我可以自由选择自己的数据存储方式并处理它们。整个交通网络由加权图表示。

那么问题来了：如何将公共交通数据存储在标准SQL数据库中，以便某些选择的算法能够轻松处理？如何轻松将其转换为时间扩展图的形式，以便简单的Dijkstra算法就足够了？

- TheMP

相关：具有时间限制的图形上的路径查找（路由，行程规划等）算法，链接的帖子讨论如何在这样的数据中找到最短路径，这似乎与您想要的相关（虽然不是重复！）。 - amit

顺带提一下，A* 可能是更好的路线搜索算法，因为这是大多数旅行规划系统的基础... - Rowland Shaw

Dijkstra算法在现实世界的网络中不够快。 - dmitri

是的，我知道 Dijkstra 算法很慢。但是，我需要一个简单的算法作为更复杂算法的基准。 - TheMP

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- dube · Accepted Answer

自从我写了一篇关于“仅使用公共交通工具，你可以在多少时间内到达目的地”的学士论文后，我可以分享一些有关您问题的见解。

问题：

首先，忘记传统算法。选择时态感知算法。对于常规道路网络有效的算法，在时间限制图上完全失败。时间感知是一个问题，但还有许多其他问题，作为普通乘客，您永远不会考虑到这些问题。

1. 一些火车保证等待其他火车。 2. 切换火车（从A到B）时，您需要一些最小停机时间。 3. 停机时间取决于车站（大型或小型车站）和站台（从1号站台切换到2号站台比从1号站台切换到20号站台更快）。 4. 火车时刻表因日期而异，您的数据表中有许多条目与所选日期不适用。

解决方案

根据你的昵称，我猜你能够阅读德语。你可以在我的论文文件中阅读我的算法分析和数据库设置。第49页展示了数据库模型，第50页展示了内存模型。同时请查看第55-57页的参考文献（它们大多是英文）。

即使time-aware-dijkstra非常慢，但好的算法是RAPTOR（科学描述和示例可以在这里找到）。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上找到）。