The travelling salesman problem (TSP) asks the following questions: "Given a list of cities and the distance between each pair of cities, what is the shortest possible route that vistis each city exactly one and returns to the original city?"
We are considering the solution of the symmetric version of the TSP over a complete graph G = (V, E) with n = |V| nodes. More specifically, the graph considered has 12 nodes, n = 12. Moreover, since it is a complete graph the number of edges is
\[|E|= n(n−1) = 66\]The graph is non-directed and each edge \((i,j) \) has its associated cost \(c_{i,j} \) satisfying
\[c_{i,j} = c_{j,i}\]In order to compute the solution of the symmetric TSP, we randomly generated the cost matrix (or distance matrix) C.
TSP is an NP-hard problem in combinatorial optimization.
In this project we solve the TSP for a small intance problem by applying problem relaxations and different heuristics finding lower and upper bounds of the solution. You can download the project here.