Travelling Salesman Problem
Given a list of cities and their pairwise distances, the aim of this study is to find the shortest
possible tour that visits each city exactly once. Here I embrace the Heuristic approach which
means that algorithms for finding feasible and acceptable solutions that will give upper
bounds on the objective value. Tour construction under heuristic approach is based on the
Nearest Neighbour, Greedy, and Tour Improvement heuristics.
Briefly, Nearest Neighbour method is perhaps the simplest and most straightforward TSP
heuristic. The key to this algorithm is to always visit the nearest city. The Greedy heuristic
gradually constructs a tour by repeatedly selecting the shortest edge and adding it to the tour
as long as it doesn’t create a cycle with less than N edges, or increases the degree of any node
to more than 2. We must not add the same edge twice of course. In Toru Improvement, Once
a tour has been generated by some tour construction heuristic, we might wish to improve that
solution. There are several ways to do this, but the most common ones are the 2-opt and 3-
opt local searches. Their performances are somewhat linked to the construction heuristic
used.
Nearest Neigbour Heuristic
As briefly discussed above, the idea is that you start at a random city, from which you travel
to the nearest city that has not been visited before. This is repeated until you have passed
every city. The advantage with this heuristic is that it yields a quick solution, however not
necessarily the optimal one. I use three different data having different number of cities. he
advantage with this heuristic is that it yields a quick solution, however not necessarily the
optimal one.
The Nearest Neighbour heuristic constructs a feasible tour as follows:
1. Randomly choose a start node and start with the “tour” that only consists of that node.
2. Repeat the following step until all nodes are contained in the tour:
Among all nodes not yet in the tour, choose one that is closest to the last inserted node and
append it to the tour.
The pseudo code of nearest neighbor algorithm is the following:
1. Stand on an arbitrary vertex as current vertex.
2. Find out the lightest edge connecting current vertex
and an unvisited vertex V.
3. Set current vertex to V.
4. Mark V as visited.
5. If all the vertices in domain are visited, then
terminate.
6. Go to step 2
In small data sets, I have 10 cities while in the medium and large data set I have 15 and 50
respectively.
Instance
Tour Length
Start City
Time Elapsed
Small
293.4324
10
0.004108
Medium
403.0037
10
0.003403
Large
780.3112
10
0.004435
Optimal paths follow the arrow direction.
Optimal Path of Small data
10 2 8 5 3 4 7 1 6 9
Optimal Path of Medium data
10 1 2 14 6 5 11 7 12 4 16 8 3 9 15 13
Optimal Path of Large data
10 17 8 9 31 32 28 4 45 14 7 38 26 30 6 21 1
11 27 34 2 25 48 13 36 33 44 39 18 46 29 3 5 23
42 41 37 15 22 20 47 50 16 12 24 35 40 19 49 43
Figure 1: Solution when applying the nearest neighbour heuristic to the test
