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

dkastl · September 17, 2011, 5:50pm

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.
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.
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@georepublic.de
Web: http://georepublic.de

Jay_Mahadeokar · September 17, 2011, 6:02pm

Hi,

On Sat, Sep 17, 2011 at 11:20 PM, Daniel Kastl <daniel@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?

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@georepublic.de
Web: http://georepublic.de

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Regards,
-Jay Mahadeokar

Stephen_Woodbridge1 · September 17, 2011, 6:51pm

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@georepublic.de
<mailto:daniel@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@georepublic.de <mailto:daniel.kastl@georepublic.de>
    Web: http://georepublic.de/>

    _______________________________________________
    pgrouting-dev mailing list
    pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
    http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

--
Regards,
-Jay Mahadeokar

_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

dkastl · September 17, 2011, 9:19pm

+1 and getting ride of GAUL and CGAL dependencies.

Hey, Steve. Today I was half listening to the PostGIS developer meeting at the code sprint. And they discussed about dependency to CGAL or not

Daniel

–
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
Web: http://georepublic.de

Mario_Basa · September 19, 2011, 2:30pm

Daniel,

I am trying to understand this: the mutation computation will be done
in SQL? Wouldn't that be expensive?

For me, implementing the GA specifically for pgRouting will be the
best way to remove GAUL dependency. No idea how complex that will be
though.

Mario.

On Sun, Sep 18, 2011 at 2:50 AM, Daniel Kastl <daniel@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.
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.

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@georepublic.de
Web: http://georepublic.de

_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

dkastl · September 20, 2011, 5:23am

Hi Mario,

I think Anton knows how it is done at the moment and Steve seems to know how to do it better

I guess that there are many TSP solvers available or recipes how to implement your own. It’s kind of popular topic, I think.

One important point for me is, that a new TSP function should allow to pass a distance matrix, because the current one takes the linear distance. IMO the user should be able to decide how to calculate distances, and with Jay’s APSP (all-pair-shortest-path) there is now a way to compute a “real distance” matrix much more efficient than before.

Daniel

On Mon, Sep 19, 2011 at 11:30 PM, Mario Basa <mario.basa@gmail.com> wrote:

Daniel,

I am trying to understand this: the mutation computation will be done
in SQL? Wouldn’t that be expensive?

For me, implementing the GA specifically for pgRouting will be the
best way to remove GAUL dependency. No idea how complex that will be
though.

Mario.

On Sun, Sep 18, 2011 at 2:50 AM, Daniel Kastl <daniel@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.
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.

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@georepublic.de
Web: http://georepublic.de

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
Web: http://georepublic.de