问题描述
给定一系列城市和每对城市之间的距离，求解访问每座城市一次并回到起始城市的最短回路。
数学建模
集合：
V
V
V：城市集合
常量：
c
i
j
c_{ij}
cij：城市
i
i
i到城市
j
j
j之间距离,
i
≠
j
i \neq j
i=j；
变量：
x
i
j
x_{ij}
xij：是否从城市
i
i
i走到城市
j
j
j；
∑ i ∈ S ∑ j ∈ S , j ≠ i c i j x i j s . t . ∑ i ∈ S , i ≠ j x i j = 1 , ∀ j ∈ S ∑ j ∈ S , j ≠ i x i j = 1 , ∀ i ∈ S ∑ i , j ∈ S x i j ≤ ∣ S ∣ − 1 , 2 ≤ ∣ S ∣ ≤ n − 1 , S ∈ V \sum_{i \in S}\sum_{j \in S,j \neq i} c_{ij}x_{ij} \\ s.t. \sum_{i \in S, i \neq j} x_{ij} = 1, \forall j \in S \\ \sum_{j \in S, j \neq i} x_{ij} = 1, \forall i \in S \\ \sum_{i,j \in S}x_{ij} \leq \vert S\vert - 1, 2 \leq\vert S\vert\leq n-1,S\in V i∈S∑j∈S,j=i∑cijxijs.t.i∈S,i=j∑xij=1,∀j∈Sj∈S,j=i∑xij=1,∀i∈Si,j∈S∑xij≤∣S∣−1,2≤∣S∣≤n−1,S∈V
- 目标函数表示最小化旅行距离；
- 第一个约束表示每个城市只能进入一次；
- 第二个约束表示每个城市只能出发一次；
- 第三个约束是去除子环路的约束，仅允许所有点都被包含进来的子环存在。
参考资料
- 运筹优化常用算法、模型及案例实战：Python+Java 实现. 刘兴禄，熊望祺，臧永森，段宏达，曾文佳，陈伟坚.
- 旅行推销员问题
- Traveling with a Quantum Salesman
