[pgrouting-dev] Possible design flaw in TSP general methods

[Stephen Woodbridge]

On 8/6/2013 5:17 PM, Dave Potts wrote:
> If I have a distance matrix which looks like
>
>
> 0 4 9999 1
> 4 0 2       3
> 9999 2 0 2
> 1 3 2 0
>
> The idea being that the only cheap route from 3-4 is to  3-4 and then
> 4-3 to get back, but if naviating a path for the entire tsp, it never
> calls back on it self, so it would assume that the entire problem can be
> solved in 4 hops, when the best possible route will be in 5 hops.
> Starting at 1
>
> For example 1-> 2 2->3 3->4 4->3 3->1,  total 11 Total 5 interconnecting
> nodes
>
> 1->4 4->3 3->1   total 9999+3+3   total 10005        Total 4
> interconnecting nodes, but rather more expensive
>
>
>
> Does anybody know of a tsp method that can resolve something like this
> and what its called?  I am looking for a tsp that does not mind double
> back on itself.

This is called TSPM or TSP "Multiple Visits" if you google it. I have 
seen a reference to being able to convert this problem into a standard 
TSP problem similar to the ATSP to TSP solution.

-Steve