readme

Simulated annealing (SA) for the Symmetric Euclidean TSP

This directory contains a simple solver written in ansi-C
for the Symmetric Euclidean Traveling Salesman Problem. 

It is available from http://www.cenaath.cena.dgac.fr/~maugis/tsp.shar
 
Produces a postscript output of 
- the problem instance 
- a minimum spanning tree (mst) connecting the cities 
- an approximation based Prim's algorithm
- the solution found by simulated annealing

Solution based on local search heuristics for non-crossing paths and
nearest neighbors. See G. Reinelt, "The Traveling Salesman Problem",
Springer Verlag 1994.

Install: gcc -O4 -o tsp tsp.c -lm ; tsp n=20 | ghostview -
or     : make all

Input from a file or generated randomly
Additional data sets are obtainable from TSPLIB:
http://www.iwr.uni-heidelberg.de/iwr/comopt/soft/TSPLIB95/TSPLIB.html

Usage: tsp [-v] [n=%d] [s=%d] [filename]
     -v       : verbose
     n=       : nb of cities (cities generated randomly)
     s=       : seed nb of random generator
     filename : tsp input file. If none, stdin assumed. 

Input file format:
n
x1 y1 name1
y2 y2 name2
...
 
where x1 y1 can be in the form longitude - latitude .i.e E002184700 N49100100
or just numbers .i.e 12 24 23e10

Enjoy !

        Lionnel Maugis * Sofreavia / ATM 
           Tel : [phone]
      FAX RNIS : (33-1) 60-48-70-20
        e-mail : [e-mail]
          http : http://www.cenaath.cena.dgac.fr/~maugis 
       Address : 1, rue de Champagne - 91200 ATHIS-MONS
Postal Address : Orly Sud 205        - 94542 ORLY AEROGARE CEDEX