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

[Dave Potts]

On 06/08/13 23:20, Stephen Woodbridge wrote:
> 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
Thanks Steve, if wonder if such a thing as Multiple Visits asymmetric 
travelling salesman problem solution exists

Dave.
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev