New answers tagged

4

Some additional sources to help you answer your question: Cook, W. "In pursuit of the traveling salesman: mathematics at the limits of computation. 2012." Gutin, Gregory, and Abraham P. Punnen, eds. The traveling salesman problem and its variations. Vol. 12. Springer Science & Business Media, 2006.


8

I doubt there is a complete listing of every possible approach to TSPs. You can find a significant amount of information on Bill Cook's site. Bill Cook wrote what I believe many consider the definitive book about TSPs ("In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation", Princeton University Press, 2012) and is one of ...


6

There are some proofs of the contrary: whatever the starting point, your local search can be stuck in solutions far away from the optimum. Here "local" means that each iteration must be done in polynomial time. Check the seminal paper "On the Complexity of Local Search for the Traveling Salesman Problem" by Papadimitriou and Steiglitz on ...


3

I am not aware of such proof. I think your question may be meaningful given a specific improvement heuristic. For example, I worked on solving large scale VRP problems using genetic algorithms as the meta-heuristic and doing local search to improve solutions. In this case, randomly generated initial solutions performed much better for me than using well-...


1

There is a mathematically justified way of saying is better than the other. The expected time to solve over all problems. When the expected value can't be computed over the distribution of problems you care about you can sample that space and run both approaches for both. This is called benchmarking and with sufficient samples the benchmark numbers will ...


Top 50 recent answers are included