公交车公共交通算法
我正在开发一个可以查找公交路线的离线 C# 应用程序。 我可以提取时间表/巴士/路线数据。我正在寻找适用于基本数据的最简单的解决方案。
可以使用什么算法来查找从巴士站“A”到巴士站“B”的路线？是否有适用于 C#/Java 的开源解决方案？ 数据库的 google GTFS 格式是否适合简单的解决方案？ http://code.google.com/transit/spec/transit_feed_specation.html
感谢您的任何帮助。我被这个问题困住了。我不知道从哪里开始 - 如何存储数据以及如何查找路线。 我知道 Dijkstra/A* 但我只在不依赖时间的图表上使用它们......
I am working on an offline C# application that can find bus routes.
I can extract the timetable/bus/route data. I am searching for the most simple solution that will work with basic data.
What algorithm can be used to find a route from bus stop "A" to bus stop "B"? Is there a open-source solution ready for C#/Java?
Is the google GTFS format for database good for a simple solution? http://code.google.com/transit/spec/transit_feed_specification.html
Thanks for any help. I am stuck with this. I don't know where to start - how to store the data and how to find routes.
I know about Dijkstra/A* but I have used them only on graphs that were not time dependent...
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（7）
只是想分享我对这个问题的最终方法。这是大学项目的一部分，因此它可能不完全适合现实世界的使用。它必须相当快才能在 Windows Mobile 设备上运行。
我最终使用了 4 个表（SQLite）。一张表保存公交车列表，第二张表保存车站列表。另一个表保存了组合 - 哪些公共汽车在特定车站停靠，从该车站到哪里以及需要多长时间（分钟）。所有组合都必须存储。最后一张表是一个简单的时间表。对于每个车站，它列出了停在那里的每辆公共汽车和时间（我将时间存储为整数值 - 14:34 是 1434，以便更快地进行比较）。
我使用了双向广度优先搜索算法。检索起始站和目的地站的邻近站（可直接访问）。如果这两个“图”在某个站上重叠，则存在从站 A 到站 X 的路径。例如，从 A 站您可以到达 B、C、D、E 站（乘坐特定巴士）。从目的地站 X 可以直接到达 N、C、Z。这两个图在站C上重叠。因此路径A->C。 C-> X 存在。如果在第一次迭代中没有找到路径，则算法继续并再次展开图 (BFS)。
第一步不考虑时间——这使得它足够快。您只会获得可能路径的列表以及您必须使用的巴士列表来选择这些路径。
在最后一步中评估时间，您浏览可能的路径列表并检查公共汽车是否在特定时间内行驶（增加每个站点的时间）。
在一个拥有 250 个车站和 100 多辆公共汽车/铁路的小城市中，这些方法最多可换乘 3 次（您必须在旅途中换乘公共汽车）。计算只需几秒钟。但我必须将整个数据库加载到内存（字典）中以加快查询速度，这花费了太长时间。
但我认为这不适用于大型网络。但适用于单个中小城市的公共交通。
Just wanted to share my final approach on this problem. This was part of a university project, so it might not be fully suitable for real world use. It had to be reasonably fast to run on a Windows Mobile device.
I ended up using 4 tables (SQLite). One table keeps the list of buses, the second one keeps a list of stations. Another table keeps the combinations - what bus does stop at a specific station and where does it go from this station and how long (minutes) does it take. All combinations have to be stored. And the last table is a simple time-table. For every station it lists every bus that stops there and the time (I stored the time as integer value - 14:34 is 1434, to make it faster for comparing).
I used a bi-directional breadth first search algorithm. The neighbor stations (directly accessible) are retrieved for the start station and destination station. There is a path from station A to station X if these two "graphs" overlap on a station. For example, from station A you can get to stations B,C,D,E (by using specific buses). And from the destination station X you can get directly to N,C,Z. These two graphs overlap on station C. So a path A -> C -> X exists. If no paths are found in this first iteration, then the algorithm continues and spreads out the graphs (BFS) again.
Time is not taken into account in the first step - this makes it fast enough. You only get a list of possible paths with a list of buses that you have to use to take these paths.
The times are evaluated in the last step, you go through the list of possible paths and check if the bus travels within the specific time (increasing the time every stop).
On a small city, with 250 stations and 100+ buses/railways, these approach works up to 3 changes (where you have to change the buses on the journey). It takes only seconds to calculate. But I had to load the whole database into memory (Dictionary) to speed up the queries, which were taking too long.
I don't think this would work for a large network though. But it works for a public transport of a single small-medium size city.
从概念上讲，您可以采用相同的基本算法来评估 A 和 B 之间的距离，但您应该评估时间而不是距离。如果你给它适当的输入，Dijkstra 可以做到这两点。
您习惯于将地图视为距离的度量。然而，同一张地图也可以用来衡量时间；您所需要的只是添加有关平均速度的数据，并且在特定道路上行驶特定距离所需的时间就会自行计算出来。您甚至可以根据时间来可视化地图；需要更长时间的路线将会更长。 Dijkstra 并不关心它正在评估哪个，真的；它只关心找到数字最小的连续路线，而该数字是否代表长度或时间并不重要。
为了纳入速度，简单的算法只是使用白天的速度限制，并假设你从 A 到 B 时永远不必停下来；更先进的算法可以包含有关一天中的时间和交通模式的信息（这将影响您当时在该道路上行驶的平均速度），以及道路是高速公路还是地面街道（从而对停车时间做出有根据的猜测）在十字路口）。您使用的内容取决于可用的内容，但基本的 4 层或 5 层时间维度应该足以满足除绝对时间最关键的应用程序之外的所有应用程序。对于地图中每条道路的每个方向，您需要早高峰、白天、晚高峰和夜间的平均速度，可能还需要午餐时间的数据。一旦掌握了这一点，就可以对 Dijkstra 算法进行相对基本的更改，以传递一天中的某个时间并让它根据时间评估路线。
Conceptually, you take the same basic algorithm for evaluating distance between A and B, but instead of distance, you should be evaluating time. Dijkstra can do both, if you give it the proper inputs.
You're used to seeing a map as a measure of distance. However, the same map can be a measure of time as well; all you need is to add data about average speed, and the time it takes to cover a particular distance of a particular road will shake itself out. You can even visualize the map in terms of time; routes that take longer will be longer. Dijkstra doesn't care which it's evaluating, really; it just cares about finding the continuous route with the lowest number, and whether that number represents length or time is immaterial.
To incorporate speed, naive algorithms simply use the daytime speed limit and assume you never have to stop while going from A to B; more advanced algorithms can incorporate information about time of day and traffic patterns (which will impact the average speed you travel on that road at that time), and whether a road is a freeway or surface street (and thus make educated guesses about time spent stopped at an intersection). What you use depends on what you have available, but a basic 4- or 5-layer time of day dimension should be adequate for all but the absolute most time-critical applications. For each direction of each road in your map, you need the average speed during morning rush, daytime, evening rush and night, possibly with lunchtime numbers as well. Once you have that, it's a relatively basic change to a Dijkstra algorithm to pass in a time of day and have it evaluate routes based on time.
如果您对时间信息感兴趣，那么为什么不使用时间信息而不是它们之间的物理距离来标记图形边缘上的距离值。这样您将搜索最快的路线，而不是最短的路线。然后您可以使用 Dijkstra/A* 来计算结果。
我有点不清楚你所说的时间依赖是什么意思。如果您的意思是您需要回答“上午 10 点之前从 x 到 y”形式的查询，那么您可以计算哪些公交车路线在上午 10 点之前到达，这似乎是对数据的简单过滤器。然后将 Dijkstra/A* 应用于数据。
If you are interested in time information, then why not label the distance values on the graph edges using the time information instead of their physical distance from each other. That way you will search for the quickest route, instead of the shortest route. You can then use Dijkstra/A* in order to compute the your result.
I'm a little unclear on what you mean by time dependent. If you mean that that you need to answer queries of the form 'goes from x to y before 10am' then you can calculate what bus routes arrive before 10am, seems like a simple filter on the data. Then apply Dijkstra/A* to the data.
尝试将此作为您的数据模型。
巴士 1 前往车站 A、B 和 C。巴士 2 前往车站 B、D 和 E。
我将基于巴士和车站存储一个唯一的节点，到节点的距离基于时间。我们将有节点 A1、B1、C1、B2、D2 和 E2。在传输的特殊情况下，应用等待下一班车作为节点之间的距离。例如，如果公交车 1 比公交车 2 早 30 分钟到达 B 站，则从 B1 到 B2 的行程时间为 30 分钟。
您应该能够应用 Dijkstra 算法。
Try this as your data model.
Bus 1 goes to stops A, B and C. Bus 2 goes to stops B, D and E.
I would store a unique node based on both bus and stop, with distances to nodes being based on time. We would have node A1, B1, C1, B2, D2 and E2. In the special case of transfers apply the wait for the next bus as the distance between nodes. For example, if Bus 1 arrives at stop B 30 minutes before Bus 2, travel time from B1 to B2 is 30 minutes.
You should than be able to apply Dijkstra's Algorithm.
您正在解决的问题并不是一项简单的任务。因此，它有一个名字：混合整数非线性规划问题（MINLP）。用一位作者的话说（1998 年 Deb）：
在黛布的论文中，他提出了一种遗传算法。
你的另一个选择是使用模拟。只要扔掉一些东西，你就可以立即尝试——选择从你的起点开始的数千条随机路线，然后找出 想象一下
这样的算法：您正在尝试从某个时间开始找到从 A 站到 B 站的最快路线。你告诉他们每次有机会上车或下车时都抛硬币，下车（如果已经下车，则继续上车）。有一张索引卡，记下他们在走的过程中所做的选择，你去 B 点，等待第一个人出现并拿走他的卡。
The problem you are working on is not a trivial task. So much so, that is has a name: the mixed integer nonlinear programming problem (MINLP). In the words of one author (Deb 1998):
In Deb's paper he proposes a genetic algorithm.
Your other option would be to use simulation. Just to throw something out there you can try right away-- choose thousands of random routes that start at your origin, and fish out the ones that work reasonably well at getting to the destination.
Picture the algorithm like this: You are trying to find the quickest route from stop A to stop B, starting at a certain time. You hire 1,000 people and arm them with a quarter to flip. You tell them to flip the coin every time they have a chance to get on or off a bus. Heads, get off (or get on, if already off). Tails, stay on (or keep waiting, if off). They each have an index card to write down the choices they make as they go. You go to point B and wait for the first guy to show up and take his card.
有大量关于公共交通路线算法的出版物 (30 多篇)，这些出版物是由开源 (Java) OpenTripPlanner 项目，此处：
https://docs.opentripplanner。 org/en/latest/Bibliography/
OpenTripPlanner 是多模式路由引擎，还包括自行车和步行 - 来自上面的链接：
上面的路由参考书目包括以下类别的算法和相关工作的参考：
如果您发现列表中没有的新内容，请随时将其添加到 wiki！
至于其他开源公共交通路线库 - 还有 Bliksem Labs 的 RRRR 项目：
https:// github.com/bliksemlabs/rrrr
从上面的链接：
OpenTripPlanner 和 RRRR 都使用 GTFS 数据。
There is an extensive list of publications (30+) on public transport routing algorithms that has been compiled over time by contributors to the open-source (Java) OpenTripPlanner project here:
https://docs.opentripplanner.org/en/latest/Bibliography/
OpenTripPlanner is multi-modal routing engine that also includes bike and walk - from the above link:
The routing bibliography above includes references for the following categories of algorithms and related work:
If you find something new that's not on the list, please feel free to add it to the wiki!
As far as other open-source public transport routing libraries - there is also the RRRR project by Bliksem Labs:
https://github.com/bliksemlabs/rrrr
From the above link:
Both OpenTripPlanner and RRRR use GTFS data.
阅读本文：
多模式路线规划。
硕士论文，卡尔斯鲁厄大学（TH），Fakultät für Informatik，2009 年。
在线可在 http://i11www.ira.uka.de/ extra/publications/p-mmrp-09.pdf
有关铁路路线的部分也适用于公交车路线。
其要点是：将空间和时间扩展为单个图的简单方法不适用于大型网络。有更智能的解决方案。
read this:
Multi-Modal Route Planning.
Master's thesis, Universität Karlsruhe (TH), Fakultät für Informatik, 2009.
online available at http://i11www.ira.uka.de/extra/publications/p-mmrp-09.pdf
the section on railway routing also applies for bus routing.
The gist of it: the naive approach of expanding space and time into a single graph does not work for large networks. There are smarter solutions.