两周后,我将参加一项人们必须在荷兰乘坐火车旅行最多公里数的比赛。每个人都有 24 小时的旅行时间,旅行距离最长的人获胜。但是,您只能沿着每个“路段”旅行一次。例如,如果您从鹿特丹旅行到阿姆斯特丹,然后从阿姆斯特丹返回海牙,那么很大一部分将不算数,因为您已经去过那里。如果您两次经过同一路段,您的公里数将不算数。为了获得最佳行程,我想使用算法的力量:)。
为了找到最佳路线,我决定使用 Python 并使用 networkx
包来获得荷兰铁路的可视化效果。到目前为止一切顺利,但现在有趣的部分来了:算法。给定一张包含所有铁路路段和距离的图表,你如何解决这个问题?这是图表,没有距离。
在我看来,这是旅行商问题(除非您可以多次访问城市)、最大流量优化和某种反向 Dijkstra 算法的组合:p。有没有现有的算法可以解决这个问题?或者我需要自己构建一些东西吗?如果是后者,回溯是一种好方法吗?
最佳答案
我认为首先要注意的是,由于时间表的原因,最长路径等经典的基于图的算法不会真正适用于此,因此我将其定义为混合整数线性规划问题。您将定义两种类型的变量:
- 二进制变量
x_t
对于给定的火车旅行是否t
(由来源c1
、目的地c2
、开始时间t1
和结束时间t2
标识)被使用。 - 二进制变量
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
关于python - 带有距离和行驶时间的图表 : find most km's in 24 hours (with constraints),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30691395/