Travelling Salesman

http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/atsp/

Problem Description

The travelling salesman problem (TSP) can be formulated as follows: Consider a weighted graph G with n nodes, labeled 1,2,...,n. The nodes represent cities, and the edges represent the roads between the cities. Each edge from i to j has weight or cost C(i,j), representing the length of the road. The problem is to find the shortest tour that visits all the cities exactly once (except the starting city, which is also the terminating city). This problem is described in Section 4.7 of [7]. The problem is determined by the cost matrix C, where C(i,j) = C(j,i) (possibly infinity).

Programs

tsp.m
This MATLAB program gives the best found tour via the CE method.

Usage:
Call the program from MATLAB, with the following syntax:

pi=tsp(N,rho,alpha,C,traj)

Example: tour=tsp(1000,0.05,0.8,C,0)
where C is a matrix of costs (lengths) between nodes.

Inputs:
N	-	Number of samples to generate each round
rho	-	fraction of best samples to take
alpha	-	smoothing parameter
C	-	C(i,j) is the cost between node i and node j
traj	-	0, node placements
		1, node transitions
Outputs:
pi	-	the best tour found

gtsp0.m This program is used internally to generate tours via node placements.

gtsp1.m This program is used internally to generate tours via node transitions.

stsp.m This program is used internally to evaluate the performance of a particular tour.

minitsp.m This is a program which generates a smaller TSP problem (with a specified number of nodes) from a larger one. This idea is mentioned in Remark 4.13 in [7].