2
$\begingroup$

I've got a test Travel Salesman Problem's data with known optimal solutions. It's in a form of set of 2D points. Particularly, this is a tsplib format; sources are here and here.

I'd started a simple test with the "Western Sahara - 29 Cities" (wi29) and found that my algorithm rapidly found a few better particular solutions than the proposed optimum.


I checked one of them manually and didn't find an error. So, I guess, here're the three options.

  1. I did a mistake.
  2. Wrong optimum.
  3. Different problems were solved.

1 and 2. My solution tour is:

17>18>19>15>22>23>21>29>28>26>20>25>27> 24>16>14>13>9>7>3>4>8>12>10>11>6>2>1>5

(will list my checking calculations if requested)

Rounded length: 26040.76. Optimal reference value: 27603.

  1. I can't find a particular task descriptions and especially rounding policy for the TSPLib examples optimums. This is important, because they're looking rounded or discretized in another manner, but simple result rounding isn't looks like it.
$\endgroup$
2
$\begingroup$

In the TSPLIB norm, the travel cost between each pair of cities is the Euclidean distance between the points rounded to the nearest integer (not the distance rounded to two decimal places).

$\endgroup$
1
$\begingroup$

While comparing your solutions with the TSPLib's proposed optimal solutions be assured that you're solving the same problem.

I'd found here two important points about it.

  1. In TSPLib, the 2D data is rational pairs accurate to the 4th decimal place, but the distance function is Euclidean metrics result rounded to integer values.
  2. They're solving the traveling salesman problem with returning to the start.

This was obtained from hints here and confirmed by diving into their code.

Later, I found a useful FAQ for solving all my problems without diving into the library's code, hope it saves time for readers. TSPLIB FAQ

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.