database - 如何存储公共(public)交通数据

Question

我目前正在尝试实现我自己的公共(public)交通路径查找器，以找到具有给定时间表的电车/公共(public)汽车等连接。所有数据都是由我生成的(通过简单地添加来自谷歌地图的停靠点坐标)。多亏了它，我可以自由选择自己存储和处理数据的方式。整个交通网络由加权图表示。那么问题来了:如何将公共(public)交通数据存储在标准SQL数据库中，以便于选择一些算法来轻松处理？以后如何方便的转换成时间展开图的形式，用简单的Dijkstra算法就可以了？

Answer 1

由于我写了一篇关于“仅使用公共(public)交通工具你能在 X 分钟内走多远”的学士论文，我可以分享一些关于你的问题的见解。

问题

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

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

---

解决方案

从您的昵称来看，我假设您能够阅读德语。您可以在我的 thesis document. 中阅读我对算法和数据库设置的分析。第 49 页显示数据库模型，第 50 页显示内存模型。另请查看第 55-57 页的引用资料(大部分是英文的)。

即使是 time-aware-dijkstra 也真的很慢。一个好的算法是 RAPTOR(带有示例的科学描述 can be found here)。 RAPTOR 利用时间表模式而不是受其阻碍。

RAPTOR 的工作原理:时间表主要由车站(位置)、乘车(单列火车的一次运行)、停靠站(乘车、时间、位置的组合)组成。猛禽的诀窍是将所有游乐设施组织成路线。一条路线只能包含具有相同停靠顺序且不会相互超越的游乐设施。通过这种方式，您可以乘坐与您的时间相匹配的路线的第一次骑行，而无需检查同一路线上的所有其他骑行(因为它们保证会稍后到达)。路线的数量(在我的数据中是 1000 倍)比乘车的数量要少得多。此外，RAPTOR 算法以“train-hopping-cycles”运行，这使它能够准确地检查单个站点一次(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。关于公共(public)交通算法的一项重要经验是，这个问题比看起来要难得多。

我的应用可以是seen here .它使用瑞士铁路公司 (SBB & ZVV) 的 HAFAS 数据，但目前数据仅来自 2014 年。计算本身很快，需要大量时间的是生成图形叠加层。

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