3.9. 旅行销售人(TSP - traveling Salesman 问题)

给出一个城市列表,找到一个每周访问每个城市的销售人员的最短导览。

此问题由 Wikipedia 定义。它是计算数 中最密调查的问题之一。然而,在现实世界中,它通常只是规划问题的一部分,以及其他限制,如员工的转变限制。

问题大小

dj38     has  38 cities with a search space of   10^43.
europe40 has  40 cities with a search space of   10^46.
st70     has  70 cities with a search space of   10^98.
pcb442   has 442 cities with a search space of  10^976.
lu980    has 980 cities with a search space of 10^2504.

问题困难

尽管 TSP 的简单定义,但问题似乎难以解决。由于这是一个 NP-hard 问题(如大多数规划问题),当数据问题稍微改变时,特定问题数据集的最佳解决方案可能会改变很多问题:

旅行销售人员优化解决方案可快速显示最佳解决方案变化(如果我们添加 1 个新位置)