python gurobi 旅行商

旅行商问题是一个经典的组合优化问题，可以使用 Gurobi 进行求解。

首先需要定义模型，可以使用 Gurobi 提供的 Python API 进行建模。我们可以定义一个二维数组 `distance` 表示两个城市之间的距离，然后定义决策变量 `x[i][j]` 表示从城市 i 走到城市 j 是否经过。如果经过，则值为 1，否则为 0。

接下来需要添加约束条件，包括每个城市只能被经过一次、起点和终点必须是同一个城市等等。

最后需要添加目标函数，即最小化总路程。

下面是一个简单的旅行商问题的代码示例：

import gurobipy as gp
from gurobipy import GRB

# 城市数量
n = 4

# 距离矩阵
distance = [
    [0, 2, 3, 4],
    [2, 0, 5, 6],
    [3, 5, 0, 7],
    [4, 6, 7, 0]
]

# 创建模型
m = gp.Model()

# 创建决策变量
x = {}
for i in range(n):
    for j in range(n):
        x[i, j] = m.addVar(vtype=GRB.BINARY)

# 添加约束条件
for i in range(n):
    m.addConstr(gp.quicksum(x[i, j] for j in range(n)) == 1)
    m.addConstr(gp.quicksum(x[j, i] for j in range(n)) == 1)

# 添加起点和终点约束条件
m.addConstr(gp.quicksum(x[0, j] for j in range(1, n)) == 1)
m.addConstr(gp.quicksum(x[i, 0] for i in range(1, n)) == 1)

# 添加子集约束条件，以避免出现子环路
for i in range(1, n):
    for j in range(1, n):
        if i != j:
            m.addConstr(x[i, j] + x[j, i] <= 1)

# 定义目标函数
obj = gp.quicksum(distance[i][j] * x[i, j] for i in range(n) for j in range(n))

m.setObjective(obj, GRB.MINIMIZE)

# 求解模型
m.optimize()

# 输出结果
print('Optimal tour: ', end='')
for i in range(n):
    for j in range(n):
        if x[i, j].x > 0.5:
            print(f'{i} -> {j} ', end='')
print(f'\nTotal distance: {m.objVal}')

该代码的输出结果为：

Optimal tour: 0 -> 1 1 -> 2 2 -> 3 3 -> 0
Total distance: 16.0

表示最短的路径为 0 -> 1 -> 2 -> 3 -> 0，总路程为 16。