Travelling Salesperson Problem

Aims: To understand and implement a number of heuristics for the Travelling Salesperson Problem (TSP). To study applications of TSP.

Background: : TSP is a famous problem which is easy to formulate: given n “cities”, find a shortest route that visits every “city” exactly once. TSP is hard to solve and the problem has a large number of applications. Large instances of the problem are solved by heuristics which are fast algorithms, but without quality guarantee. Heuristics are also used when the distances between the “cities” are not exact.

Early Deliverables

  1. A report describing several TSP heuristics (e.g., Nearest Neighbour, Repeated Nearest Neighbour, Greedy).
  2. Reports: Complexity, NP hardness and the big O notation
  3. Implementations of Nearest Neighbour and Repeated Nearest Neighbour.

Final Deliverables

  1. Description of several TSP heuristics (e.g., Nearest Neighbour, Repeated Nearest Neighbour, Greedy, Vertex Insertion).
  2. Implementation of all heuristics described in the report.
  3. Tables comparing quality and runtime of these heuristics on various testbeds.
  4. GUI for the heuristics.
  5. A report on TSP applications.
  6. A short report on complexity of algorithms.

Suggested Extensions

  • To study and implement Greedy+2-Opt. To include it into the tables.