如何存放公共交通数据 [英] How to store public-transportation data

问题描述

我目前想实现自己的公共交通路径查找器来查找与给定的时间表乘坐电车/总线连接等。所有的数据都被我产生（通过简单地添加停止从谷歌地图坐标）。多亏了它，我可以自由地选择自己的数据存储和处理它们的方式。整个交通网络是一个加权图psented重新$ P $。 所以在这里谈到的问题是：如何存储公共交通数据标准的SQL数据库，以便它可以很容易地选择一些算法处理？如何在以后很容易地转换为时间扩展图形的方式，使简单的Dijkstra算法就足够了？

I am currently trying to implement my own public transportation path-finder to find connections by tram/bus etc. with given timetables. All the data is generated by me (by simply adding stops coordinates from google map). Thanks to it, I am free to choose my own way of storing data and processing them. The whole transportation network is represented by a weighted graph. So here comes the question: how to store public transportation data in standard SQL database so that it could be easily processed by some chosen algorithms? How to easily convert it later to the form of time-expanded graph so that simple Dijkstra algorithm would suffice?

推荐答案

自从我写了一篇学士论文有关只使用公共交通工具在X分钟多远，你能得到，我可以分享你的问题的一些见解。

Since I wrote a bachelor thesis about "how far can you get in X minutes using only public transport", I can share some insight on your problem.

首先，忘了传统算法。去时间感知的。因为适合普通公路网络，完全在时间限制图表失败。时间意识是一个问题，但还有更多的，你绝不会想到像往常一样客运

First and foremost, forget about traditional algorithms. Go for time-aware ones. What works for regular road networks, totally fails on time restricted graphs. Time awareness is one problem, but there are many more which you would never think about as usual passenger

1. 部分列车，保证等候其他列车
2. 您有一定的停机时间最短切换时的火车（从火车站A到B）
3. 的停机时间取决于站（或大或小站），并在该平台上（从平台1切换到2快于1至20）
4. 列车时刻表因所选的日期，你的数据表中有很多不适用于您选择的日期条目。

看你的昵称我想你可以阅读德语。你可以阅读我的​​算法分析，在我的论文文档我的数据库设置。 第49页显示了数据库模型和第50页的inmemory模型。另外看看55-57页引用（他们大多是英文）。

---

Solutions

Judging by your nickname I assume you are able to read german. You can read my analysis of algorithms and my database setup in my thesis document. Page 49 shows the database model and page 50 the inmemory model. Also take a look at the references on page 55-57 (they are mostly english).

甚至时间感知，Dijkstra算法实在是太慢了。一个好的算法是 RAPTOR （科学描述与例如可以在这里找到） 。 RAPTOR利用时间表模式，而不是被阻碍它的。

Even time-aware-dijkstra is really slow. A good algorithm is RAPTOR (scientific description with example can be found here). RAPTOR makes use of the timetable patterns instead of being hindered by it.

如何RAPTOR作品： 时间表主要由站（位置），游戏机（单列车的一个运行），停止（的车程，时间，地点的组合）的。猛禽的关键是要组织所有的游乐设施到路线。路由只能包含游乐设施具有站相同的顺序和不要超车对方。这种方式可以采取哪些符合你的时间和省略检查都在同一航线的其他游乐设施（因为它们都保证以后到达）航线的第一次乘坐。路由的量是相当小的（因子1000在我的数据）比乘坐的量。此外，RAPTOR算法列车跳槽周期，这使得它来检查单站恰好一次运行（Dijkstra算法不能），并遵循

How RAPTOR works: Timetables mainly consist of stations (location), rides (one run of a single train), stops (combo of ride,time,location). The trick of raptor is to organize all rides into routes. A route may only contain rides which have the same sequence of stops and do not overtake each other. This way you can take the first ride of a route which matches your time and omit checking all the other rides on the same route (because they are guaranteed to arrive later). The amount of routes is considerably smaller (factor 1000 in my data) than the amount of rides. In addition, the RAPTOR algorithm runs in "train-hopping-cycles", which enables it to check a single station exactly once (dijkstra cannot) and to follow

它是这样的：

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。 一个关于在公共交通工具算法的重要经验是，这个问题是很多比它看起来更难。

For my application I used a modified version of RAPTOR, which I named REAS. It's optimized for getting data about the complete network (instead of looking up a single route). You should simply stick to RAPTOR. One of the key learnings about algorithms in public transport is that the problem is a lot harder than it looks.

我的应用程序可以这里看到。它使用了瑞士铁路公司的HAFAS数据（SBB＆安培; ZVV）。但目前的数据仅是从2014年的计算本身是快，什么需要花费大量的时间在产生图形覆盖

My app can be seen here. It uses the HAFAS data of the swiss railway company (SBB & ZVV) but currently the data is only from 2014. The calculation itself is fast, what takes a lot of time is generating the graphical overlay.

如果您有更多的问题，请随时直接与我联系（联系方式可在ttm.ti8m.ch）

If you have more questions, feel free to contact me directly (contact info is available on ttm.ti8m.ch)

这篇关于如何存放公共交通数据的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！