Supported versions: latest (3.8) 3.7 3.6 3.5 3.4 3.3 3.2 3.1 3.0 main dev
Unsupported versions:2.6 2.5 2.4 2.3

Traveling Sales Person - 函数族

• pgr_TSP- 当输入作为矩阵单元信息给出时。

• pgr_TSPeuclidean - 当输入是坐标时。

一般信息

问题定义

旅行推销员问题 (TSP) 提出以下问题：

给定一个城市列表以及每对城市之间的距离，哪条是访问每个城市一次并返回出发城市的最短路线？

起源

旅行推销员问题由数学家 William Rowam Hamilton 爵士 和 Thomas Penyngton Kirkman 于 18 世纪研究。

关于 Hamilton 和 Kirkman 工作的讨论，可以在 《图论》（Biggs 等，1976年） 一书中找到。

• ISBN-13: 978-0198539162

• ISBN-10: 0198539169

人们认为旅行推销员问题（TSP）的一般形式最早由维也纳和哈佛的卡尔·门格尔（Karl Menger）研究。后来，普林斯顿的哈斯勒、惠特尼和梅里尔（Hassler, Whitney & Merrill）进一步推动了这个问题。关于门格尔和惠特尼之间的联系以及TSP的发展，可以在 组合优化的历史(直到1960年)

计算经过 : math:n 城市的不同旅行次数：

• 给定一个起始城市，

• 第二个城市还有 $n-1$ 个选择，

• 第三个城市的 $n-2$ 选项等。

• 相乘得到 $(n-1)！=(n-1)(n-2)..1$.

• 现在，由于旅行成本不取决于旅行的方向：

  • 这个数字乘2

  • $(n-1)!/2$.

特征

• 该问题是一个NP-hard优化问题。

• 使用度量算法

• Implementation generates solutions that are twice as long as the optimal tour in the worst case:

• Graph characteristics for best performance:

  • 图是无向的

  • 图是全连通的

  • 图中，边上的旅行成本服从三角不等式。

  • 旅行费用是对称的：

    • 从 u 到 v 的旅行费用与从 v 到 u 的旅行费用相同

TSP 可选参数

列	类型	默认	描述
start_id	ANY-INTEGER	0	第一个访问顶点 当 0 时，任何顶点都可以成为第一个访问顶点。
end_id	ANY-INTEGER	0	返回 start_vid 之前最后访问的顶点。 当为 0 时，任何顶点都可以成为返回 start_id 之前最后访问的顶点。 当 NOT 0 且 start_id = 0 时，它是第一个和最后一个顶点

另请参阅

参考

• Boost: 度量旅行商问题近似算法

• 滑铁卢大学TSP研究

• 维基百科：旅行商问题

索引和表格

• Index

• Search Page