[pgrouting-dev] Problems with TSP

[Stephen Woodbridge]

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
>