Search code examples
algorithmtraveling-salesman

How to improve the quality of the `concorde` TSP solver? Am I misusing it?

I'm trying to use the concorde TSP solver in a file using the following format:

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

Since I couldn't find a guide about the format, I just modified a sample file I downloaded. I am running the following command:

concorde myFile.tsp

It quickly (~45ms) outputs the solution as a .sol file, which results in something like that:

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

Graphing, I get:

enter image description here

Which, by visual inspection, is too far from an ideal solution. Thus,

  1. Am I doing something wrong with the file format or command?

  2. If not, considering how fast it computed the solution, can I prompt it to spend more time looking for better solutions?

Solution

  • EUC_2D is the rounded L2 norm. That is, the distance between two points is taken to be their Euclidean distance rounded to the nearest integer. Your points are all going to be at distances 0 or 1 to one another and Concorde is going to generate a daft tour like the one you drew.

    Scale your problem up until the rounding stops making a difference.