[pgrouting-dev] Having problems under standing the distance matrix of TSP in respect to route network pgroute version 2

Stephen Woodbridge woodbri at swoodbridge.com
Thu Jun 13 15:40:47 PDT 2013


Dave - moving this over to the pgrouting list.

Hi Dave,

I'm not sure the Daniel used the example data network for this example. 
The data looks like one of the matrix I used in my test cases.

src/tsp/test/*.test

I just made up numbers for a symmetric matrix. It was not taken from an 
actual network.

So the sly part is that its NOT from a graph ;)

Daniel - please correct me it you did something else.

-Steve

On 6/13/2013 6:11 PM, Dave Potts wrote:
>
> In the travel sales person problem an example is provided,  I having
> problems understanding it
>
> The example route network is posted as
> http://docs.pgrouting.org/dev/doc/src/developer/sampledata.html#sampledata
>
> I have assume the distance between red node 1 and red node 3 is 2, ie
> the unit distance 1 +1  which I  make to be 2
>
> given that
>
> I think the route matrix should be
>
>      1 2 3 4
> ======
> 1 | 0 1 2 3
> 2 | 1 0 1 2
> 3 | 2 1 0 1
> 4 | 3 2 1 0
>
> distance 1 to 4 is 1+1 +1 ==3
> distance 2 to 4 is 1+1       ==2
> distance 3 to 4 is 1
> etc
>
> But the give value is (please see
> http://docs.pgrouting.org/dev/src/tsp/doc/index.html)
>      1 2 3 4
>
> 1  {0,1,2,3},
> 2  {1,0,3,2},
> 3  {2,3,0,4},
> 4  {3,2,4,0}
>
> I just don't understand how the distance between 3 and 4 can be the
> value 4, ditto he values between 2 and 3
>
> Have I missed something sly ?
>
> Dave.
>
>
>
> _______________________________________________
> postgis-devel mailing list
> postgis-devel at lists.osgeo.org
> http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-devel

_______________________________________________
postgis-devel mailing list
postgis-devel at lists.osgeo.org
http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-devel


More information about the pgrouting-dev mailing list