java 公交公共交通算法

Bus public transport algorithm

提问by Daniel Novak

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.

我正在开发一个可以找到公交路线的离线 C# 应用程序。我可以提取时间表/公共汽车/路线数据。我正在寻找适用于基本数据的最简单的解决方案。

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

可以使用什么算法来查找从“A”巴士站到“B”巴士站的路线？是否有适用于 C#/Java 的开源解决方案？数据库的 google GTFS 格式是否适合简单的解决方案？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...

谢谢你的帮助。我坚持这个。我不知道从哪里开始 - 如何存储数据以及如何查找路线。我知道 Dijkstra/A* 但我只在不依赖于时间的图表上使用它们......

回答by Pete

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

您正在处理的问题不是一项微不足道的任务。这么多，那就是有一个名字：混合整数非线性规划问题（MINLP）。用一位作者的话（Deb 1998）：

"When formulated mathematically, the time scheduling problem becomes a mixed integer nonlinear programming problem (MINLP) having a large number of resource- and service-related constraints. Although attempts have been made in the past to find an optimal schedule of a simplified model using classical optimization techniques (Bookbinder & DCsilets, 1992; Kikuchi & Parameswaran, 1993), it is observed that this is an extremely difficult task even for a small transit network. The difficulty arises mainly because of the large number of variables and constraints, discrete nature of variables, and nonlinearities involved in the objective function and the constraints."

“当以数学方式表述时，时间调度问题变成了混合整数非线性规划问题 (MINLP)，具有大量与资源和服务相关的约束。尽管过去曾尝试使用以下方法找到简化模型的最佳调度经典优化技术 (Bookbinder & DCsilets, 1992; Kikuchi & Parameswaran, 1993)，观察到即使对于小型公交网络，这也是一项极其困难的任务。困难的出现主要是由于大量的变量和约束、离散性目标函数和约束中涉及的变量和非线性。”

In Deb's paper he proposes a genetic algorithm.

在 Deb 的论文中，他提出了一种遗传算法。

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.

把算法想象成这样：你试图找到从某个时间点开始，从 A 站到 B 站的最快路线。你雇佣了 1,000 人，并用四分之一的时间武装他们。你告诉他们每次有机会上车或下车时就抛硬币。头，下车（或上车，如果已经下车）。尾巴，继续（或继续等待，如果关闭）。他们每个人都有一张索引卡，用来写下他们做的选择。你去 B 点，等待第一个出现并拿走他的卡。

回答by Sean Barbeau

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 projecthere:

开源 (Java) OpenTripPlanner 项目的贡献者随着时间的推移编译了大量关于公共交通路由算法的出版物（30+）：

https://github.com/opentripplanner/OpenTripPlanner/wiki/RoutingBibliography

https://github.com/opentripplanner/OpenTripPlanner/wiki/RoutingBibliography

OpenTripPlanner is multi-modal routing engine that also includes bike and walk - from the above link:

OpenTripPlanner 是多模式路由引擎，还包括自行车和步行 - 来自上面的链接：

This is a list of articles, dissertations, and books that have inspired and informed both the existing OTP routing engine and some ongoing experiments. Currently, OpenTripPlanner uses a single time-dependent (as opposed to time-expanded) graph that contains both street and transit networks. Walk-only and bicycle-only trips are generally planned using the A* algorithm with a Euclidean heuristic or contraction hierarchies. Walk+Transit or Bike+Transit trips are planned using a variant of the MOA* algorithm with epsilon-dominance for path pruning and the Tung-Chew heuristic (a graph providing a lower bound on aggregate weight) for queue ordering.

这是一系列文章、论文和书籍，它们对现有的 OTP 路由引擎和一些正在进行的实验都有启发和启发。目前，OpenTripPlanner 使用包含街道和公交网络的单个时间相关（而不是时间扩展）图。通常使用带有欧几里德启发式或收缩层次结构的 A* 算法来规划仅步行和仅自行车的旅行。Walk+Transit 或 Bike+Transit 行程使用 MOA* 算法的变体进行规划，该算法具有用于路径修剪的 epsilon-dominance 和用于队列排序的 Tung-Chew 启发式算法（提供聚合权重下限的图）。

The routing bibliography above includes references for the following categories of algorithms and related work:

上述路由参考书目包括以下类别的算法和相关工作的参考：

• Path Search Speedup Techniques
• Multi-objective Pareto Shortest Paths
• Resource-constrained Routing
• Contraction and Transfer Patterns
• Timetable-based routing
• ALT and Metric Embeddings
• Calibration and Implementation Details
• Post-Dijkstra Public Transit Routing

• 路径搜索加速技术
• 多目标帕累托最短路径
• 资源受限路由
• 收缩和转移模式
• 基于时间表的路由
• ALT 和公制嵌入
• 校准和实施细节
• 后 Dijkstra 公共交通路线

If you find something new that's not on the list, please feel free to add it to the wiki!

如果您发现列表中没有的新内容，请随时将其添加到 wiki！

As far as other open-source public transport routing libraries - there is also the RRRR project by Bliksem Labs:

至于其他开源公共交通路由库 - 还有 Bliksem Labs 的 RRRR 项目：

https://github.com/bliksemlabs/rrrr

https://github.com/bliksemlabs/rrrr

From the above link:

从上面的链接：

RRRR (usually pronounced R4) is a C-language implementation of the RAPTOR public transit routing algorithm. It is the core routing component of the Bliksem journey planner and passenger information system. The goal of this project is to generate sets of Pareto-optimal itineraries over large geographic areas (e.g. BeNeLux or all of Europe), improving on the resource consumption and complexity of existing more flexible alternatives. The system should eventually support real-time vehicle/trip updates reflected in trip plans and be capable of running directly on a mobile device with no Internet connection.

RRRR（通常读作 R4）是 RAPTOR 公共交通路由算法的 C 语言实现。它是 Bliksem 旅程规划器和乘客信息系统的核心路由组件。该项目的目标是在较大的地理区域（例如比荷卢经济联盟或整个欧洲）生成多组帕累托最优路线，改善现有更灵活替代方案的资源消耗和复杂性。该系统最终应支持反映在旅行计划中的实时车辆/旅行更新，并且能够在没有互联网连接的情况下直接在移动设备上运行。

Both OpenTripPlanner and RRRR use GTFS data.

OpenTripPlanner 和 RRRR 都使用 GTFS 数据。

回答by Jakob Erdmann

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

多模式路线规划。硕士论文，卡尔斯鲁厄大学 (TH)，Fakult?t für Informatik，2009 年。可在线访问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.

其要点是：将空间和时间扩展为单个图形的幼稚方法不适用于大型网络。有更聪明的解决方案。

回答by Daniel Novak

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.

只是想分享我对这个问题的最终方法。这是大学项目的一部分，因此它可能不完全适合现实世界中的使用。它必须相当快才能在 Windows Mobile 设备上运行。

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

我最终使用了 4 个表（SQLite）。一张表保存公共汽车列表，第二张保存车站列表。另一个表格保留了组合 - 什么巴士在特定车站停靠，它从这个车站去哪里以及需要多长时间（分钟）。必须存储所有组合。最后一张表是一个简单的时间表。对于每个车站，它列出了停在那里的每辆公共汽车和时间（我将时间存储为整数值 - 14:34 是 1434，以便更快地进行比较）。

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.

我使用了双向广度优先搜索算法。为起始站和目标站检索相邻站（可直接访问）。如果这两个“图形”在一个站上重叠，则存在从 A 站到 X 站的路径。例如，从 A 站您可以到达 B、C、D、E 站（使用特定巴士）。从目的站 X 您可以直接到达 N、C、Z。这两个图在站 C 上重叠。因此存在路径 A -> C -> X。如果在第一次迭代中没有找到路径，则算法继续并再次展开图 (BFS)。

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.

在一个拥有 250 个车站和 100 多条公共汽车/铁路的小城市，这些方法最多可更改 3 次（您必须在旅途中更换公共汽车）。计算只需几秒钟。但是我不得不将整个数据库加载到内存（字典）中以加快查询速度，这需要很长时间。

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.

不过，我认为这不适用于大型网络。但它适用于单个中小型城市的公共交通。

回答by KeithS

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.

从概念上讲，您采用相同的基本算法来评估 A 和 B 之间的距离，但您应该评估时间而不是距离。如果你给它适当的输入，Dijkstra 可以做到这两点。

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.

您习惯于将地图视为距离的度量。然而，同一张地图也可以用来衡量时间；您所需要的只是添加有关平均速度的数据，并且通过特定道路的特定距离所需的时间将自行消除。您甚至可以在时间方面可视化地图；需要更长时间的路线会更长。Dijkstra 并不关心它正在评估哪个，真的；它只关心找到数字最小的连续路线，并且该数字代表长度还是时间并不重要。

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.

为了结合速度，天真的算法简单地使用白天的速度限制，并假设您从 A 到 B 时永远不必停下来；更高级的算法可以结合有关一天中的时间和交通模式（这将影响您当时在该道路上行驶的平均速度）以及道路是高速公路还是地面街道的信息（从而对停下来的时间做出有根据的猜测在十字路口）。你使用什么取决于你有什么可用，但基本的 4 层或 5 层时间维度应该足以满足所有时间要求，但绝对最关键的应用程序。对于地图中每条道路的每个方向，您需要早高峰、白天、晚高峰和夜间的平均速度，可能还需要午餐时间的数字。一旦你有了它，它'

回答by Richard Warburton

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.

如果您对时间信息感兴趣，那么为什么不使用时间信息而不是它们彼此之间的物理距离来标记图边上的距离值。这样，您将搜索最快的路线，而不是最短的路线。然后您可以使用 Dijkstra/A* 来计算您的结果。

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.

我有点不清楚你所说的时间依赖是什么意思。如果您的意思是您需要回答“上午 10 点之前从 x 到 y”形式的查询，那么您可以计算上午 10 点之前到达的巴士路线，这似乎是对数据的一个简单过滤器。然后将 Dijkstra/A* 应用于数据。

回答by Philip Tinney

Try this as your data model.

试试这个作为你的数据模型。

Bus 1 goes to stops A, B and C. Bus 2 goes to stops B, D and E.

1 路公交车前往 A、B 和 C 站。2 路公交车前往 B、D 和 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.

我将存储基于总线和站点的唯一节点，节点的距离基于时间。我们将有节点 A1、B1、C1、B2、D2 和 E2。在传输的特殊情况下，将等待下一个总线作为节点之间的距离。例如，如果 1 路公交车比 2 路公交车早 30 分钟到达 B 站，则从 B1 到 B2 的行程时间为 30 分钟。

You should than be able to apply Dijkstra's Algorithm.

您应该能够应用 Dijkstra 算法。