[Solved]: TSP problem with a benchmark data

Problem Detail: 

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.

3. 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.

Asked By : Les

Answered By : Bill Cook

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).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/56597

3.2K people like this

 Download Related Notes/Documents