TSP Algorithm for 1000 cities

[ster]

Hello..
I have to solve TSP for about 1000 cities in maximum 10 secs...!
I 'm thinking of using a liner programming-based algorithm (haven't chosen exactly yet), but I don't know if he well be sufficient..
What do you think?

[Zachm]

Have you looked at this link (http://en.wikipedia.org/wiki/Traveling_salesman_problem) ?

It contains a handful of exact & heuristic methods for the TSP problem.

Personally, I don't think that any of the exact methods will suffice your time constraint (10 sec), maybe try a heuristic method like GA or Adaptive Simulated Annealing ?

One more thing: have you considered parallel computation ? it might boost your computation time.

Best of luck !

[ster]

Thanx for the reply. Yeah, I 've checked this out. Actually, this is were i started from. :)

Ok, I 'll study both GA (Genetic Algorithms i suppose) and the Adaptive Simulated Annealing thing. Hope i choose the appropriate soon...


I 'm also thinking of bying this one...
http://www.amazon.com/Traveling-Salesman-Problem-Computational-Mathematics/dp/0691129932/sr=8-2/qid=1170773888/ref=pd_bbs_sr_2/105-5246712-7197223?ie=UTF8&s=books

Has anyone read this?? Is it good for a starter on TSP problems?

[Zachm]

Right, GA = Genetic Algorithm :)