CIS 3223 Labs 13 AND 14 – Traveling Salesman Problem (TSP) Heuristics

DUE: (by noon on Friday, May 9, 2008)

 

TSP

 

In Lab 3 you implemented the nearest neighbor algorithm for TSP. This algorithm is very simple to implement and very fast (quadratic in number of cities), but it gives only suboptimal solutions. There are many more heuristical algorithms that are either faster or more successful than the nearest neighbor algorithm. Several of these algorithms are described in Chapter 9 of Dasgupta textbook. Many more are described in

“The Traveling Salesman Problem: A Case Study in Local Optimization” by David S. Johnson and Lyle A. McGeoch.

 

 

TASK

Your goal is to implement in Matlab one of the TSP heuristics other than the nearest neighbor algorithm. You have a freedom to choose the algorithm from the textbook, the referenced paper, or try to invent your own solution. The total score for the lab is 200% (100% are regular points and 100% are extra credit for a particularly deserving work). Your submission should contain:

  1. The pseudo code with discussion of how the algorithm works, and with analysis of its runtime
  2. Matlab implementation of the algorithm
  3. Performance evaluation. You should evaluate the algorithm on at least several data sets with varying numbers of cities, preferably with varying properties. The performance measures are the cost of the resulting tour and the runtime. For benchmarking purposes, you should compare the algorithm with the TSP implementation from Lab 3. Do not just provide the numbers, but provide the discussion that gives an insight into the properties of the proposed algorithm with an emphasis on advantages, drabacks and possible improvements of the algorithm.
  4. Extra credit will be given for implementations of particularly challenging existing algorithms, for proposing successful new TSP heuristics, and for particularly detailed and insightful evaluation studies.