2
$\begingroup$

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.

$\endgroup$
1

3 Answers 3

Reset to default
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ The Wikipedia also tells about the Cutting-plane method, Christofides algorithm and V-opt heuristic. How do they compare with the methods you listed above? $\endgroup$
    – skan
    Commented Apr 27, 2017 at 15:25
1
$\begingroup$

@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

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – igor
    Commented Apr 13, 2011 at 13:03
  • $\begingroup$ 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. $\endgroup$
    – Dukes
    Commented Apr 15, 2011 at 4:18
0
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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? $\endgroup$
    – Zach Langley
    Commented Apr 12, 2011 at 0:41
  • $\begingroup$ @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? $\endgroup$
    – igor
    Commented Apr 12, 2011 at 5:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .