寻路（路由，行程规划，...）在图形上与时间限制的算法 [英] Pathfinding (routing, trip planning, ...) algorithms on graphs with time restrictions

问题描述

我有公交/火车/ ...停止，每个日期等到达/离开时间的数据库。我正在寻找一个方式做搜索最快（最短/最低/至少过渡）两个位置之间的往返。我想在未来的任意位置，使用OpenStreetMap的数据做站之间，距离车站步行到开始/结束，但暂时我只是想在数据库中查找两站之间的路径。

现在的问题是，我似乎无法找到有关此主题的很多信息，例如这个维基百科页面有大量的文字，在它绝对没有任何有用的信息。

什么我发现是 GTFS 格式，在谷歌公交使用。虽然我所在的城市没有提供一个公共数据馈送（甚至不是一个私人的），我已经把所有的GTFS包含的重要信息，使转型将是微不足道的。

有一些GTFS为基础的软件，比如像 OpenTripPlanner 的也可以用的 OpenStreetMap的

然而的，路由code是不是有据可查的（至少从我发现），我并不需要整个事情。

所有我要找的是我可以使用的算法，他们的表现，也许一些伪code。

一些很好的概述

因此​​，的问题是，给予停止，路线和到达/离开/旅行时间列表，我怎么能很容易地找到从STOP最快的路径，停止B？

解决方案

1. 型号您的问题，一个图表。每站将一个顶点，和 每个公交/火车将是一个边缘。
2. 创建一个函数 W：Edges-＆GT; R ，表示时间/资金/ ...为每条边。
3. 现在，你有一个典型的最小路径问题，可以通过解决 Dijkstra算法，该发现从给定的源的所有顶点最小的路径。

（*）对于至少过渡'，你的体重实际上是各1个边，所以你甚至可以通过运行的 BFS 甚至双向 BFS代替Dijkstra算法，正如我在解释<一个href="http://stackoverflow.com/questions/7220232/compute-social-distance-between-two-users/7220294#7220294">post [它是社会距离的解释，却是相同的算法实际上]。

---

修改
作为编辑的图形[时序]您的评论中提到[价格和转换次数，我所提到的上面仍然适用，因为这些图都是静态]的非静态性质，可以使用距离矢量路由算法的，这实际上意味着工作动态图，并且是<一个分布式变异HREF =htt​​p://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm>贝尔曼Ford算法​​。
的算法思路：

• 在周期性的，每个顶点将其距离向量其 邻居[矢量显示多少成本，从发送顶点旅行，彼此的顶点。
• 在其邻国尝试更新它们的路由表[通过优势是最好的移动到每个目标]
• 对于你的情况，每个节点知道什么是让邻国以最快的方式，[行程时间+等待时间]，它[顶点/站】增加这个数字在距离向量的每个主菜，以知道如何，这将多少时间，才能到目的地。当校车，出行时间应重新计算所有节点[从此源]，和新的载体应该发送给它的邻居

I have a database of bus/train/... stops and the arrival/departure times on each date and so on. I'm looking for a way to do a search for the fastest(shortest/cheapest/least transitions) trip between two locations. I would like to have arbitrary locations in the future, using OpenStreetMap data to do walking between stops and from stops to start/end, however for the time being I just want to find path between two stops in the database.

The problem is I can't seem to find much info about this subject, for example this Wikipedia page has a lot of text with absolutely no useful information in it.

What I've found is the GTFS format, used in Google Transit. While my city doesn't provide a public data feed (not even a private one), I already have all the important information that the GTFS contains and making a transformation would be trivial.

There is some GTFS-based software, like like OpenTripPlanner that can also do pedestrian/car/bike routing using OpenStreetMap.

However, the routing code isn't well documented (at least from I've found) and I don't need the whole thing.

All I'm looking for is some good overview of the algorithms I could use, their performance, maybe some pseudocode.

So, the question is, given a list of stops, routes and arrival/departure/travel times, how can I easily find the fastest path from stop A to stop B?

解决方案

1. Model your problem as a graph. Each station will be a Vertex, and each bus/train will be an Edge.
2. create a function w:Edges->R,that indicates the time/money/... for each edge.
3. now, you have a typical minimum path problem, which can be solved by Dijkstra algorithm, which finds minimum path to all vertices from a given source.

(*) For 'least transitions', your weight is actually 1 for each edge, so you can even optimize this by running a BFS or even bi-directional BFS instead of dijkstra, as I explained in this post [It is explained for social distance, but it is the same algorithm actually].

---

EDIT
as an edit to the non-static nature of the graph [for timing] you mentioned on comments [for price and number of transitions, what I have mentioned above still applies, since these graphs are static], you can use a distance vector routing algorithm, which actually meant to work for dynamic graphs, and is a distributed variation of Bellman Ford algorithm.
The algorithm idea:

• periodically, every vertex sends its "distances vector" to its neighbors [the vector indicates how much it 'costs' to travel from the sending vertex, to each other vertex.
• Its neighbors try to update their routing tables [through which edge is it best to move to the each target]
• for your case, each node knows what is the fastest way to get to its neighbors, [travel time + wait time] and it [the vertex/station] adds this number to each entree in the distance vector, in order to know how to and how much time it will take, to get to the destination. When a bus leaves, the travel time should be re-calculated to all nodes [from this source], and the new vector should be sent to its neighbors

这篇关于寻路（路由，行程规划，...）在图形上与时间限制的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！