An implementation of the travelling salesman problem using Brute-force, Branch-and-bound, removing-edges, MST-approximationn, Nearest_neighbour(greedy), Dynamic Programming, Randomized approach, Genetic programming

1 Description The objective of this project is to implement some algorithms for solving the Traveling Salesman Problem (TSP), to provide an experimental study of their running time and the quality of the solutions found.

2 Work to do

You must program different algorithms for the TSP problem, including:

I. The brute-force approach exploring all the possible solutions in a systematic way.

II. A branch-and-bound version.

III. The version adding and removing edges as seen in the exercise sheet.

IV. The approximation based on the minimum spanning tree as seen in the exercise sheet.

V. A version considering at each step the nearest unvisited choice (called the greedy approach).

VI. A dynamic programming approach (designed on your own or based on a publication found on the web that you must cite and detail properly the algorithm and complexities in your report)

VII. A version based on a randomized approach.

VIII. A version based on a genetic programming or ant colony approach.

IX. Another personal version.