[pgrouting-dev] Problems with TSP

[Dave Potts]

On 25/06/13 00:57, Stephen Woodbridge wrote:
Attempting a solution to the ASP using the current method with an array 
hack seems somewhat easier that converting this program to the modern 
world http://www.netlib.org/toms/750(Solution to asp in Fortran!!!!!)

Dave.
> On 6/24/2013 6:27 PM, Dave Potts wrote:
>> On 24/06/13 23:30, Stephen Woodbridge wrote:
>>
>> Thank you for your comments on the TSP.
>>
>> 1. Please find attach an sql hacking for running the matrix tsp from a
>> request, it works with the quote example, which is based on the one from
>> the tsp page.
>
> Thanks, I will look this over. I think that Daniel and I have come to 
> the idea that we want snippets and user tips, tricks and hacks put in 
> gists or maybe a contrib library or some place other than the core 
> product to make the code more lean and mean and easier to maintain. 
> And over time if there are things that we or the larger community feel 
> are critical to be supported in the core that we will then look at 
> adding them. We just went through the painful process of shedding a 
> lot of cruft from the product.
>
>> 2. Is there any way of saying in the TSP that there is not a link
>> between two nodes? Because if there is, there is method on the listed on
>> http://en.wikipedia.org/wiki/Traveling_salesman_problem#Asymmetric_TSP
>> for turning a Asmmetric problem in to a normal TSP problem by just
>> increasing the size of the matrix!  But you need a way of saying a link
>> is impossible!
>>
>> I have already tried the value of -1 but that got thrown out as an 
>> error.
>
> The wikipedia page is using -infinity to say the at A === A', it 
> should work with using zero instead in our code.
>
> At the moment, the algorithm seems to be very fragile (ie: fails) 
> about putting in a cost like infinity or a very large number to mean 
> that you can not follow that link. But you can try to put in a number 
> large for this, if it has problems it will respond with the find 
> eulerian path error.
>
>> 3. There is a spelling mistake on the
>> http://docs.pgrouting.org/dev/src/tsp/doc/index.html page, 'containig'
>
> Checked in. thanks.
>
>> If your still on hoilday, please enjoy the rest of it.
>
> I'm back, now trying to dig out of the backlog of email and phone 
> messages.
>
> Thanks,
>   -Steve
>
>> regards
>>
>>
>> Dave
>> <http://en.wikipedia.org/wiki/Traveling_salesman_problem#Asymmetric_TSP>
>>> On 6/23/2013 5:19 AM, Dave Potts wrote:
>>>> Just looked at the write up for the tsp, ok the answer will be in the
>>>> range 0-(X-1) where X is the number of points provided, the returned
>>>> index starts of at zero in set as one as found in postgres arrays.  
>>>> But
>>>> I do not understand the remark id, 'index into the matrix' the matrix
>>>> is a two dimension so I I don't understand how the index is 
>>>> desgined to
>>>> work!
>>>
>>> Since the the matrix is symmetric NxN, index refers to a row or
>>> column, so the resultant path would be for you first example below
>>> would be:
>>>
>>> 0,2: 20
>>> 1,3:  2
>>> 2,1: 90
>>> 3,0: 42
>>>
>>> or a path from 2 -> 3 -> 1 -> 0 for a cost of (20+2+90+42) = 154
>>>
>>>> On 23/06/13 10:04, Dave Potts wrote:
>>>>> I having some problems with the tsp
>>>>>
>>>>> I have a matrix {{0,31,22,42},{31,0,90,2},{22,90,0,27},{42,2,27,0}},
>>>>> starting at node 2,  I get the answer
>>>>> seq | id
>>>>> -----+----
>>>>>    0 |  2
>>>>>    1 |  3
>>>>>    2 |  1
>>>>>    3 |  0
>>>>> (4 rows)
>>>>> using the matrix
>>>
>>> So as you figured out, 4 is invalid, and probably should throw an
>>> error (write a ticket for this) as the nodes are 0-3.
>>>
>>> -Steve
>>>
>>>>>  {{0,22,42,31},{22,0,27,90},{42,27,0,2},{31,90,2,0}} starting at node
>>>>> 4  I get the answer
>>>>> seq | id
>>>>> -----+----
>>>>>    0 |  0
>>>>>    1 |  1
>>>>>    2 |  2
>>>>>    3 |  3
>>>>> The matrix is topological identicial, I start off at the same
>>>>> topological node, so I was expecting the same answer, also I was
>>>>> expecting all nodes to be in the result set ie nodes 1,2,3 and 4, for
>>>>> some strange reason I get 0.
>>>>>
>>>>> Is there some mistake in my data?
>>>>>
>>>>> regards
>>>>>
>>>>>
>>>>> 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
>>>>
>>>
>>> _______________________________________________
>>> pgrouting-dev mailing list
>>> pgrouting-dev at lists.osgeo.org
>>> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>>