DA-project-tsp

Second project of the Design of Algorithms unit course

Objectives

Design efficient heuristics to solve the travelling salesman problem with different datasets. You should have:

• An exhaustive backtracking approach;
• A 2-opt approximation algorithm that relies on the triangular inequality;
• Other algorithms that, theoretically, perform better than the above.

A presentation should also be prepared as to explain and analyse the heuristics that were developed throughtout the project. You should compare the efficiency and optimality between heuristics with the aid of graphs and plots.

What we did

• An exhaustive backtracking approach;
• A 2-approximation algorithm that relies on the triangular inequality;
• Christofides algorithm
• A tour improvement algoritm: the 2-opt algorithm

Grade

19.62/20.00