Traveling salesman

Prize: €5,000
Time: 145 days left

Find the shortest tour that visits each city one time and then returns to the start.

Problem

You get n cities c_0, \dots, c_{n-1} \in \mathbb{R}^2. A tour is a permutation \sigma of \{0, \dots, n-1\}, and its length is:

L(\sigma) = \sum_{i=0}^{n-1} d\left(c_{\sigma(i)},\, c_{\sigma((i+1) \bmod n)}\right)

where d is the Euclidean distance:

d(a, b) = \lVert a - b \rVert_2 = \sqrt{(a_x - b_x)^2 + (a_y - b_y)^2}

The goal is to find \sigma^* = \arg\min_{\sigma \in S_n} L(\sigma). There are (n-1)!/2 different tours, so a full search is possible only for small n.

Submission

One Python file solve.py (standard library only, no network). It reads instance.json from the current directory:

{"cities": [[12, 840], [530, 77], [301, 412]]}

and prints the tour as a JSON list of city indices on its last output line, for example [0, 2, 1]. Each instance has a limit of 20 seconds.

Example instance: example.json

Score

The score is the sum of the tour lengths on the K = 3 hidden instances, and a lower score is better:

S = \sum_{k=1}^{K} L_k(\sigma_k)

The hidden instances have n \in \{50, 200, 1000\} cities. If an answer is wrong or late on one instance, the full submission fails.

Submit

Limit: 5 per day