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

[Jay Mahadeokar]

Hi,

On Sat, Sep 17, 2011 at 11:20 PM, 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.
>
> 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 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
>
>


-- 
Regards,
-Jay Mahadeokar
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20110917/ab6c2534/attachment.html