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

[Daniel Kastl]

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 at 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 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.
> > 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 at georepublic.de
> > Web: http://georepublic.de
> >
> > _______________________________________________
> > pgrouting-dev mailing list
> > pgrouting-dev at lists.osgeo.org
> > http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
> >
> >
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>



-- 
Georepublic UG & Georepublic Japan
eMail: daniel.kastl at georepublic.de
Web: http://georepublic.de
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20110920/9121f3c6/attachment.html