包含距离和旅行时间的图表：在 24 小时内找到最多的公里数（有限制）

Question

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

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

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

Answer 1

我认为您应该为一个有向图建模，其中包含所有出发-到达行进边以及所有等待边（在车站的到达和离开之间）24 小时。不幸的是，您的里程奖励不是优势的属性，而是也取决于过去的优势。我怀疑是否有一个非常好的算法可以有效地找到有前途的路径和捷径。您只能删除具有相同（或部分）旅行段和较晚到达的路径。

编辑：

根据规则，您可能还必须为 starting/stopping 路段（从边界算起的部分）或快速运输模拟德国和比利时的车站。此外，您可能必须模拟前一天清晨到达的班次和第二天晚些时候到达的班次（计算当天的部分航段）。

Answer 2

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

二进制变量 x_t 是否给定火车旅行 t（由源头 c1、目的地 c2、开始时间 t1 和结束时间标识）时间 t2) 被使用。
二进制变量 y_s 表示给定段 s（由源 c1 和目标 c2 标识）是否在执行期间被使用（一次或多次）天.

优化问题的 objective 是最大化段距离之和 d_s 乘以该段是否在所有段中使用的指标 y_s s .因为段指示符永远不会超过 1（即使我们多次使用它），这解决了 "double counting segments" 问题。

您需要的第一类约束确保我们实际进行有效旅行。对于从时间 c1 开始的任何给定火车旅行 t，在时间 t1 开始，只有在之前的旅行次数 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 变量。特别是，如果使用段 s 的行程 t1, t2, ..., t_n 中的 none 全天使用，我们需要确保 y_s 设置为 0。这可以通过 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 return 行程不会影响 objective，因此优化引擎可以决定是否采用任何一种方式带走它们）：

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

包含距离和旅行时间的图表：在 24 小时内找到最多的公里数（有限制）

Graph with distance and travelling times: find most km's in 24 hours (with constraints)

python

algorithm

mathematical-optimization