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

[Stephen Woodbridge]

On 5/19/2013 4:28 AM, Dave Potts 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

Dave,

My plan has been to write another API that will allow you to pass a 
distance matrix to the solver and it will return the ordered indexes to 
the matrix. I'll see if I can pick up the pace on that.

Initially, I my goal was to just get rid of the GAUL dependancy and it 
was fairly easy to just slide the new code into the existing api 
transparently for the most part.

-Steve