Traveling Salesman Problem

Traveling Salesman Problem also known as TSP can be defined as follows: Given a number of cities and the costs of travelling from any city to any other city, what is the least-cost round-trip route that visits each city exactly once and then returns to the starting city. This is a good book about TSP. You can find TPS instances in this site. These instances can be used in order to benchmark algorithms. In this report some contructive heuristic methods (nearest neighbor, arbitrary insertion, farthest insertion) as well as a improvement heuristic (2-opt) are compared. Corresponding matlab files are also available.