运筹学经典问题（七）：旅行商问题（TSP）

问题描述

给定一系列城市和每对城市之间的距离，求解访问每座城市一次并回到起始城市的最短回路。

数学建模

集合：
$V$：城市集合

常量：
$c_{ij}$：城市$i$到城市$j$之间距离, $i\ne j$；

变量：
$x_{ij}$：是否从城市$i$走到城市$j$；

$$\begin{gathered} \sum _{i\in S}\sum _{j\in S,j\ne i}{c}_{ij}{x}_{ij} \\ s.t.\sum _{i\in S,i\ne j}{x}_{ij}=1,?j\in S \\ \sum _{j\in S,j\ne i}{x}_{ij}=1,?i\in S \\ \sum _{i,j\in S}{x}_{ij}\le |S|?1,2\le |S|\le n?1,S\in V \end{gathered}$$

1. 目标函数表示最小化旅行距离；
2. 第一个约束表示每个城市只能进入一次；
3. 第二个约束表示每个城市只能出发一次；
4. 第三个约束是去除子环路的约束，仅允许所有点都被包含进来的子环存在。

参考资料

1. 运筹优化常用算法、模型及案例实战：Python+Java 实现. 刘兴禄，熊望祺，臧永森，段宏达，曾文佳，陈伟坚.
2. 旅行推销员问题
3. Traveling with a Quantum Salesman