[pgrouting-dev] Do we need a new and better TSP?

[Stephen Woodbridge]

Hi Jay,

On 9/17/2011 2:02 PM, Jay Mahadeokar wrote:
> Hi,
>
> 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:

   http://www.google.com/#q=synthetic+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:

   http://imaptools.com/cgi-bin/tsp.cgi

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 
solver.

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.

-Steve

>
>       * 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?
>
>     Daniel
>
>
>
>     --
>     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>
>     http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
>
>
>
> --
> Regards,
> -Jay Mahadeokar
>
>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev