城市公共交通：如何利用巴士？

Question

我正在开发一个旅行规划网站。目前，这个项目中有几个简单的部分，即该网站只能规划公交路线，公交车的时间表目前不可用。因此，我们只在数据库中存储公交路线，由于公交车的时间表不可用，所以旅客的等待时间也不相关。我们可以获得的是每辆公交车在两个站点之间覆盖的时间和距离。

我认为使用一个无向带权图来存储每辆公交车每个站点的时间和距离成本是正确的方法。然后，我可以使用Dijkstra算法根据用户选择的时间或距离计算出两个位置之间的最短路径。如果公交路线在某些站点交叉，则通过简单的C#函数找出是否需要乘坐两三辆公交车，并使用这些交叉站点让旅客换乘公交车。但是每辆公交车都将有一个单独的图。另一种方法（不确定是否正确）是使用包含城市每个公交站点的图作为节点，然后使用此技术找出两个站点之间的旅行方式。哪种方法是正确的？我应该使用A*算法代替Dijkstra算法吗？

对于设计，有几个一般性的要点：我希望应用程序具有可扩展性，以便在需要时可以添加其他交通方式。此外，如果可能的话，公交车时间表也可以稍后添加，而不会对网站造成重大变化。我已经看到这里有很多专家已经处理了更复杂的交通项目。因此，请帮助我以最可扩展、模块化和可扩展的方式实现此功能。

- NAB

Answer 1

一张图表必须是有方向的 - 在道路两侧的公交车站（即使在像英国这样很少有中央分隔带的国家）也不是同一个站点！

- winwaed

---

非常有价值的观点！我不知道我怎么会错过这个。随着被迫思考，它变得更加复杂:( - NAB

Answer 2

去年夏天我开始了一个类似的应用程序，但是没有完成。不过我对这个图表以及如何构建你的数据有一些建议。

我的计划是将每个站点作为一个节点，并在每次公交车通过的每个节点之间建立一条路径。例如，如果公交车在6小时内每隔半小时停靠一次，则两个节点之间将有12条路径。时间是“成本”的主要驱动因素，因此通常会选择最快的路径。

在开始之前，应用程序将查询下一5个小时（根据需要进行调整）内所有路径的数据库。然后使用Dijkstra算法进行计算。

其他要考虑成本的因素包括路线的实际费用、换乘（及其费用）、没有顶棚的车站（如果你经常遇到恶劣天气）等。

这个计划对我来说效果很好。我住在一个有3个公交系统的地区。

最后，你可能需要按照Google Transit Feed规范构建你的数据结构，因为许多机构都会生成这种类型的数据，你可以导入它们。

- Brad

Answer 3

我为一个测试应用程序编写了这样的算法。每个站点都有一个字典，作为起始点和目的地。该算法是递归的。递归的每一步都是这样的：给定源和目标，它会生成进入目标的路线列表，离开源的路线列表。如果有任何公共站点，我们就完成了，报告路线。如果没有，那么我为源生成相邻站点，并进行递归。下一次递归为汇生成相邻站点列表，进行递归。在递归之前，我当然记录了先前的路径，最后我会有一个列表。

我记得我不得不放置一些截止条件，因为递归有时会卡在某些“坏”区域。

我还查看了这篇论文：

www.citeulike.org/user/rchauhan/article/819528

我很感兴趣，您是否以不同的方式解决了这个问题。

- BBSysDyn

Answer 4

我认为最重要的优化是将可以更换路线的站点与不能更换路线的站点分开。然后，您只需要将可以更换路线的站点视为图表中的中间站点。这应该使图表变得非常小，以至于Dijkstra算法就足够了。

我通过简单地剪切它们并将它们的两个邻居连接起来形成一个新的边来区分仅具有两个边的节点。然后，在这个减少的图表上进行路径查找，这应该会快得多。即只考虑可能切换路线的站点。

- CodesInChaos

---

你是在建议为每辆公交车建立一个图，并使用Dijkstra算法来寻找最短路径吗？我正在考虑实现换乘功能：1）分别在具有目的地或起点站的公交车中搜索共同的停靠点。2）现在在这些公交车路线中，找到共同点与目的地/起点站之间的最短距离。3）最后将两个结果合并以获取完整旅程的详细信息，并将其与其他组合进行比较以获得最短路径。 - NAB

我想到的另一种优化方式是，一旦搜索完成，将两个点之间最短路径的详细信息存储在“快速访问”表中。随着时间的推移，该表将不断增长，并且在几次使用后，搜索结果将更快。我也可以手动在后台为每个站点（nxn组合）运行此过程。 - NAB

不，我的想法是略过只有一条路线通过的车站，因为在这些车站中没有什么有趣的事情会发生。 - CodesInChaos

Answer 5

也许你可以从paddydubs在github上找到的TransportDublin项目中获得一些帮助。

- nawroth