[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
Fri Jun 14 06:07:03 PDT 2013
Hi Dave,
I'm not totally opposed to this, but I would like to discuss how you
plan to structure the data and what your query would look like.
There is another possibility that I like better and that would be to
write stored procedure that takes you sql query and returns a matrix.
matrix[][] pgr_matrix(sql text)
Then you can do something like:
select * from pgr_tsp(pgr_matrix('select * from matrix_table'), 27);
This is like to be reusable elsewhere as a utility.
-Steve
On 6/14/2013 1:38 AM, Daniel Kastl wrote:
> Hi Dave,
>
> Somehow we already discussed this in May:
> http://pgrouting.974090.n3.nabble.com/pgrouting-dev-New-TSP-API-td4025094.html
>
> I think the current function pgr_tsp function is good as it is, but some
> alternative with SQL query is a good idea.
> Then there would be two ways how to call TSP, for example
>
> pgr_tsp(matrix float[][], start integer)
> pgr_tsp(sql text, start integer)
>
> But instead of rewriting it's better to write a wrapper function that
> accepts SQL and transforms it into the matrix (and ensures that the
> matrix is valid).
>
> Daniel
>
>
>
>
>
>
> On Fri, Jun 14, 2013 at 2:17 PM, Dave Potts <dave.potts at pinan.co.uk
> <mailto:dave.potts at pinan.co.uk>> wrote:
>
> On 14/06/13 02:59, Daniel Kastl wrote:
> Hi Daniel, List
>
> I must admit I found the entire process of creating a postgress
> array in a suitable form for the pgr_tsp function to be a exercise
> in slow torture!
>
> Would anybody have any major objections if I attempted to rewrite
> the interface so it took a normal sql querry?
>
> Something like
>
> pgr_costResult[]pgr_tsp('SELECT source,target distance FROM vertex_table',2);
>
> That way the problem with creating a square array in postgres would disappear.
>
> Dave
>
>
>
> <https://www.google.nl/search?client=ubuntu&hs=uQi&channel=fs&gl=uk&q=exercise+in+slow+torture&spell=1&sa=X&ei=BKa6UYnAF5G20QXc_4HQCg&ved=0CCcQvwUoAA>
>> Hi Dave,
>>
>> Thanks for reporting. Maybe I just mixed up something with copy &
>> paste.
>> I remember that I needed to add a vertex table to the sample data
>> for the new TSP with distance matrix and got the ID's a bit wrong
>> first.
>> Will take a look.
>>
>> Daniel
>>
>>
>> On Fri, Jun 14, 2013 at 7:40 AM, Stephen Woodbridge
>> <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.com>> wrote:
>>
>> 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
>> <mailto: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
>> <mailto:postgis-devel at lists.osgeo.org>
>> http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-devel
>> _______________________________________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org
>> <mailto:pgrouting-dev at lists.osgeo.org>
>> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>>
>>
>>
>>
>> --
>> Georepublic UG & Georepublic Japan
>> eMail: daniel.kastl at georepublic.de
>> <mailto:daniel.kastl at georepublic.de>
>> Web: http://georepublic.de <http://georepublic.de/>
>>
>>
>> _______________________________________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org <mailto:pgrouting-dev at lists.osgeo.org>
>> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org <mailto:pgrouting-dev at lists.osgeo.org>
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
>
>
>
> --
> Georepublic UG & Georepublic Japan
> eMail: daniel.kastl at georepublic.de <mailto:daniel.kastl at georepublic.de>
> Web: http://georepublic.de <http://georepublic.de/>
>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
More information about the pgrouting-dev
mailing list