Rudy’s OBTF Rudolf Adamkovič

Home / Computer science / Traveling salesman problem (TSP) / Computation: Python, Nearest neighbor heuristic (NN)

Input

The distance matrix

\begin{equation*} D \in \mathbb{Z}^{n \times n}, \end{equation*}

constructed as follows:

  1. load the instance pr76 from TSPLIB (Reinelt, n.d.)
  2. measure the Euclidean distances between all cities
  3. round the distances and convert them to integers
n = len(PR76)
c = np.array(PR76)[:, 1:]
d_float = sp.spatial.distance_matrix(c, c)
d = np.rint(d_float).astype(int)
Table 1: Instance PR76 from TSPLIB Reinelt (n.d.)
City x y
1 3600 2300
2 3100 3300
3 4700 5750
4 5400 5750
5 5608 7103
6 4493 7102
7 3600 6950
8 3100 7250
9 4700 8450
10 5400 8450
11 5610 10053
12 4492 10052
13 3600 10800
14 3100 10950
15 4700 11650
16 5400 11650
17 6650 10800
18 7300 10950
19 7300 7250
20 6650 6950
21 7300 3300
22 6650 2300
23 5400 1600
24 8350 2300
25 7850 3300
26 9450 5750
27 10150 5750
28 10358 7103
29 9243 7102
30 8350 6950
31 7850 7250
32 9450 8450
33 10150 8450
34 10360 10053
35 9242 10052
36 8350 10800
37 7850 10950
38 9450 11650
39 10150 11650
40 11400 10800
41 12050 10950
42 12050 7250
43 11400 6950
44 12050 3300
45 11400 2300
46 10150 1600
47 13100 2300
48 12600 3300
49 14200 5750
50 14900 5750
51 15108 7103
52 13993 7102
53 13100 6950
54 12600 7250
55 14200 8450
56 14900 8450
57 15110 10053
58 13992 10052
59 13100 10800
60 12600 10950
61 14200 11650
62 14900 11650
63 16150 10800
64 16800 10950
65 16800 7250
66 16150 6950
67 16800 3300
68 16150 2300
69 14900 1600
70 19800 800
71 19800 10000
72 19800 11900
73 19800 12200
74 200 12200
75 200 1100
76 200 800
© 2025 Rudolf Adamkovič under GNU General Public License version 3.
Made with Emacs and secret alien technologies of yesteryear.