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

问题描述

我目前正试图实现我自己的公共交通路径寻找器，以通过电车/公共汽车等与给定的时间表找到连接。所有的数据是由我生成的（通过简单地从google地图添加停止坐标）。感谢它，我可以自由选择我自己的方式存储数据和处理它们。整个交通网络由加权图表示。
所以这里有问题：如何存储公共交通数据在标准的SQL数据库，使它可以很容易地处理一些选择的算法？

解决方案

因为我写了一个简单的Dijkstra算法，一个学士论文你能在X分钟只使用公共交通，我可以分享一些洞察你的问题。

问题

首先，忘记传统的算法。去时间感知的。什么适用于常规道路网络，完全失败的时间限制图。时间意识是一个问题，但还有更多，你永远不会像往常一样考虑乘客

1. 某些火车有保证等待其他（从火车a到火车b）


2. 停车时间取决于车站（大站或小站）和平台（从平台1切换到2的速度比1到20快）


3. 列车时刻表取决于日期，您的数据表有很多条目，不适用于您的





---





解决方案

根据你的昵称判断，我假设你能读德语。您可以在我的论文文档中阅读我对算法和数据库设置的分析。 / a>
Page 49显示数据库模型和第50页内存模型。另请参阅第55-57页的参考资料（它们大部分是英文）。





即使 time-aware-dijkstra 。一个好的算法是 RAPTOR （可以在这里找到示例的科学描述） ）。 RAPTOR利用时间表模式，而不是被它阻碍。





RAPTOR的工作原理：
时间表主要包括车站（位置），游乐设施（乘坐，时间，位置的组合）。猛禽的伎俩是组织所有乘坐路线。路线只能包含具有相同停靠点序列且不会相互超越的游览。这样，你可以采取第一次的路线匹配你的时间，省略检查所有其他乘坐在同一条路线（因为他们保证以后到达）。路线的数量比骑乘量小得多（我的数据中的因子1000）。此外，RAPTOR算法运行在火车跳跃周期，它使它能够检查单个站正好一次（dijkstra不能），并按照





它去像这样：

  reachableStations =（startStation，timeX）
 for i = i< maxHops; i ++ {
 if（reachableStations包含targetStation）
完成！ 
 usefulRoutes =收集从reachableStations离开的所有路线
 reachableStations =跟随所有可用的路线到
，并收集下一个周期的电台。 
为每个find保存站点组合。 
} 
  





---





。





对于我的应用程序，我使用RAPTOR的修改版本，我命名为REAS。它被优化用于获取关于整个网络的数据（而不是查找单个路由）。你应该坚持RAPTOR。





我的应用程序可以是在此处查看。它使用瑞士铁路公司（SBB& ZVV）的HAFAS数据，但目前的数据仅来自2014年。计算本身很快，生成图形叠加需要很多时间。





如果您还有其他问题，请随时直接与我联系（联系方式：ttm.ti8m.ch）




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?

解决方案

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.

The 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. some trains are guaranteed to wait for other trains
2. you have some minimum downtime when switching trains (from train a to b)
3. the downtime depends on the station (big or small stations) and the platform (switching from platform 1 to 2 is faster than 1 to 20)
4. train schedules differ depending on the date, your data table has a lot of entries which do not apply to your selected date.

---

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).

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.

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

It goes like this:

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.
}   

---

.

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.

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.

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

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