python - 带有距离和行驶时间的图表 : find most km's in 24 hours (with constraints)

Question

两周后，我将参加一项人们必须在荷兰乘坐火车旅行最多公里数的比赛。每个人都有 24 小时的旅行时间，旅行距离最长的人获胜。但是，您只能沿着每个“路段”旅行一次。例如，如果您从鹿特丹旅行到阿姆斯特丹，然后从阿姆斯特丹返回海牙，那么很大一部分将不算数，因为您已经去过那里。如果您两次经过同一路段，您的公里数将不算数。为了获得最佳行程，我想使用算法的力量:)。

为了找到最佳路线，我决定使用 Python 并使用 networkx 包来获得荷兰铁路的可视化效果。到目前为止一切顺利，但现在有趣的部分来了:算法。给定一张包含所有铁路路段和距离的图表，你如何解决这个问题？这是图表，没有距离。

在我看来，这是旅行商问题(除非您可以多次访问城市)、最大流量优化和某种反向 Dijkstra 算法的组合:p。有没有现有的算法可以解决这个问题？或者我需要自己构建一些东西吗？如果是后者，回溯是一种好方法吗？

Answer 1

我认为首先要注意的是，由于时间表的原因，最长路径等经典的基于图的算法不会真正适用于此，因此我将其定义为混合整数线性规划问题。您将定义两种类型的变量:

1. 二进制变量 x_t对于给定的火车旅行是否t (由来源 c1 、目的地 c2 、开始时间 t1 和结束时间 t2 标识)被使用。
2. 二进制变量 y_s对于给定的段是否 s (由来源 c1 和目的地 c2 标识)在白天使用(一次或多次)。

优化问题的目标是最大化线段距离之和 d_s乘以该段是否被使用的指标 y_s所有分割市场 s .因为段指示器永远不会超过 1(即使我们多次使用它)，这解决了“重复计算段”问题。

您需要的第一类约束确保我们实际上进行了一次有效的旅行。对于任何给定的火车旅行 t来自来源c1开始时间 t1 , 行程可以被采取 ( x_t = 1 ) 只有当之前的行程数变成 c1减去 c1 中的先前旅行次数等于 1。这确保我们实际上是在 c1当我们从c1坐火车的时候到别的地方。如果所有先前火车行程的集合进入c1是i1, i2, ..., in和所有先前火车旅行的集合 c1是o1, o2, ..., om , 那么这个约束就是 x_t <= x_i1 + x_i2 + ... + x_in - x_o1 - x_o2 - ... - x_om .请注意，这会造成一个棘手的情况，因为我们不会去整个行程的出发城市。因此我们将创建一个假的起始城市 S和来自 S 的行程(距离为 0)在所有其他旅行之前一次到另一个城市。如果我们调用来自 S 的行程到对方城市s1, s2, ..., sn ，然后我们将添加约束 x_s1 + x_s2 + ... + x_sn = 1所以我们的行程只有一个出发城市。

我们需要的其他约束确保 y_s变量设置正确。特别是，我们需要确保 y_s如果没有行程 t1, t2, ..., t_n 则设置为 0使用段 s全天使用。这可以通过 y_s <= x_t1 + x_t2 + ... + x_tn 来完成.

您可以使用 Python 中的 pulp 包以一种令人惊讶的可读性和直接的方式实现它。我将使用 dists指示段及其长度和trains指示所有列车(具有开始位置、结束位置、开始时间、结束时间的元组)。通过检查，对于这个网络，我们预计只是从 D 到 E 的距离为 3:

import pulp

dist = {("A", "B"): 1.0,
        ("B", "C"): 1.0,
        ("D", "E"): 3.0}
trains = [("A", "B", 1.0, 2.0),
          ("B", "C", 2.0, 3.0),
          ("C", "B", 3.5, 4.5),
          ("B", "A", 4.5, 5.5),
          ("D", "E", 1.0, 5.5)]
sources = set(list([t[0] for t in trains]))

x = pulp.LpVariable.dicts("x", trains, lowBound=0, upBound=1, cat=pulp.LpInteger)
y = pulp.LpVariable.dicts("y", dist.keys(), lowBound=0, upBound=1, cat=pulp.LpInteger)
s = pulp.LpVariable.dicts("s", sources, lowBound=0, upBound=1, cat=pulp.LpInteger)
mod = pulp.LpProblem("Train Optimization", pulp.LpMaximize)

# Objective
mod += sum([dist[k] * y[k] for k in dist])

# Feasibility
for t in trains:
    mod += x[t] <= s[t[0]] + sum([x[k] for k in trains if k[1] == t[0] and k[3] <= t[2]]) - sum([x[k] for k in trains if k != t and k[0] == t[0] and k[2] <= t[2]])
mod += sum([s[k] for k in sources]) == 1

# Valid y variables
for k in dist:
    mod += y[k] <= sum([x[t] for t in trains if (t[0] == k[0] and t[1] == k[1]) or (t[1] == k[0] and t[0] == k[1])])

# Solve
mod.solve()
for t in trains:
    print "Trip", t, "used:", x[t].value()

正如预期的那样，我们得到:

Trip ('A', 'B', 1.0, 2.0) used: 0.0
Trip ('B', 'C', 2.0, 3.0) used: 0.0
Trip ('C', 'B', 3.5, 4.5) used: 0.0
Trip ('B', 'A', 4.5, 5.5) used: 0.0
Trip ('D', 'E', 1.0, 5.5) used: 1.0

我们可以将 A-B 和 B-C 的距离加倍:

dist = {("A", "B"): 2.0,
        ("B", "C"): 2.0,
        ("D", "E"): 3.0}

现在，正如预期的那样，我们开始采用 A-B-C 循环(我们是否采用 C-B 和 B-A 返回行程不会影响目标，因此优化引擎可以决定是否采用它们):

Trip ('A', 'B', 1.0, 2.0) used: 1.0
Trip ('B', 'C', 2.0, 3.0) used: 1.0
Trip ('C', 'B', 3.5, 4.5) used: 1.0
Trip ('B', 'A', 4.5, 5.5) used: 0.0
Trip ('D', 'E', 1.0, 5.5) used: 0.0