python - 带有距离和行驶时间的图表:在24小时内找到大多数公里(有限制)

两个星期后，我将参加一场比赛，在那里人们必须乘火车去荷兰最公里。每个人都有24小时的旅行时间，最长的人旅行获胜。但是，您只能沿着每个“区段”旅行一次。例如，如果你从鹿特丹到阿姆斯特丹，再从阿姆斯特丹回到海牙，很大一部分都不算，因为你已经去过那里了。如果你同时走两段路，你的公里数就不算了。为了得到最佳的行程，我想使用算法的力量：）。为了找到最佳路线，我决定使用Python并使用networkx包来对荷兰铁路进行可视化。到目前为止，很好，但是现在有趣的部分是：算法。给定一个包含所有铁路区段和距离的图表，如何解决问题？这是图表，没有距离。在我看来，这是一个旅行商问题的组合（除了你可以多次访问城市），最大流优化，以及一些倒Dijkstra算法：P：有一个现有的算法可以解决这个问题吗？或者我需要自己做些什么？如果是后者，像回溯这样的方法是一个好方法吗？ 最佳答案 我认为首先要注意的是，经典的基于图的算法，如最长路径在这里不会真正适用，因为时间表，所以我会把这个框架作为一个混合整数线性规划问题。您可以定义两种类型的变量：二元变量x_t用于给定列车行程t（由源，目的地c1，开始时间c2，结束时间t1）。在一天中，是否使用一个给定的段（由源标识和目的地CC标识）（一次或多次）。优化问题的目的是最大化段距离之和t2倍，以指示该段是否在所有段y_s中使用“cc>”。因为段指示符永远不会超过1（即使我们多次使用它），它也会处理“双计数段”问题。您需要的第一类约束确保我们实际执行有效的旅行。对于任何给定的列车行程从源s开始在时间c1，只有在进入c2的出行次数才等于1时才能进行出行（d_s）。这确保了当我们乘火车从y_s到其他地方时，我们实际上是在s处。如果进入t的所有先前列车行程的集合是c1，而退出t1的所有先前列车行程的集合是x_t = 1，则该约束是c1。请注意，这会造成一个棘手的情况，因为我们不会进入整个行程的起始城市。因此，我们将在所有其他行程之前创建一个伪起始城市“CC”和“TRIP”（距离0）。如果我们将从c1到另一个城市的旅行称为c1，那么我们将添加约束c1，这样我们的行程就只有一个起始城市。我们需要的其他约束确保c1变量设置正确。特别是，如果使用segmenti1, i2, ..., in的tripsc1没有在一天中使用，我们需要确保o1, o2, ..., om设置为0。这可以通过x_t <= x_i1 + x_i2 + ... + x_in - x_o1 - x_o2 - ... - x_om来实现。您可以用Python中的纸浆包以令人惊讶的可读性和直截了当的方式实现这一点。我将使用S表示段及其长度和S来指示所有列车（元组具有起始位置、结束位置、开始时间、结束时间）。通过检查，对于这个网络，我们希望距离3从D到E：import pulpdist = {("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)# Objectivemod += sum([dist[k] * y[k] for k in dist])# Feasibilityfor 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 variablesfor 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])])# Solvemod.solve()for t in trains: print "Trip", t, "used:", x[t].value()正如所料，我们得到：Trip ('A', 'B', 1.0, 2.0) used: 0.0Trip ('B', 'C', 2.0, 3.0) used: 0.0Trip ('C', 'B', 3.5, 4.5) used: 0.0Trip ('B', 'A', 4.5, 5.5) used: 0.0Trip ('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.0Trip ('B', 'C', 2.0, 3.0) used: 1.0Trip ('C', 'B', 3.5, 4.5) used: 1.0Trip ('B', 'A', 4.5, 5.5) used: 0.0Trip ('D', 'E', 1.0, 5.5) used: 0.0