1

我已经为三个班车路线制作了一个带有成本（每个车站之间的距离）的有向图。任何穿梭路线的车站到车站的票价都是一样的，因此唯一要做的就是尽量减少换乘。

我希望它以这种方式工作。我想从 Station A -> C 出发。为简单起见，我们首先假设车站之间的距离为一 (1)。

路线 1：A -> D -> B -> C -> A
路线 2：A -> C -> E -> F -> A
路线 3：A -> X -> Y -> Z -> A

由于路线 1 和路线 2 中都有一条从 A -> C 的路径，因此我将选择成本最低的路线 2。我已经这样做了。

但是如果我想从 Station C -> Y 出发，没有从 C -> Y 的直达路线。所以我必须从 1 或 2 出发，然后在 A 下车，然后从 A -> Y。基本上，我只是希望尽量减少班车接送和行驶距离。

有没有流行的算法呢？

4

6 回答 6

3

您可以使用Dijkstra 算法解决此问题。

建立一个图表，以便：

穿梭路线上的每个站点都有一个节点。如果两辆班车去同一个车站，那么该车站的每条路线都有一个节点。因此，在您的示例中，有节点 A1、D1、B1、C1、A2、C2、E2、F2 -> A2 等。还为每个站点创建一个节点，但使其独立于路线，例如 A、B、 C等。

如果班车直接在两个车站之间行驶，例如，在您的示例中在 A1 和 D1 之间但不在 A1 和 B1 之间，则在这两个节点之间创建有向边。该边缘的权重应该是两个站点之间的成本（距离）。因此，例如，有边 (A1, D1) 和 (D1, C1)

如果两辆班车停在同一个车站，则在两条路线上的车站节点之间创建两条有向边，例如，创建边 (A1, A2) 和 (A2, A1)。边缘的权重应该是转移的成本。

在每个特定路径的车站节点和独立于车站的车站节点之间创建两条边，例如，创建边（A，A1），（A1，A），（A，A2），（A2，A）。给这些节点中的每一个节点一个远小于之前边的成本的成本，例如，0.01 * 最小成本。

现在，如果您想在两个站点之间旅行，请使用 Dijkstra 算法找到两个非特定路线节点之间成本最低的路径。

在您的示例中，要从 F 到 X，请找到节点 F 和 X 之间成本最低的路径。返回的路径将是 F -> F2 -> A2 -> A3 -> X3 -> X，意味着从 F 开始，乘坐2号班车，前往A，换乘3号线，然后在X站下车。

于 2011-01-16T01:33:51.570 回答
1

对某些场景、约束等进行了大量优化。

试试dijkstra，它通常是最短路径算法的基础（即很多人开始学习该主题的地方），虽然要真正理解如何有效地实现它，您可能还应该熟悉相关的数据结构（一堆不同的描述等。见维基）

于 2011-01-16T01:05:00.850 回答
0

很多这样的算法：

http://en.wikipedia.org/wiki/Shortest_path_problem#Algorithms

于 2011-01-16T01:06:53.423 回答
0

我认为这比 TSP 复杂一些。您希望最小化距离和使用的穿梭车。

如何称量每一个？如果您只想尽量减少班车接送，请使用套装

每条路线都是一组。如果一个集合有一个项目（车站或给定的字母）也属于另一个集合，您可以从一个集合转移到另一个集合（或从班车转移到另一个集合）。

于 2011-01-16T01:13:47.710 回答
0

这是交通规划中经常处理的事情。

以这种方式增强表示网络的图：

  1. 为每条路线使用单独的链接。给每个人一个成本（旅行时间是一个很好的价值）。
  2. 在路径链接和代表站点的节点之间添加链接。这些将代表登机和下车。
  3. 为登机链接增加高成本（不一定是真正的成本）。

现在两个站点之间的最小路径将是成本：

  1. 当两个站都通过一条路线连接时，一个登机费加上路径中每条链路的小费率。
  2. 两个或两个以上的登机费加上不直接由路线连接的车站的每个链接的费率。
  3. 如果没有找到站点之间的路径，则为无限。

在所有情况下，就登机和换乘以及链接数量而言，路径将是最少的。

请注意，每个链接都必须有一个成本（即使它是符号的），因为如果允许零成本的子路径，某些路径搜索算法将无限循环。

于 2011-01-16T18:54:56.517 回答
-1

这是旅行商问题的一个组成部分。实际上，没有“简单”的解决方案。但是有几种算法可以提供“足够好”的解决方案。

于 2011-01-16T01:06:42.320 回答