[pgrouting-dev] Do we need a new and better TSP?
woodbri at swoodbridge.com
Sat Sep 17 14:51:25 EDT 2011
On 9/17/2011 2:02 PM, Jay Mahadeokar wrote:
> On Sat, Sep 17, 2011 at 11:20 PM, Daniel Kastl <daniel at georepublic.de
> <mailto:daniel at georepublic.de>> wrote:
> Hi list,
> On Friday at FOSS4G in Denver I discussed with Steve about TSP, and
> I want to share a bit of what we came up with:
> * According to Steve there is a way to solve TSP without GA
> (Genetic Algorithm), and that way we could get rid off GAUL
> dependency and make it a "core" function.
> I believe TSP is a NP Complete problem. So a polynomial time solution
> does not exist. Steve, can you elaborate what heuristic might be used
> besides GA?
This is a great question. You are correct the TSP is a NP Complete
problem, but this is more an academic issue than a real world issue. For
most use cases, I think a potential user would rather have an optimized
solution in "web" time than an optimum solution in days, years, or life
times depending on the number of points.
I did some research a few years ago into alternate faster solution and
have an implementation of Simulated Annealing TSP:
This does a good job but it will give different results for the same
input matrix if you change the row order. What I like about this
solution is that it can handle a large number of points (10's-100's)
very quickly and give reasonable results.
It also looks like there are a few algorithms with code on the link
above that might be candidates. At any rate, I have code that I used here:
For a fast demo just copy and past the list of cities into the textbox
and click solve. This little demo works by, computing the lat-lon for a
city in the US, and then populating the distance matrix with the
straight line distance between the points, and passing that to the TSP
The code I'm using for this demo is based on code I found in 2001-2002
and at the time I was pretty careful about picking up code that was in
the public domain only. That said, I'm not sure what the licensing is or
if we can even still contact the original authors. The is not that large
or complex that we could not re-implement a clean version directly into
pgRouting to remove the dependency on GAUL library.
Simulated Annealing is a very cool algorithm that has MANY uses beyond
just doing TSP.
+1 and getting ride of GAUL and CGAL dependencies.
> * Instead of calculation of a distance matrix within the TSP
> function, the distance matrix could be passed as a "SELECT".
> Then the user could decide the way distances should be
> calculated. And APSP would be a nice way to calculate a distance
> matrix for example.
> +1 for use of APSP!
> Any other ideas how to improve the current implementation of TSP?
> Do you have some other use cases with specific requirements?
> Georepublic UG & Georepublic Japan
> eMail: daniel.kastl at georepublic.de <mailto:daniel.kastl at georepublic.de>
> Web: http://georepublic.de <http://georepublic.de/>
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org <mailto:pgrouting-dev at lists.osgeo.org>
> -Jay Mahadeokar
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
More information about the pgrouting-dev