alternative TSP solvers

perrygeo / optimal_tour

Find the shortest tour visiting all GeoJSON points using concorde and mapbox APIs

21 stars 2 forks source link

alternative TSP solvers #8

Closed perrygeo closed 8 years ago

perrygeo commented 8 years ago

concorde is the gold standard, basically all of the significant mathematical breakthroughs in TSP research are encapsulated in this program. It's the best but the license is restrictive, it needs a closed-source LP solver, the public code is not actively maintained and the current mechanism of calling out to a subprocess is clunky.

[ ] look for other TSP solvers with reasonable python interfaces
[ ] evaluate for speed, quality, etc
[ ] abstract tsp solver and make it configurable

perrygeo commented 8 years ago

Concorde also ships with code to "solve" TSPs using the Lin–Kernighan heuristic.

mourner commented 8 years ago

Per chat, I suggest switching to LKH:

state of the art (on par with Concorde) and holding records for many TSP challenges, including world record for 2 million point TSP
super easy to install and use — download, make and it's ready (no need for external solvers etc.)
full source code available (not open source but still)
last version released in Nov 2012 (as opposed to Concorde who's public version is from 2003)
it's very fast

perrygeo commented 8 years ago

:+1:

LKH looks great. I'll spend some time looking into writing a python wrapper for it.

I'll likely take the short-cut of wrapping the CLI as I did in pyconcorde - building the interface first, then swapping out the implementation if/when we get around to building python bindings to the C lib.

perrygeo commented 8 years ago

Some quick notes on my initial testing with LK solvers

Using the particularly challenging u2152 problem from TSPLIB, LKH can do a single run in 40 seconds and usually gets within 0.5% of the optimal. Concorde, OTOH, can solve for the optimal tour but it takes 40 minutes. LKH thus provides a more pragmatic solution for most use cases where we want a near-optimal result but quickly.
LKH can solve the asymmetrical case of the TSP which is important since travel times are not always symmetrical! Concorde does not even attempt to solve them, forcing you to convert to a symmetrical case.
I tried the David Neto's GPL'd implemetation, lk but was not able to get it to compile. gcc was throwing warnings all over the place and it's not particularly well-written C code. Maybe useful for studying the algorithm, not too useful as an implementation.

perrygeo commented 8 years ago

I've renamed pyconcorde to pytsp and added optional support for LKH and potentially other solvers. This allows optimal_tour to use one interface and the details of the implementation can be handled in pytsp

feeLs27 commented 6 years ago

Is it possible to install pytsp for window 10?