[pgrouting-dev] Is there Traveling sales man problem that uses a non euclidean solution

[Daniel Kastl]

On Sun, May 19, 2013 at 5:28 PM, Dave Potts <dave.potts at pinan.co.uk> wrote:

> Hi,
>
> Are there any plans to implement a version of the traveling salesman
> problem that would use a non euclidean solution and perhaps include a cost
> factor?
>
> My network is navigated in terms of a cost function for getting between
> two different nodes, which givens a 'distance' calculation between two
> different nodes the cost of the journey between A->B and B->A may be
> different.
>
> Is anybody aware of any work that may have been done in implementing such
> a solution in pgroute software?  From my understanding the current version
> of traveling salesman only works in term of euclidean distance which is
> measured from an direct calculation of the physical location.  Such that
> the cost of A->B is the same as B->A
>

Hi Dave,

Best would be to pass a distance matrix as parameter of TSP.
Then the calculation of the distances would be more flexible: euclidean
distance for example, if it should be fast. Or someone could already have a
distance matrix stored as a different able.

But this hasn't been implemented.
Steve and I talked about it already though.

Daniel




-- 
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/20130519/4266a046/attachment.html>