CIS 3223 Lab03 – Nearest Neighbor Algorithm for Traveling Salesman Problem (TSP)

DUE: (before the next lab, 10:30am Friday, Feb 15, 2008)

 

Traveling Salesman Problem

 

The traveling salesman problem, or TSP, is generalization of the sorting problem. In the TSP, we are given a set {c1, c2, . . . , cN} of cities and for each pair {ci, cj} of distinct cities a distance d(ci, cj). Our goal is to find an ordering π of the cities that minimizes the quantity

This quantity is referred to as the tour length, since it is the length of the tour a salesman would make when visiting the cities in the order specified by the permutation, returning at the end to the initial city. TSP is called symmetric if the distances satisfy d(ci, cj) = d(cj, ci) for 1 ≤ i, j ≤ N.

 

As illustration, the following is an example of TSP ordering of American cities.

 

The symmetric traveling salesman problem has many applications, from VLSI chip fabrication to X-ray crystallography, and a long history. It is “intractable” because any algorithm for finding optimal tours must have a worst-case running time that grows faster than any polynomial. This gives rise to many heuristic algorithms that find near-optimal tours quickly. In this lab, you will have to implement a simple heuristics, called the Nearest Neighbor Algorithm.

 

Nearest Neighbor Algorithm:

 

We construct an ordering π ( 1 ), . . . , π (N) of the cities, such that the initial π(1) is chosen as a random integer between 1 and N, while every other π(i), i = 2… N, is chosen by the following rule:

Among the cities whose index is not already selected to ordering {π(1), π(2), …., π(i—1)}, find the city ck with the closest distance to cπ (i—1) and set π(i) = k.

The resulting tour traverses the cities in the order defined by cπ ( 1 ), . . . ,cπ (N).

 

 

TASKS

  1. (20%) Write the pseudocode for the Nearest Neighbor Algorithm. Assume that each city ci is represented by its location (xi, yi) and that the distance d(ci, cj) is simple Euclidean distance calculated as

Input to the algorithm is set of pairs S = {(x1, y1), (x2, y2), …, (xN, yN)} and its output is ordering π = π(1), π(2), …., π(N).

 

  1. (20%) Estimate the runtime T(N) of the Nearest Neighbor Algorithm.

 

  1. (40%) Implement the Nearest Neighbor Algorithm in Matlab. You should do it by writing the function:

function ordering = NN_TSP(cities)

that takes cities which is a matrix of dimension N´2 as input (where each row represents a city and columns are x and y coordinates of its location) and produces ordering as output. Submit the Matlab code you wrote.

 

  1. (20%) Test the algorithm on N = 10, 100, 1000 randomly generated cities. You can generate N random cities as

cities = rand(N, 2);

You can plot the original ordering (path that traverses all cities in order from city 1 to city N) as

plot(cities(:,1),cities(:,2))

You can plot the resulting ordering of cities as

plot(cities(ordering,1),cities(ordering,2))

Provide the plots of the original ordering and ordering after the Nearest Neighbor Algorithm for each N. List the actual run time for each N. Discuss how successful is the resulting ordering. Do you see some imperfections in the solution (places where you think the algorithm could have produced better solution)?