如何提高“协和” TSP求解器的质量？我在滥用它吗？

Question

我正在尝试使用concorde以下格式在文件中使用TSP求解器：

NAME : p5
COMMENT : Nada
TYPE : TSP
DIMENSION : 20
EDGE_WEIGHT_TYPE : EUC_2D
NODE_COORD_SECTION
0 0.329733 0.67714
1 0.823944 0.035369
2 0.002488 0.866692
3 0.241964 0.671822
4 0.98876 0.134457
5 0.879147 0.457779
6 0.021017 0.271951
7 0.221737 0.367143
8 0.549802 0.523319
9 0.363839 0.22359
10 0.696631 0.495935
11 0.279072 0.100501
12 0.660156 0.860675
13 0.251769 0.029172
14 0.32112 0.207704
15 0.821433 0.507387
16 0.095411 0.953448
17 0.115897 0.269363
18 0.704484 0.411328
19 0.705198 0.795917

由于找不到有关格式的指南，因此我只修改了我下载的示例文件。我正在运行以下命令：

concorde myFile.tsp

快速（〜45ms）将解决方案输出为.sol文件，结果如下：

20
0 10 19 8 12 15 5 4 18 1 
9 17 6 11 7 13 14 3 2 16 

绘图，我得到：

通过目视检查，这与理想的解决方案相距太远。从而，

1. 我的文件格式或命令有问题吗？

2. 如果不是，考虑到计算解决方案的速度，我是否可以提示它花费更多时间寻找更好的解决方案？

Answer 1

EUC_2D是舍入的 L2范数。即，将两点之间的距离作为四舍五入到最接近整数的欧几里得距离。您的点之间的距离都将为0或1，而协和式飞机将像您绘制的那样进行一次浮潜游览。

扩大您的问题，直到舍入不再起作用为止。