简单TSP的数据

Question

我写了一个简单的遗传算法,可以解决5个城市的旅行商问题.我想看看它如何处理更多城市的问题,如10,25,50,100,但我找不到问题的样本日期来尝试.基本上,我正在寻找城市之间距离的二维列表或矩阵.如果有解决方案会很好.我应该在哪里看？

先感谢您

Answer 1

TSPLIB是TSP的一个着名的基准库,其实例范围从14个到近100,000个城市.实例已经解决为最优,在某些情况下,最佳解决方案也是可用的.

许多实例具有现实世界背景,例如旅行在德国,瑞士,美国或全世界的城市.一些实例代表了计算机板布局的钻孔问题.还有一个实例代表了尤利西斯的航行.

Answer 2

我在网上找到的消息来源非常庞大.我可能做错了,但是10个地方(城市)需要~0.6s,11个地方需要~7s.我能找到的最小的已知解决方案数据集是15个位置(并且被认为是"小","经典"是48个位置)但也许那些用于优化(非强力)算法.最后,我用现实世界的城市制作了自己的桌子:

           m
           a
           a                           h
           s       h   s               u
           t   a   e   i   g           l
           r   a   e   t   e           s
           i   c   r   t   l   e   b   b   a       e
           c   h   l   a   e   c   o   e   n   o   p
           h   e   e   r   e   h   n   r   n   h   e
           t   n   n   d   n   t   n   g   e   e   n
maastricht 0   29  20  21  16  31  100 12  4   31  18
    aachen 29  0   15  29  28  40  72  21  29  41  12
   heerlen 20  15  0   15  14  25  81  9   23  27  13
   sittard 21  29  15  0   4   12  92  12  25  13  25
    geleen 16  28  14  4   0   16  94  9   20  16  22
      echt 31  40  25  12  16  0   95  24  36  3   37
      bonn 100 72  81  92  94  95  0   90  101 99  84
  hulsberg 12  21  9   12  9   24  90  0   15  25  13
     kanne 4   29  23  25  20  36  101 15  0   35  18
       ohe 31  41  27  13  16  3   99  25  35  0   38
      epen 18  12  13  25  22  37  84  13  18  38  0

Optimal (by program): cities 0-7-4-3-9-5-2-6-1-10-8-0 = 253km
maastricht -> hulsberg -> geleen -> sittard -> ohe -> kanne -> echt
-> heerlen -> bonn -> aachen -> epen -> kanne -> maastricht

程序可读的数据格式是部分表(因为它是对称的):

29 20 21 16 31 100 12 4 31 18
15 29 28 40 72 21 29 41 12
15 14 25 81 9 23 27 13
4 12 92 12 25 13 25
16 94 9 20 16 22
95 24 36 3 37
90 101 99 84
15 25 13
35 18
38

对我来说,在第3代i7(i7-3630QM)上处理大约需要6.7秒.程序是用C++编写的,单线程和简单的强制可能性.对于测试来说,删除一个地方可能更实际,然后需要大约660毫秒(0.7秒),这仍然足以看出代码更改是否有很大的不同.