一、问题描述：是一个经典的组合优化问题
一个商人从一点出发，经过所有点后返回原点。
目标：经过所有点的最短路程。
约束：
1，除起点和终点外，所有点当且仅当经过一次；
2，起点与终点重合；所有点构成一个连通图
图论解释：该问题实质是在一个带权完全无向图中，找一个权值最小的哈密尔顿回路
哈密尔顿回路（Hamilton回路）
定义：G=(V,E)是一个图，遍历图中每个顶点一次且仅一次的路线称为哈密尔顿路径，遍历图中每个顶点一次且仅一次的回路(从哪里出发再回到哪里)称为哈密尔顿回路。具有哈密尔顿回路的图叫做哈密尔顿图。
【离散数学】图论（四）哈密顿回路（Hamiltonian cycle） - 简书 (jianshu.com)
二、TSP问题建模
(29条消息) 旅行商(TSP)问题建模和子路径(subtour)消除约束详解_Dragon Fly的博客-CSDN博客_tsp约束条件
三、存在子回路（subtour）
导致解中含有多个相离的环，也就是subtour。需要的解是一个单个的经过所有点的大环
子路径消除约束常见两种：
- 加入
subtour-elimination约束 -
加入Miller-Tucker-Zemlin(MTZ)约束
1： subtour-elimination 消除子环路
主要想法就是，根据子环路的特点，在模型中添加相应的约束，将其破开>>增加子环路不存在的条件就是(即破圈的方法)
粗犷理解：点的个数为N，S为点的集合，除了包含全部点的集合的情况，所有其他少了一个或几个点的集合所形成的点点线条必须小于等于（集合中点总数-1）(即少了一个或几个点后，连线边要求比现存的点少）
subtour-elimination的约束，思路就是相当于割平面法，是一个枚举的约束，复杂度
采用Gurobi或者CPLEX求解器中提供的callback(回调函数)的方法来动态的添加subtour-elimination约束。
2 ： Miller-Tucker-Zemlin(MTZ)约束消除子环路
对每个结点，引入一个决策变量，
粗犷理解：M 取无穷大数，是运筹学中常见的基本操作，取M = N （N为节点的个数）
由于TSP的起点和终点是一致的，如果不做处理，会出现infeasible的情况
修正：点集为V ′ = { 1 , 2 , ⋯ , N , N + 1 } V'=\{1,2,..., N,N+1}，一共N + 1 个点，其中点1和点N + 1 是同一个点，点1表示起点，点N + 1 表示终点
文章来源：https://www.toymoban.com/news/detail-437160.html
(29条消息) 运筹学修炼日记：TSP中两种不同消除子环路的方法及callback实现（Python调用Gurobi求解，附以王者荣耀视角解读callback的工作逻辑）_刘兴禄的博客-CSDN博客文章来源地址https://www.toymoban.com/news/detail-437160.html
到了这里，关于旅行商问题 Traveling Salesman Problem(TSP)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
