开始使用免费开始使用

旅行商问题（TSP）

旅行商问题（TSP）是一个常见问题，在物流中有广泛应用。给定一名推销员的一组城市，以及任意两城之间的距离，他需要找到一条最短路线：从起点出发，途经所有城市各一次，最后返回起点。这是一个计算上较难的问题，但 Miller-Tucker-Zemlin（MTZ）方法表明可以用整数线性规划来求解。在本练习中，您将为一个包含 15 个城市的小型数据集（见下图）定义 TSP 的目标函数和部分约束。您的目标是练习将 LpVariable.dicts 与列表推导式结合使用。

Photo of Cities

我们已为您创建了 3 个 Python 变量 n、cities 和 dist $^{1}$。n 表示城市数量，cities 是编号后的城市列表，dist 是一个 pandas DataFrame，存放每对城市之间的距离。您可以在控制台中查看它们。此外，模型也已为您初始化。

\(^{1}\) 数据集来源：Gerhard Reinelt，TSPLIB - A Traveling Salesman Problem Library，ORSA Journal on Computing。

本练习是课程的一部分

Python 供应链分析

查看课程

交互式实操练习

通过完成这段示例代码来试试这个练习。

# Define Decision Variables
x = LpVariable.dicts('X', [(____, ____) for c1 in ____ for c2 in ____], 
                     cat='____')
u = LpVariable.dicts('U', [____ for c1 in ____], 
                     lowBound=0, upBound=(n-1), cat=____)
编辑并运行代码