运筹学经典问题(七):旅行商问题(TSP)

发布时间:2023年12月17日

问题描述

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

在这里插入图片描述

数学建模

集合:
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 iS?jS,j=i?cij?xij?s.t.iS,i=j?xij?=1,?jSjS,j=i?xij?=1,?iSi,jS?xij?S?1,2Sn?1,SV

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

参考资料

  1. 运筹优化常用算法、模型及案例实战:Python+Java 实现. 刘兴禄,熊望祺,臧永森,段宏达,曾文佳,陈伟坚.
  2. 旅行推销员问题
  3. Traveling with a Quantum Salesman
文章来源:https://blog.csdn.net/JESSIENOTCAR/article/details/134993647
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。