如何存储public-交通数据

Question

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

Answer 1

自从我写了一篇关于 "how far can you get in X minutes using only public transport" 的学士论文后，我可以就您的问题分享一些见解。

问题

首先，忘掉传统算法。寻找有时间意识的人。适用于常规道路网络的方法在时间限制图上完全失败。时间意识是一个问题，但还有很多你平时想不到的 passenger

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

解决方案

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

即使 time-aware-dijkstra 也真的很慢。一个好的算法是 RAPTOR（带有示例的科学描述 can be found here）。 RAPTOR 利用 timetable 模式而不是被它阻碍。

RAPTOR 的工作原理： Timetables主要由站（位置）、乘车（单列运行一次）、停站（乘车、时间、位置的组合）组成。猛禽的诀窍是将所有游乐设施组织成路线。一条路线只能包含具有相同停靠点顺序且不会相互超越的游乐设施。通过这种方式，您可以乘坐与您的时间相匹配的路线的第一次骑行，而无需检查同一路线上的所有其他骑行（因为它们保证会稍后到达）。路线的数量（在我的数据中是 1000 倍）比乘车的数量要少得多。此外，"train-hopping-cycles" 中的 RAPTOR 算法运行s 使其能够仅检查一次单个站点（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）

如何存储public-交通数据

How to store public-transportation data

database

algorithm

graph

path-finding

问题

解决方案