Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What is the fastest algorithm for asymmetric TSP? Maybe someone knows the fastest solution according to computer calculations. For example, WinQSB calculates 60 cities in 2-3 seconds on Intel Core 2, 2 GHz 2 Gb memory. At this moment I am reviewing Branch and Bound. My goal is the fastest calculation of the optimal (the shortest) path between $n$ points (I have distances between points; the distance from A to B does not equal the distance from B to A, so it's an asymmetric TSP).

Thank you for any help.

share|improve this question
    
The title contains the word "asymmetric" (in an ungrammatical position). Are you looking for algorithms for the asymmetric TSP? Then the text of the question should reflect that. ("I have distances between them" sounds more like symmetric to me.) The last time I checked, cutting-plane methods seemed to be state-of-the-art, but that was many years ago. –  joriki Apr 8 '11 at 5:15
    
@joriki thank you. any way asymmetric algo. –  igor Apr 8 '11 at 5:53
    
@igor: It's a bit confusing that you speak about asymmetric TSP algorithms. There is a symmetric and an asymmetric TSP, and algorithms for these two problems; symmetry and asymmetry are not properties of the algorithms. –  joriki Apr 8 '11 at 6:42
    
@joriki, sorry I am not native English speaker, but I think you understand the crux of the matter :) –  igor Apr 8 '11 at 7:29
    
@igor: OK, I tried to improve the wording. –  joriki Apr 8 '11 at 7:46

3 Answers 3

@Zach Langley, @igor Yes there is no problem at all with an asymmetric TSM problem for a genetic algorithm. TSM problems are frequently used to teach people about genetic programming so there should be a lot of stuff out there tutorials ect.

The way I would do it is to simply have a lookup table. so if each of the points in the problem were called say 1 2 3 then a lookup table could be something set up like.
[12] = 1
[13] = 2
[21] = 2
[31] = 2
ect ect
So the program just assesses each pair one at a time to get a total journey length. Then the normal operators will sort out which are the good and bad paths. This might not be the best way to encode the problem but it will work. Genetic algorithms dont really care what the data means all it does is breed good solutions with other good solutions and discards families of bad solutions to streamline its search so there is probably a superior way to encode the data.
As for justifying it being the fastest I cannot cite any papers or anything off hand but this type of problem evolutionary programming has shined on for the past 3 decades. The TSP have been used as a benchmarking tool for various forms of evolutionary techniques to evaluate performance and are use to pit them vs other non evolutionary techniques. For various problems like this evolutionary strategies beat non evolutionary methods for speed.

It is important to note that evolutionary strategies dont check every single combination so you never are 100% sure you have the global optimum. However they are incredibly fast (significantly faster than any other method) and will get you very close to the optimum if not the actual optimum.

Sorry for posting another answer I couldnt make a comment this long

share|improve this answer
    
Is it possible to add backward distances (points) (a->b - direct, b->a backward distances) to find optimal path (just moving a mind from two dimension field)? What do you think about? –  igor Apr 13 '11 at 13:03
    
Not really sure what you mean to be honest. There are definitely a lot of ways to do this and the way I said is just what I thought of offhand. –  Dukes Apr 15 '11 at 4:18

I did a project on TSP many years ago where I compared four different algorithms' performance over numerous datasets (in Java).

The algorithms I used were:

- Ordinary Hill Climber (HC)
- Random Restart Hill Climber (RRHC)
- Random Mutation Hill Climber (RMHC)
- Simulated Annealing (SA)

My results showed that RMHC performed better than both RRHC and HC; however, SA performed the best overall, providing slightly more precise results than the other three.

All of my tests were run over 100, 1,000, 10,000, 100,000 and 1,000,000 iterations and each and every time SA came out on top.

I hope this helps.

share|improve this answer
    
thanks, SnookerFan –  igor May 22 '13 at 6:58

A simple genetic algorithm with an integer encoding would by far be the fastest. The speed at which it will find the optimal or a "good enough" solution will depend a lot on the parameters chosen for selection, crossover and mutation rate.

share|improve this answer
1  
It sounds like @igor is looking for exact algorithms, and as I understand it, genetic algorithms for the TSP are heuristics that work via randomized improvement. Also, how do you justify that a genetic algorithm will be the fastest? –  Zach Langley Apr 12 '11 at 0:41
    
@Zach Langley, @Dukes No problem, agree, no one algorithm can resolve this problem in controled, predictable time. Can I use genetic algorithm to ASYMMETRIC TSP? How should I input A -> B and B' -> A' data (they have different distances) to calculate by using this algorithm? –  igor Apr 12 '11 at 5:50

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.