10
$\begingroup$

Are Metaheuristics and Evolutionary Algorithms the "Gold Standard" for the Traveling Salesman Problem?

I am interested in learning more about how we have been able to solve the (famous) Traveling Salesman Problem for more and more cities as new developments in Combinatorial Optimization occurred over the years.

Does anyone know which algorithms are considered to be the more "successful" algorithms for solving the Traveling Salesman Problem in modern times?

Based on what I have been reading, it seems that Metaheuristics and Evolutionary Algorithms (e.g. Genetic Algorithm) seem to showing great results in versions of the Traveling Salesman Problems where the number of cities are large - but are there any other types of algorithms that are considered to be successful in modern times for "solving" the Traveling Salesman Problem?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ In my experience, for TSP and VRP variants, Late Acceptence (LAHC) works well, with other Local Search (such as Tabu Search) doing well too. However, Genetic Algortihms are consistently inferior for these kind of problems, in the benchmarks I've run and the academic competitions I've seen. They do have a cool name though! $\endgroup$
    – Geoffrey De Smet
    Jan 24, 2022 at 7:50
  • $\begingroup$ Note that there are different definitions of the word "metaheuristics". You seem to use it as "metaphore-based algorithm". If you define it as "general concept behind a heuristc", i.e. the literal meaning, then metaheuristics are a relevant approach for most optimization problems, including the TSP, when the goal is to get good solutions on instances that exact algorithms can't solve within the considered time limit. $\endgroup$
    – fontanf
    Jan 24, 2022 at 12:34
  • $\begingroup$ Also note that there might be different goals in optimization: proving the optimality, finding good solutions quickly, finding near optimal solutions with long runs... it's not common to have one approach, one "gold standard", that would be the best for all these cases $\endgroup$
    – fontanf
    Jan 24, 2022 at 12:37

3 Answers 3

Reset to default
22
$\begingroup$

The answer to the question is: No. (Although one can debate what exactly is a "metaheuristic")

The "gold standard" for finding high quality feasible solutions for the TSP is the LKH (Lin-Kernighan-Helsgaun) heuristic described in this paper:

K. Helsgaun (2000). "An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic". European Journal of Operational Research. 126 (1): 106–130.

It is a way to implement the Lin-Kernighan heuristic which is probably best described as a local improvement heuristic where "local" is dynamically increased and adapted.

The talk by Bill Cook linked above is a great overview for the TSP and his software to solve TSPs called Concorde: "The Traveling Salesman Problem: Postcards from the Edge of Impossibility" (https://youtu.be/5VjphFYQKj8). It also demonstrates that huge TSPs can be solved to proven optimality and even for very large problem instances we can nowadays find very, very good solutions.

Just because we can't solve TSPs by brute force does not mean we can't solve TSPs at all. It depends a little on what you mean by "solve", but Concorde can both find very good solutions very fast and prove optimality for amazingly large and practical data sets.

To find solutions, Concorde uses the LKH heuristic and probably a collection of other heuristics some of which probably classify as metaheuristics or evolutionary. See the Concorde website for details on that: https://www.math.uwaterloo.ca/tsp/index.html .

To prove optimality, Concorde uses Linear Programming relaxations, cutting planes and branch-and-bound. That is the best approach to prove optimality for TSPs at the moment.

Improve this answer
$\endgroup$
5
  • $\begingroup$ @ phillipp Christophel: thank you so much for your answer! Just to clarify: would the LKH algorithm be considered an example of a "gradient free method"? Thanks! $\endgroup$
    – stats_noob
    Jan 24, 2022 at 18:28
  • $\begingroup$ Well, it does not use gradients so you could call it that, but to my understanding "gradient free" is typically used to describe genetic algorithms and similar methods to separate them from derivative based search approaches. I see it this way: LKH is a form of problem specific local search with diversification. Genetic algorithms have two typical properties: A population and competition within that population. LKH does not have that, so its not a genetic algorithm. $\endgroup$
    – Philipp Christophel
    Jan 25, 2022 at 9:10
  • $\begingroup$ A good book on the topic of heuristics in my opinion is: "How to Solve It: Modern Heuristics" by Zbigniew Michalewicz and David B. Fogel (link.springer.com/book/10.1007/978-3-662-07807-5). Its not up to date in all areas (i.e. neural networks) but still a good read. $\endgroup$
    – Philipp Christophel
    Jan 25, 2022 at 9:14
  • $\begingroup$ Very good answer. I'd just add somewhere a definition of Concorde (or just an "(aka Concord)") as you start to use that term at some point without a clear indication on what it is refering to. (well, you do point to a site on the next paragraph... I didn't notice at first watch) $\endgroup$
    – Olivier Dulac
    Jan 25, 2022 at 9:49
  • 1
    $\begingroup$ @OlivierDulac Thanks for the comment, I fixed that. $\endgroup$
    – Philipp Christophel
    Jan 25, 2022 at 13:36
7
$\begingroup$

Take a look at the Concorde https://www.math.uwaterloo.ca/tsp/concorde.html.

If it's a TSP problem, not a variant, Concorde can solve it and it is a beast.

When you say "versions of the Travelling Salesman Problems where the number of cities are large", around what value are you refering to with "large"?

Improve this answer
$\endgroup$
5
  • $\begingroup$ @ Juan Pablo Mesa : Thank you so much for your answer! I guess more than a thousand cities (e.g. I have heard that after 9 cities, it is almost impossible for a computer to solve the travelling salesman problem using brute force). Do you have any more information about Concorde? What kind of algorithms is Concorde using to explore the optimal path? Thank you so much! $\endgroup$
    – stats_noob
    Jan 24, 2022 at 7:19
  • 2
    $\begingroup$ Although the presentation is some ten years old and not very technical, I think Bill Cook's presentation called "The Traveling Salesman Problem: Postcards from the Edge of Impossibility" is quite informative. You can find it here youtu.be/5VjphFYQKj8 $\endgroup$
    – Sune
    Jan 24, 2022 at 8:35
  • 9
    $\begingroup$ Concorde can solve problems with 1000+ nodes. Remember that although a computer can't solve TSP by brute force (i.e., complete enumeration) if it has more than a few nodes, there are still exact algorithms that can solve much larger instances to provable optimality (or within a tolerance). That is, just because we can't solve something by enumeration doesn't mean we need heuristics necessarily. $\endgroup$
    – LarrySnyder610
    Jan 24, 2022 at 15:06
  • $\begingroup$ as @philipp-christophel said in his answer, Concorde uses the Lin-Kernighan-Helsgaun heuristic to solve the problem, and then proves optimality with LP relaxations. Also, as Larry said, Concorde can easily handle problems with more than 1000 nodes. In the -benchmarks- section of the Concorde's website, the results for problems with up to 85000 cities are shown. You can also take a look at how much time it takes to solve problems with different instance sizes (although bigger size isn't always larger in computing time) $\endgroup$
    – Juan Pablo Mesa
    Jan 24, 2022 at 16:23
  • $\begingroup$ Thank you everyone so much for your answers and replies! Just to clarify: would the LKH algorithm be considered an example of a "gradient free method"? Thanks again! $\endgroup$
    – stats_noob
    Jan 24, 2022 at 18:26
4
$\begingroup$

There's been a brilliant development in the Traveling Salesman problem recently leveraging neuromorphic computing. Essentially, neuromorphic chips contain a massive array of (often) physical neurons with dense local connections and some routing circuitry to transmit information to other arrays. In essence, each node or "city" is represented by a neuron and the strength of the synaptic connections between them represent distances. Current is injected into the "departure" neuron and its firing activity activates adjacent neurons at a rate according to those connection strengths. This continues until the "destination" neuron fires once, then synaptic activity can be traced backwards to reveal the path of least resistance.

The brilliance of this solution comes from the fact that every path in the net can be checked simultaneously, and the way neurons communicate using sparse spiking is extremely power efficient. I can't remember the exact number sbut I believe Intel's Loihi 1 chip achieved solutions with 1000x less power and 10x reduced latency over GPU solutions. With Loihi 2 which was recently released to research communities, this efficiency likely increased a further 5-fold. Just imagine, with a human-brain sized network we could check 100 billion routes between 100 million cities in far less than a second with the energy cost of a potato chip!

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Despite this efficiency, it's essentially still a brute force approach. $\endgroup$
    – ChengDuum
    Jan 24, 2022 at 19:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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