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

[Stephen Woodbridge]

On 8/6/2013 5:35 PM, Dave Potts wrote:
> 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

I spent a couple of evenings googling for TSP papers of various flavors 
and have whole directory of pdf files on these.

google: TSPM "multiple visits"

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