【运筹优化】(1) TSP 旅行商问题,Python + Gurobi 代码

简介: TSP(旅行商问题)涉及寻找有向完全图中起点到所有其他点的最短回路。目标是最小化路径权重总和,保证每个节点仅访问一次。模型通过0-1决策变量表示边的存在,约束确保每个节点恰好一次作为起点和终点。为消除子圈,引入MTZ方法,添加辅助变量破坏环路。实验中,随机生成30个点,计算距离并应用MTZ模型求解,通过Gurobi库实现并展示结果。

TSP

1. 介绍

问题描述:

给定一个有向完全图 G = (V, E)

有向完全图:一个节点可以直接到达其他节点

V:图中节点集合 |V| = N

E:图中边集合

当边 eij 与边 eji 对称时,称为对称 TSP 问题

目标:

找到一条从起点(任意点)出发依次不重复地经过所有其他节点,最终返回起点的最小权和(最短)的路径

输入: 一系列坐标点的集合

输出: 一个访问序列。每个节点被且只被访问一次;每个节点被且只被离开一次。

Pasted image 20240405203628.png


2. 建模

变量

符号 释义
$i, j$ 节点 i 和节点 j
$x_{ij}$ 0-1 决策变量,判断最优解中是否有边 (i, j)
$c_{ij}$ 边 $(i,j)$ 的权重 (距离、成本)
V 所有节点的集合

模型框架

公式 编号
$$min \sum_{i\in V} \sum_{j \in V} c_{ij}x_{ij}$$ (1)
$$\sum_{i \in V} x_{ij} =1 \quad\quad \forall j \in V, i\ne j$$ (2)
$$\sum_{j\in V}x_{ij} = 1 \quad\quad \forall i \in V, i\ne j$$ (3)
$$x_{ij} \in {0, 1} \quad\quad \forall i,j \in V, i\ne j$$ (4)

公式解释

  • (1) 最小化解的总权重,在最优解中所有边的权重相加
  • (2) 访问约束。被且只被访问一次。对于任意 j 节点,最优解中流入该节点的边总数等于 1
  • (3) 离开约束。被且只被离开一次。对于任意 i 节点,最优接种流出该节点的边的总数等于 1
  • (4) 决策变量的 0-1

不足

求解时不会出现一个环路,而是出现若干个子圈,子圈的权重之和与大圈相比更小

Pasted image 20240405210513.png

改进:破子圈约束

方法:MTZ 消除环路约束

加入辅助变量。破坏所有环路的存在。对每个节点引入一个决策变量 $\mu_i$ ,$\forall i \in V, \mu_i \ge 0$。
$$\mu_i - \mu_j + N\times x_{ij} \le N-1, \quad \forall i,j\in V, i,j\ne 0,i\ne j $$
其中,$\mu_i$ 是节点 i 被访问的次序,正常情况下,先访问 i 后访问 j,$\mu_i-\mu_j=-1$,若 j 被访问过了,j 的序号比 i 小,那么 $\mu_i-\mu_j>0$

最终模型

目标

  • $$min \sum_{i\in V} \sum_{j \in V} c_{ij}x_{ij}$$

约束

  • $$\sum_{i \in V} x_{ij} =1, \quad\quad \forall j \in V, i\ne j$$
  • $$\sum_{j\in V}x_{ij} = 1, \quad\quad \forall i \in V, i\ne j$$
  • $$\mu_i - \mu_j + N\times x_{ij} \le N-1, \quad\quad \forall i,j\in V, i,j\ne 0,i\ne j$$
  • $$x_{ij} \in \{0, 1\}, \quad\quad \forall i,j \in V, i\ne j$$
  • $$\mu_i \ge 0, \quad \mu_i \in R, \quad \forall i\in V$$

实验

随机生成30个点,计算两两节点 i 和 j 之间的距离,若 i=j 则将距离设为无限大。使用MTZ方法破子圈。

Pasted image 20240406212305.png

代码展示


import gurobipy as gp
import numpy as np
import matplotlib.pyplot as plt

# ------------------------------------------ #
# 数据集
# ------------------------------------------ #

coords = []  # 保存所有的节点坐标
n = 0  # 记录产生节点的个数
while n<30:
    coord = [np.random.randint(1,10), np.random.randint(1,10)]
    if coord not in coords:
        coords.append(coord)
        n += 1
grids = gp.tuplelist(coords)  # 转换为gurobi列表类型
N = len(grids)  # 节点个数
# 创建距离矩阵
dis_matrix = np.zeros(shape=[N,N])
for i in range(N):
    for j in range(N):
        if i==j:  # 如果节点自身到自身
            dis_matrix[i][j] = 1000000  # 无限远
        else:
            dis_matrix[i][j] = np.sqrt((grids[i][0]-grids[j][0])**2 \
                                + (grids[i][1]-grids[j][1])**2)

# ------------------------------------------ #
# 模型构建
# ------------------------------------------ #
m = gp.Model()

# 变量
x = m.addMVar((N,N), lb=0, ub=1, vtype=gp.GRB.BINARY)  # 代表i和j节点之间是否可达
u = m.addVars((N), vtype=gp.GRB.CONTINUOUS)  # 给每个节点一个编号 len=N
m.update()

# 目标
# m.setObjective(gp.quicksum(dis_matrix[i][j]*x[i][j] for j in range(N) for i in range(N)), gp.GRB.MINIMIZE)
obj = 0
for i in range(N):
    for j in range(N):
        obj += x[i][j] * dis_matrix[i][j]
m.setObjective(obj, gp.GRB.MINIMIZE)

# 约束
# m.addConstr(gp.quicksum(x[:,j] for j in range(N))==1, name='con_in')  # 流入约束
# m.addConstr(gp.quicksum(x[i,:] for i in range(N))==1, name='con_out')  # 流出约束
# 流入约束
for j in range(N):
    m.addConstr(gp.quicksum(x[:,j])==1)
# 流出约束
for i in range(N):
    m.addConstr(gp.quicksum(x[i,:])==1)


# 破子圈约束
for i in range(1,N):
    for j in range(1,N):
        if i != j:
            m.addConstr(u[i]-u[j]+N*x[i][j]<=N-1)

# 求解
m.optimize()

# 结果展示
var_lst = m.getVars()  # 变量值
for i in range(0, len(var_lst)):
    if var_lst[i].X != 0:
        print(var_lst[i].VarName, var_lst[i].X)
print("目标函数值:", m.ObjVal)
best=(x.X).astype(int)
print(f"最优分配为:\n {best}")

# 记录按顺序遍历的节点编号
ans = np.where(best==1)  # 获取被选节点的索引
ans_i = ans[0]
ans_j = ans[1]
n0 = ans_i[0]  # 起始节点
anslist = [n0]  # 记录编号
coordlist = [coords[n0]]  # 记录坐标
for _ in range(N):
    n1 = ans_j[n0]  # 下一个节点
    anslist.append(n1) 
    coordlist.append(coords[n1])
    n0 = n1  # 更新当前节点,当前走到n1

# 绘图
plt.plot(np.array(coords)[:,0], np.array(coords)[:,1], 'o')  # 散点[x,y]
plt.plot(np.array(coordlist)[:,0], np.array(coordlist)[:,1], '--')  # 折线
plt.show()
目录
相关文章
|
7天前
|
缓存 并行计算 数据处理
全面提升Python性能的十三种优化技巧
通过应用上述十三种优化技巧,开发者可以显著提高Python代码的执行效率和性能。每个技巧都针对特定的性能瓶颈进行优化,从内存管理到并行计算,再到使用高效的数值计算库。这些优化不仅能提升代码的运行速度,还能提高代码的可读性和可维护性。希望这些技巧能帮助开发者在实际项目中实现更高效的Python编程。
77 22
|
15天前
|
关系型数据库 数据库 数据安全/隐私保护
云数据库实战:基于阿里云RDS的Python应用开发与优化
在互联网时代,数据驱动的应用已成为企业竞争力的核心。阿里云RDS为开发者提供稳定高效的数据库托管服务,支持多种数据库引擎,具备自动化管理、高可用性和弹性扩展等优势。本文通过Python应用案例,从零开始搭建基于阿里云RDS的数据库应用,详细演示连接、CRUD操作及性能优化与安全管理实践,帮助读者快速上手并提升应用性能。
|
17天前
|
数据采集 供应链 API
实战指南:通过1688开放平台API获取商品详情数据(附Python代码及避坑指南)
1688作为国内最大的B2B供应链平台,其API为企业提供合法合规的JSON数据源,直接获取批发价、SKU库存等核心数据。相比爬虫方案,官方API避免了反爬严格、数据缺失和法律风险等问题。企业接入1688商品API需完成资质认证、创建应用、签名机制解析及调用接口四步。应用场景包括智能采购系统、供应商评估模型和跨境选品分析。提供高频问题解决方案及安全合规实践,确保数据安全与合法使用。立即访问1688开放平台,解锁B2B数据宝藏!
|
18天前
|
API 开发工具 Python
【Azure Developer】编写Python SDK代码实现从China Azure中VM Disk中创建磁盘快照Snapshot
本文介绍如何使用Python SDK为中国区微软云(China Azure)中的虚拟机磁盘创建快照。通过Azure Python SDK的Snapshot Class,指定`location`和`creation_data`参数,使用`Copy`选项从现有磁盘创建快照。代码示例展示了如何配置Default Azure Credential,并设置特定于中国区Azure的`base_url`和`credential_scopes`。参考资料包括官方文档和相关API说明。
|
2月前
|
存储 缓存 Java
Python高性能编程:五种核心优化技术的原理与Python代码
Python在高性能应用场景中常因执行速度不及C、C++等编译型语言而受质疑,但通过合理利用标准库的优化特性,如`__slots__`机制、列表推导式、`@lru_cache`装饰器和生成器等,可以显著提升代码效率。本文详细介绍了这些实用的性能优化技术,帮助开发者在不牺牲代码质量的前提下提高程序性能。实验数据表明,这些优化方法能在内存使用和计算效率方面带来显著改进,适用于大规模数据处理、递归计算等场景。
87 5
Python高性能编程:五种核心优化技术的原理与Python代码
|
8天前
|
机器学习/深度学习 设计模式 API
Python 高级编程与实战:构建 RESTful API
本文深入探讨了使用 Python 构建 RESTful API 的方法,涵盖 Flask、Django REST Framework 和 FastAPI 三个主流框架。通过实战项目示例,详细讲解了如何处理 GET、POST 请求,并返回相应数据。学习这些技术将帮助你掌握构建高效、可靠的 Web API。
|
8天前
|
机器学习/深度学习 设计模式 测试技术
Python 高级编程与实战:构建自动化测试框架
本文深入探讨了Python中的自动化测试框架,包括unittest、pytest和nose2,并通过实战项目帮助读者掌握这些技术。文中详细介绍了各框架的基本用法和示例代码,助力开发者快速验证代码正确性,减少手动测试工作量。学习资源推荐包括Python官方文档及Real Python等网站。
|
9天前
|
机器学习/深度学习 设计模式 API
Python 高级编程与实战:构建微服务架构
本文深入探讨了 Python 中的微服务架构,介绍了 Flask、FastAPI 和 Nameko 三个常用框架,并通过实战项目帮助读者掌握这些技术。每个框架都提供了构建微服务的示例代码,包括简单的 API 接口实现。通过学习本文,读者将能够使用 Python 构建高效、独立的微服务。
|
9天前
|
消息中间件 分布式计算 并行计算
Python 高级编程与实战:构建分布式系统
本文深入探讨了 Python 中的分布式系统,介绍了 ZeroMQ、Celery 和 Dask 等工具的使用方法,并通过实战项目帮助读者掌握这些技术。ZeroMQ 是高性能异步消息库,支持多种通信模式;Celery 是分布式任务队列,支持异步任务执行;Dask 是并行计算库,适用于大规模数据处理。文章结合具体代码示例,帮助读者理解如何使用这些工具构建分布式系统。
|
10天前
|
机器学习/深度学习 数据可视化 TensorFlow
Python 高级编程与实战:深入理解数据科学与机器学习
本文深入探讨了Python在数据科学与机器学习中的应用,介绍了pandas、numpy、matplotlib等数据科学工具,以及scikit-learn、tensorflow、keras等机器学习库。通过实战项目,如数据可视化和鸢尾花数据集分类,帮助读者掌握这些技术。最后提供了进一步学习资源,助力提升Python编程技能。

热门文章

最新文章