如何使用 Pulp 将 TSP 扩展到 MTSP

Question

我们已经研究了 TSP，现在我们的任务是将其扩展到多个销售人员。 下面的代码使用 PULP 和我添加的逻辑，不幸的是不起作用。它无法正确识别正确的游览。

例如。使用下面的成本矩阵：

cost_matrix = [[ 0, 1, 3, 4],
     [ 1, 0, 2, 3 ], 
     [ 3, 2, 0, 4 ], 
     [ 4, 3, 4, 0]]

并且 n = len(cost_matrix)

对于销售人员 (k = 3)，结果应为：

SP_1的路径为：0 => 1 => 0

SP_2的路径为：0 => 2 => 3 => 0

有人可以帮我解决这个问题吗？

    # create encoding variables
    bin_vars = [ # add a binary variable x_{ij} if i not = j else simply add None
        [ LpVariable(f'x_{i}_{j}', cat='Binary') if i != j else None for j in range(n)] 
        for i in range(n) ]
    time_stamps = [LpVariable(f't_{j}', lowBound=0, upBound=n, cat='Continuous') for j in range(1, n)]
    # create add the objective function
    objective_function = lpSum( [ lpSum([xij*cj if xij != None else 0 for (xij, cj) in zip(brow, crow) ])
                           for (brow, crow) in zip(bin_vars, cost_matrix)] )
    
    prob += objective_function 

    # add constraints
    for i in range(n):
        # Exactly one leaving variable
        prob += lpSum([xj for xj in bin_vars[i] if xj != None]) == 1
        # Exactly one entering
        prob += lpSum([bin_vars[j][i] for j in range(n) if j != i]) == 1
    
    # add timestamp constraints
    for i in range(1,n):
        for j in range(1, n):
            if i == j: 
                continue
            xij = bin_vars[i][j]
            ti = time_stamps[i-1]
            tj = time_stamps[j -1]
            prob += tj >= ti + xij - (1-xij)*(n+1)

    
    # Binary variables to ensure each node is visited by a salesperson
    visit_vars = [LpVariable(f'u_{i}', cat='Binary') for i in range(1, n)]
    
    # Salespersons constraints
    prob += lpSum([bin_vars[0][j] for j in range(1, n)]) == k
    prob += lpSum([bin_vars[i][0] for i in range(1, n)]) == k

    for i in range(1, n):
        prob += lpSum([bin_vars[i][j] for j in range(n) if j != i]) == visit_vars[i - 1]
        prob += lpSum([bin_vars[j][i] for j in range(n) if j != i]) == visit_vars[i - 1]
    

    # Done: solve the problem
    status = prob.solve(PULP_CBC_CMD(msg=False))

Answer 1

求解完线性程序后，您需要提取并打印每个销售人员实际走过的路径。

# Done: solve the problem
status = prob.solve(PULP_CBC_CMD(msg=False))

if status == 1:  # 1 means the problem is solved optimally
    print("Optimal solution found")

    # Extract and print paths
    for sp in range(1, k+1):
        path = [0]  # Starting from node 0
        current_node = 0

        while True:
            next_node = [j for j in range(n) if value(bin_vars[current_node][j]) == 1]
            if not next_node:
                break
            next_node = next_node[0]
            path.append(next_node)
            current_node = next_node

        print(f'The path of SP_{sp} is: {" => ".join(map(str, path))}')
else:
    print("Optimal solution not found")