TSP求解器异常：仅返回重复起点路径，无法生成有效巡游

我尝试用距离矩阵求解TSP，但代码始终返回array([0, 0, 0, 0])，无法生成遍历所有节点的最小代价巡游，期望输出为array([0, 1, 3, 2])。以下是我的实现代码：

import numpy as np
from ortools.linear_solver import pywraplp

class TSPSolver:
    def __init__(self, distance_matrix, method):
        self.distance_matrix = np.array(distance_matrix)
        self.method = method

    def solve_tsp(self):
        return self.method.solve()

class TSPMethod:
    def __init__(self, distance_matrix):
        self.distance_matrix = np.array(distance_matrix)

    def solve(self):
        raise NotImplementedError("This method should be overridden in subclasses")

class FlowBasedMethod(TSPMethod):
    def solve(self):
        self.distance_matrix = self.distance_matrix.astype(int) # integers required by SCIP
        n = self.distance_matrix.shape[0]

        # Create the linear solver
        solver = pywraplp.Solver.CreateSolver('SCIP')

        # Create variables
        x = {}
        for i in range(n):
            for j in range(n):
                x[i, j] = solver.IntVar(0, 1, f'x_{i}_{j}')

        u = [solver.IntVar(0, n, f'u_{i}') for i in range(n)]

        # Constraints
        for i in range(n):
            solver.Add(solver.Sum(x[i, j] for j in range(n)) == 1)  # each city must be departed from exactly once
            solver.Add(solver.Sum(x[j, i] for j in range(n)) == 1)  # each city must be visited exactly once

        for i in range(1, n):
            for j in range(1, n):
                if i != j:
                    solver.Add(u[i] - u[j] + n * x[i, j] <= n - 1)  # subtour elimination

        # Objective function: minimize the total distance
        solver.Minimize(solver.Sum(self.distance_matrix[i, j] * x[i, j] for i in range(n) for j in range(n)))

        # Solve the problem
        status = solver.Solve()
        # If a solution was found, extract the tour
        if status == pywraplp.Solver.OPTIMAL:
            # Start from the first city
            tour = [0]
            current_city = 0
            while len(tour) < n:
                # Go to the next city
                for j in range(n):
                    if x[current_city, j].solution_value() > 0.5:
                        tour.append(j)
                        current_city = j
                        break
            return np.array(tour)

        else:
            print('No solution found!')
            return None

distance_matrix = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]

method = FlowBasedMethod(distance_matrix)
solver = TSPSolver(distance_matrix, method)
solver.solve_tsp()

问题根源 #

代码存在两个核心问题：

• 未禁止自环边：当前约束允许x[i,i] = 1（即从城市i直接回到自身），求解器会选择自环来满足出度/入度约束，导致无限停留在起点。
• 子回路消除约束变量范围错误：u变量初始范围设为[0, n]，不符合MTZ（Miller-Tucker-Zemlin）约束的要求，无法有效消除子回路。

修复后的代码 #

import numpy as np
from ortools.linear_solver import pywraplp

class TSPSolver:
    def __init__(self, distance_matrix, method):
        self.distance_matrix = np.array(distance_matrix)
        self.method = method

    def solve_tsp(self):
        return self.method.solve()

class TSPMethod:
    def __init__(self, distance_matrix):
        self.distance_matrix = np.array(distance_matrix)

    def solve(self):
        raise NotImplementedError("This method should be overridden in subclasses")

class FlowBasedMethod(TSPMethod):
    def solve(self):
        self.distance_matrix = self.distance_matrix.astype(int) # SCIP要求整数类型
        n = self.distance_matrix.shape[0]

        # 创建线性求解器
        solver = pywraplp.Solver.CreateSolver('SCIP')

        # 创建变量：禁止自环边
        x = {}
        for i in range(n):
            for j in range(n):
                if i != j:
                    x[i, j] = solver.IntVar(0, 1, f'x_{i}_{j}')
                else:
                    # 自环边固定为0
                    x[i, j] = solver.IntVar(0, 0, f'x_{i}_{j}')

        # 修正u变量范围，符合MTZ约束要求
        u = [solver.IntVar(1, n, f'u_{i}') for i in range(n)]
        # 固定起点u值，减少变量自由度
        solver.Add(u[0] == 1)

        # 约束：每个城市恰好出发/到达一次
        for i in range(n):
            solver.Add(solver.Sum(x[i, j] for j in range(n)) == 1)
            solver.Add(solver.Sum(x[j, i] for j in range(n)) == 1)

        # 子回路消除约束
        for i in range(1, n):
            for j in range(1, n):
                if i != j:
                    solver.Add(u[i] - u[j] + n * x[i, j] <= n - 1)

        # 目标函数：最小化总距离
        solver.Minimize(solver.Sum(self.distance_matrix[i, j] * x[i, j] for i in range(n) for j in range(n)))

        # 求解并提取路径
        status = solver.Solve()
        if status == pywraplp.Solver.OPTIMAL:
            tour = [0]
            current_city = 0
            while len(tour) < n:
                for j in range(n):
                    if x[current_city, j].solution_value() > 0.5:
                        tour.append(j)
                        current_city = j
                        break
            return np.array(tour)
        else:
            print('未找到可行解！')
            return None

distance_matrix = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]

method = FlowBasedMethod(distance_matrix)
solver = TSPSolver(distance_matrix, method)
print(solver.solve_tsp())  # 输出：array([0, 1, 3, 2])

关键修改说明 #

1. 禁止自环边：创建x[i,j]变量时，将自环边的上下限都设为0，确保求解器不会选择从城市到自身的路径。
2. 修正u变量范围：将u变量范围改为[1, n]，并固定起点u[0] = 1，符合MTZ约束的标准形式，有效避免子回路生成。

内容的提问来源于stack exchange，提问作者Lino