[pgrouting-dev] Building some tools to work with TSP

pgRouting pgrouting-dev
1

Hi all,

I have been playing with some tools to allow me to integrate TSP optimization into a web application. I thought I would share what I have come up with for comments. One of the things I did was to try and break down the process into reusable modular functions. For example there are two functions to compute the distance matrix based on either Euclidean or kdijkstra distances. One could add other functions to compute them based on other algorithms. Also each function does one conversion so it is simple to understand and easy to test or replace with another function that does the transformation in a different way. Then the final function glues all the pieces together to get the final result.

Goal:

take a string or points like "x,y;x,y;x,y;..." and compute the TSP solution to order the points based on either Euclidean distance or network distances, then compute the route through the network and return the route geometry.

Solution in progress:

1. text to point geometry *
    pgr_texttopoints(pnts text, srid integer DEFAULT(4326))

2. points to vertex ids *
    pgr_pointtoedgenode(edges text, pnt geometry, tol float8)
    pgr_pointstovids(pnts geometry, edges text, tol float8 DEFAULT(0.01))

3. points to edge ids **

4. points to [edge id, pct] **

5. points to Euclidean distance matrix *
    pgr_points2dmatrix(pnts geometry, OUT dmatrix double precision, OUT ids integer)

6. vertex ids to kdijkstra distance matrix *
    pgr_vidstodmatrix(IN vids integer, IN pnts geometry, IN edges text, tol float8 DEFAULT(0.1), OUT dmatrix double precision, OUT ids integer)

7. distance matrix to TSP to ordered list ***
select * from pgr_tsp(
     (select dmatrix::float8
        from pgr_vidstodmatrix(
                 pgr_pointstovids(
                     pgr_texttopoints('2,0;2,1;3,1;2,2;4,1;4,2;2,3;3,2', 0),
                     'edge_table'),
                 pgr_texttopoints('2,0;2,1;3,1;2,2;4,1;4,2;2,3;3,2', 0),
                 'edge_table')
     ),
     1
);

8. reorder vids based on ordered list *

9. compute trsp for pairs of vids in ordered list *,!
    pgr_trsp(sql text, vids integer, directed boolean, has_reverse_cost boolean, turn_restrict_sql text DEFAULT NULL::text)

    pgr_tsptrsp(pnts geometry, edges text, directed boolean, has_reverse_cost boolean, tol float8 DEFAULT(0.1), turn_restrict_sql text DEFAULT NULL::text)

    select * from pgr_tsptrsp(pgr_texttopoints('2,0;2,1;3,1;2,2;4,1;4,2;2,3;3,2', 0), 'edge_table', true, true);

10. output results **

NOTES:
* - done
** - not done
*** - already part of 2.0
! - computing a route through via points can be optimized in the C/C++ code for better performance, but I currently just prototyped this up in plpgsql

Thoughts,
   -Steve

2

Another common problem is orienting the returned edges so they match up end to end. For example:

   select st_astext(the_geom) from pgr_tsptrsp(pgr_texttopoints('2,0;2,1;3,1;2,2;4,1;4,2;2,3;3,2', 0), 'edge_table', true, true) a, edge_table b where a.id2=b.id;

"LINESTRING(2 1,2 2)"
"LINESTRING(2 2,3 2)"
"LINESTRING(3 2,4 2)"
"LINESTRING(4 1,4 2)" -- needs to be flipped
"LINESTRING(3 1,4 1)" -- needs to be flipped
"LINESTRING(2 1,3 1)" -- needs to be flipped
"LINESTRING(2 1,2 2)"
"LINESTRING(2 2,2 3)"
"LINESTRING(2 2,2 3)" -- needs to be flipped
"LINESTRING(2 1,2 2)" -- needs to be flipped
"LINESTRING(2 0,2 1)" -- needs to be flipped
"LINESTRING(2 0,2 1)"

So I wrote a new function pgr_flipedges(ga geometry) that can be used like this:

select st_astext(e) from (
   select unnest(pgr_flipedges(array_agg(the_geom))) as e
     from pgr_tsptrsp(pgr_texttopoints('2,0;2,1;3,1;2,2;4,1;4,2;2,3;3,2', 0), 'edge_table', true, true) a,
          edge_table b
    where a.id2=b.id
) as foo;

"LINESTRING(2 1,2 2)"
"LINESTRING(2 2,3 2)"
"LINESTRING(3 2,4 2)"
"LINESTRING(4 2,4 1)"
"LINESTRING(4 1,3 1)"
"LINESTRING(3 1,2 1)"
"LINESTRING(2 1,2 2)"
"LINESTRING(2 2,2 3)"
"LINESTRING(2 3,2 2)"
"LINESTRING(2 2,2 1)"
"LINESTRING(2 1,2 0)"
"LINESTRING(2 0,2 1)"

Notice how all the edges have been flipped to return a continuous path from start to end of each adjacent segment in the path.

-Steve
All the mentioned code will eventually get checked into pgrouting 2.1 development branch once it is stable and I have test cases and docs written for it.

-Steve

On 10/9/2013 10:29 AM, Stephen Woodbridge wrote:

Hi all,

I have been playing with some tools to allow me to integrate TSP
optimization into a web application. I thought I would share what I have
come up with for comments. One of the things I did was to try and break
down the process into reusable modular functions. For example there are
two functions to compute the distance matrix based on either Euclidean
or kdijkstra distances. One could add other functions to compute them
based on other algorithms. Also each function does one conversion so it
is simple to understand and easy to test or replace with another
function that does the transformation in a different way. Then the final
function glues all the pieces together to get the final result.

Goal:

take a string or points like "x,y;x,y;x,y;..." and compute the TSP
solution to order the points based on either Euclidean distance or
network distances, then compute the route through the network and return
the route geometry.

Solution in progress:

1. text to point geometry *
    pgr_texttopoints(pnts text, srid integer DEFAULT(4326))

2. points to vertex ids *
    pgr_pointtoedgenode(edges text, pnt geometry, tol float8)
    pgr_pointstovids(pnts geometry, edges text, tol float8 DEFAULT(0.01))

3. points to edge ids **

4. points to [edge id, pct] **

5. points to Euclidean distance matrix *
    pgr_points2dmatrix(pnts geometry, OUT dmatrix double precision,
OUT ids integer)

6. vertex ids to kdijkstra distance matrix *
    pgr_vidstodmatrix(IN vids integer, IN pnts geometry, IN edges
text, tol float8 DEFAULT(0.1), OUT dmatrix double precision, OUT ids
integer)

7. distance matrix to TSP to ordered list ***
select * from pgr_tsp(
     (select dmatrix::float8
        from pgr_vidstodmatrix(
                 pgr_pointstovids(
                     pgr_texttopoints('2,0;2,1;3,1;2,2;4,1;4,2;2,3;3,2',
0),
                     'edge_table'),
                 pgr_texttopoints('2,0;2,1;3,1;2,2;4,1;4,2;2,3;3,2', 0),
                 'edge_table')
     ),
     1
);

8. reorder vids based on ordered list *

9. compute trsp for pairs of vids in ordered list *,!
    pgr_trsp(sql text, vids integer, directed boolean,
has_reverse_cost boolean, turn_restrict_sql text DEFAULT NULL::text)

    pgr_tsptrsp(pnts geometry, edges text, directed boolean,
has_reverse_cost boolean, tol float8 DEFAULT(0.1), turn_restrict_sql
text DEFAULT NULL::text)

    select * from
pgr_tsptrsp(pgr_texttopoints('2,0;2,1;3,1;2,2;4,1;4,2;2,3;3,2', 0),
'edge_table', true, true);

10. output results **

NOTES:
* - done
** - not done
*** - already part of 2.0
! - computing a route through via points can be optimized in the C/C++
code for better performance, but I currently just prototyped this up in
plpgsql

Thoughts,
   -Steve
_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

3

Hi Steve,

select dmatrix::float8
from pgr_vidstodmatrix(
pgr_pointstovids(
pgr_texttopoints(‘-7.50501,40.26310;-7.48864,40.17530;-7.49901,40.13950;-7.57596,40.12350;-7.61591,40.13230;-7.61935,40.13230;-7.67235,40.13580;-7.67087,40.13660;-7.66510,40.13860;-7.74559,40.15640;-7.74588,40.15730;-7.74746,40.15690;-7.74922,40.15540;-7.74926,40.15310;-7.73537,40.14230;-7.63556,40.18920;-7.64849,40.22630;-7.62354,40.25680;-7.62425,40.26280;-7.62223,40.25830;-7.62179,40.25680;-7.62116,40.25580;-7.64803,40.22390;-7.63916,40.20560;-7.63664,40.20250;-7.63767,40.19970;-7.63623,40.20000;-7.56974,40.26710;-7.49104,40.26500;-7.50473,40.26320’, 4326),
‘ways’),
pgr_texttopoints(‘-7.50501,40.26310;-7.48864,40.17530;-7.49901,40.13950;-7.57596,40.12350;-7.61591,40.13230;-7.61935,40.13230;-7.67235,40.13580;-7.67087,40.13660;-7.66510,40.13860;-7.74559,40.15640;-7.74588,40.15730;-7.74746,40.15690;-7.74922,40.15540;-7.74926,40.15310;-7.73537,40.14230;-7.63556,40.18920;-7.64849,40.22630;-7.62354,40.25680;-7.62425,40.26280;-7.62223,40.25830;-7.62179,40.25680;-7.62116,40.25580;-7.64803,40.22390;-7.63916,40.20560;-7.63664,40.20250;-7.63767,40.19970;-7.63623,40.20000;-7.56974,40.26710;-7.49104,40.26500;-7.50473,40.26320’, 4326),
‘ways’)

While running the query above, I got the error below.

column “id” does not exist
LINE 1: select id, source, target, cost from ways where the_geom && …
^
QUERY: select id, source, target, cost from ways where the_geom && ‘0103000020E610000001000000050000002E34D769A4651FC05EBA490C020344402E34D769A4651FC0492EFF21FD2E444076ABE7A4F78D1DC0492EFF21FD2E444076ABE7A4F78D1DC05EBA490C020344402E34D769A4651FC05EBA490C02034440’::geometry
CONTEXT: PL/pgSQL function pgr_vidstodmatrix(integer,geometry,text,double precision) line 57 at FOR over EXECUTE statement

I guess it’s some kind of bug, which is something it may happen when we are testing something from the develop branch! :slight_smile:

Can you help me with this?

Thanks!

···

–
Helder Alves

+351912384076

On Wed, Oct 9, 2013 at 5:26 PM, Stephen Woodbridge <woodbri@swoodbridge.com> wrote:

Another common problem is orienting the returned edges so they match up end to end. For example:

select st_astext(the_geom) from pgr_tsptrsp(pgr_texttopoints(‘2,0;2,1;3,1;2,2;4,1;4,2;2,3;3,2’, 0), ‘edge_table’, true, true) a, edge_table b where a.id2=b.id;

“LINESTRING(2 1,2 2)”
“LINESTRING(2 2,3 2)”
“LINESTRING(3 2,4 2)”
“LINESTRING(4 1,4 2)” – needs to be flipped
“LINESTRING(3 1,4 1)” – needs to be flipped
“LINESTRING(2 1,3 1)” – needs to be flipped
“LINESTRING(2 1,2 2)”
“LINESTRING(2 2,2 3)”
“LINESTRING(2 2,2 3)” – needs to be flipped
“LINESTRING(2 1,2 2)” – needs to be flipped
“LINESTRING(2 0,2 1)” – needs to be flipped
“LINESTRING(2 0,2 1)”

So I wrote a new function pgr_flipedges(ga geometry) that can be used like this:

select st_astext(e) from (
select unnest(pgr_flipedges(array_agg(the_geom))) as e
from pgr_tsptrsp(pgr_texttopoints(‘2,0;2,1;3,1;2,2;4,1;4,2;2,3;3,2’, 0), ‘edge_table’, true, true) a,
edge_table b
where a.id2=b.id
) as foo;

“LINESTRING(2 1,2 2)”
“LINESTRING(2 2,3 2)”
“LINESTRING(3 2,4 2)”
“LINESTRING(4 2,4 1)”
“LINESTRING(4 1,3 1)”
“LINESTRING(3 1,2 1)”
“LINESTRING(2 1,2 2)”
“LINESTRING(2 2,2 3)”
“LINESTRING(2 3,2 2)”
“LINESTRING(2 2,2 1)”
“LINESTRING(2 1,2 0)”
“LINESTRING(2 0,2 1)”

Notice how all the edges have been flipped to return a continuous path from start to end of each adjacent segment in the path.

-Steve
All the mentioned code will eventually get checked into pgrouting 2.1 development branch once it is stable and I have test cases and docs written for it.

-Steve

On 10/9/2013 10:29 AM, Stephen Woodbridge wrote:

Hi all,

I have been playing with some tools to allow me to integrate TSP
optimization into a web application. I thought I would share what I have
come up with for comments. One of the things I did was to try and break
down the process into reusable modular functions. For example there are
two functions to compute the distance matrix based on either Euclidean
or kdijkstra distances. One could add other functions to compute them
based on other algorithms. Also each function does one conversion so it
is simple to understand and easy to test or replace with another
function that does the transformation in a different way. Then the final
function glues all the pieces together to get the final result.

Goal:

take a string or points like “x,y;x,y;x,y;…” and compute the TSP
solution to order the points based on either Euclidean distance or
network distances, then compute the route through the network and return
the route geometry.

Solution in progress:

  1. text to point geometry *
    pgr_texttopoints(pnts text, srid integer DEFAULT(4326))

  2. points to vertex ids *
    pgr_pointtoedgenode(edges text, pnt geometry, tol float8)
    pgr_pointstovids(pnts geometry, edges text, tol float8 DEFAULT(0.01))

  3. points to edge ids **

  4. points to [edge id, pct] **

  5. points to Euclidean distance matrix *
    pgr_points2dmatrix(pnts geometry, OUT dmatrix double precision,
    OUT ids integer)

  6. vertex ids to kdijkstra distance matrix *
    pgr_vidstodmatrix(IN vids integer, IN pnts geometry, IN edges
    text, tol float8 DEFAULT(0.1), OUT dmatrix double precision, OUT ids
    integer)

  7. distance matrix to TSP to ordered list ***
    select * from pgr_tsp(
    (select dmatrix::float8
    from pgr_vidstodmatrix(
    pgr_pointstovids(
    pgr_texttopoints(‘2,0;2,1;3,1;2,2;4,1;4,2;2,3;3,2’,
    0),
    ‘edge_table’),
    pgr_texttopoints(‘2,0;2,1;3,1;2,2;4,1;4,2;2,3;3,2’, 0),
    ‘edge_table’)
    ),
    1
    );

  8. reorder vids based on ordered list *

  9. compute trsp for pairs of vids in ordered list *,!
    pgr_trsp(sql text, vids integer, directed boolean,
    has_reverse_cost boolean, turn_restrict_sql text DEFAULT NULL::text)

pgr_tsptrsp(pnts geometry, edges text, directed boolean,
has_reverse_cost boolean, tol float8 DEFAULT(0.1), turn_restrict_sql
text DEFAULT NULL::text)

select * from
pgr_tsptrsp(pgr_texttopoints(‘2,0;2,1;3,1;2,2;4,1;4,2;2,3;3,2’, 0),
‘edge_table’, true, true);

  1. output results **

NOTES:

    • done
      ** - not done
      *** - already part of 2.0
      ! - computing a route through via points can be optimized in the C/C++
      code for better performance, but I currently just prototyped this up in
      plpgsql

Thoughts,
-Steve

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

4

You ways table does not have a column named "id" for now you might have to set up a view like:

create view v_ways as select your_id_col as id, source, target, cost from ways;

then try your query replacing 'ways' with 'v_ways'

-Steve

On 11/4/2013 11:31 AM, Helder Alves wrote:

Hi Steve,

    select dmatrix::float8
            from pgr_vidstodmatrix(
                     pgr_pointstovids(

    pgr_texttopoints('-7.50501,40.26310;-7.48864,40.17530;-7.49901,40.13950;-7.57596,40.12350;-7.61591,40.13230;-7.61935,40.13230;-7.67235,40.13580;-7.67087,40.13660;-7.66510,40.13860;-7.74559,40.15640;-7.74588,40.15730;-7.74746,40.15690;-7.74922,40.15540;-7.74926,40.15310;-7.73537,40.14230;-7.63556,40.18920;-7.64849,40.22630;-7.62354,40.25680;-7.62425,40.26280;-7.62223,40.25830;-7.62179,40.25680;-7.62116,40.25580;-7.64803,40.22390;-7.63916,40.20560;-7.63664,40.20250;-7.63767,40.19970;-7.63623,40.20000;-7.56974,40.26710;-7.49104,40.26500;-7.50473,40.26320',
    4326),
                         'ways'),

    pgr_texttopoints('-7.50501,40.26310;-7.48864,40.17530;-7.49901,40.13950;-7.57596,40.12350;-7.61591,40.13230;-7.61935,40.13230;-7.67235,40.13580;-7.67087,40.13660;-7.66510,40.13860;-7.74559,40.15640;-7.74588,40.15730;-7.74746,40.15690;-7.74922,40.15540;-7.74926,40.15310;-7.73537,40.14230;-7.63556,40.18920;-7.64849,40.22630;-7.62354,40.25680;-7.62425,40.26280;-7.62223,40.25830;-7.62179,40.25680;-7.62116,40.25580;-7.64803,40.22390;-7.63916,40.20560;-7.63664,40.20250;-7.63767,40.19970;-7.63623,40.20000;-7.56974,40.26710;-7.49104,40.26500;-7.50473,40.26320',
    4326),
                     'ways')

While running the query above, I got the error below.

    column "id" does not exist
    LINE 1: select id, source, target, cost from ways where the_geom && ...
                    ^
    QUERY: select id, source, target, cost from ways where the_geom &&
    '0103000020E610000001000000050000002E34D769A4651FC05EBA490C020344402E34D769A4651FC0492EFF21FD2E444076ABE7A4F78D1DC0492EFF21FD2E444076ABE7A4F78D1DC05EBA490C020344402E34D769A4651FC05EBA490C02034440'::geometry
    CONTEXT: PL/pgSQL function
    pgr_vidstodmatrix(integer,geometry,text,double precision) line
    57 at FOR over EXECUTE statement

I guess it's some kind of bug, which is something it may happen when we
are testing something from the develop branch! :slight_smile:

Can you help me with this?

Thanks!

--
Helder Alves
+351912384076

On Wed, Oct 9, 2013 at 5:26 PM, Stephen Woodbridge
<woodbri@swoodbridge.com <mailto:woodbri@swoodbridge.com>> wrote:

    Another common problem is orienting the returned edges so they match
    up end to end. For example:

       select st_astext(the_geom) from
    pgr_tsptrsp(pgr_texttopoints('__2,0;2,1;3,1;2,2;4,1;4,2;2,3;3,__2',
    0), 'edge_table', true, true) a, edge_table b where a.id2=b.id
    <http://b.id>;

    "LINESTRING(2 1,2 2)"
    "LINESTRING(2 2,3 2)"
    "LINESTRING(3 2,4 2)"
    "LINESTRING(4 1,4 2)" -- needs to be flipped
    "LINESTRING(3 1,4 1)" -- needs to be flipped
    "LINESTRING(2 1,3 1)" -- needs to be flipped
    "LINESTRING(2 1,2 2)"
    "LINESTRING(2 2,2 3)"
    "LINESTRING(2 2,2 3)" -- needs to be flipped
    "LINESTRING(2 1,2 2)" -- needs to be flipped
    "LINESTRING(2 0,2 1)" -- needs to be flipped
    "LINESTRING(2 0,2 1)"

    So I wrote a new function pgr_flipedges(ga geometry) that can be
    used like this:

    select st_astext(e) from (
       select unnest(pgr_flipedges(array___agg(the_geom))) as e
         from
    pgr_tsptrsp(pgr_texttopoints('__2,0;2,1;3,1;2,2;4,1;4,2;2,3;3,__2',
    0), 'edge_table', true, true) a,
              edge_table b
        where a.id2=b.id <http://b.id>
    ) as foo;

    "LINESTRING(2 1,2 2)"
    "LINESTRING(2 2,3 2)"
    "LINESTRING(3 2,4 2)"
    "LINESTRING(4 2,4 1)"
    "LINESTRING(4 1,3 1)"
    "LINESTRING(3 1,2 1)"
    "LINESTRING(2 1,2 2)"
    "LINESTRING(2 2,2 3)"
    "LINESTRING(2 3,2 2)"
    "LINESTRING(2 2,2 1)"
    "LINESTRING(2 1,2 0)"
    "LINESTRING(2 0,2 1)"

    Notice how all the edges have been flipped to return a continuous
    path from start to end of each adjacent segment in the path.

    -Steve
    All the mentioned code will eventually get checked into pgrouting
    2.1 development branch once it is stable and I have test cases and
    docs written for it.

    -Steve

    On 10/9/2013 10:29 AM, Stephen Woodbridge wrote:

        Hi all,

        I have been playing with some tools to allow me to integrate TSP
        optimization into a web application. I thought I would share
        what I have
        come up with for comments. One of the things I did was to try
        and break
        down the process into reusable modular functions. For example
        there are
        two functions to compute the distance matrix based on either
        Euclidean
        or kdijkstra distances. One could add other functions to compute
        them
        based on other algorithms. Also each function does one
        conversion so it
        is simple to understand and easy to test or replace with another
        function that does the transformation in a different way. Then
        the final
        function glues all the pieces together to get the final result.

        Goal:

        take a string or points like "x,y;x,y;x,y;..." and compute the TSP
        solution to order the points based on either Euclidean distance or
        network distances, then compute the route through the network
        and return
        the route geometry.

        Solution in progress:

        1. text to point geometry *
             pgr_texttopoints(pnts text, srid integer DEFAULT(4326))

        2. points to vertex ids *
             pgr_pointtoedgenode(edges text, pnt geometry, tol float8)
             pgr_pointstovids(pnts geometry, edges text, tol float8
        DEFAULT(0.01))

        3. points to edge ids **

        4. points to [edge id, pct] **

        5. points to Euclidean distance matrix *
             pgr_points2dmatrix(pnts geometry, OUT dmatrix double
        precision,
        OUT ids integer)

        6. vertex ids to kdijkstra distance matrix *
             pgr_vidstodmatrix(IN vids integer, IN pnts geometry, IN
        edges
        text, tol float8 DEFAULT(0.1), OUT dmatrix double precision,
        OUT ids
        integer)

        7. distance matrix to TSP to ordered list ***
        select * from pgr_tsp(
              (select dmatrix::float8
                 from pgr_vidstodmatrix(
                          pgr_pointstovids(

          pgr_texttopoints('2,0;2,1;3,1;__2,2;4,1;4,2;2,3;3,2',
        0),
                              'edge_table'),

          pgr_texttopoints('2,0;2,1;3,1;__2,2;4,1;4,2;2,3;3,2', 0),
                          'edge_table')
              ),
              1
        );

        8. reorder vids based on ordered list *

        9. compute trsp for pairs of vids in ordered list *,!
             pgr_trsp(sql text, vids integer, directed boolean,
        has_reverse_cost boolean, turn_restrict_sql text DEFAULT NULL::text)

             pgr_tsptrsp(pnts geometry, edges text, directed boolean,
        has_reverse_cost boolean, tol float8 DEFAULT(0.1), turn_restrict_sql
        text DEFAULT NULL::text)

             select * from
        pgr_tsptrsp(pgr_texttopoints('__2,0;2,1;3,1;2,2;4,1;4,2;2,3;3,__2',
        0),
        'edge_table', true, true);

        10. output results **

        NOTES:
        * - done
        ** - not done
        *** - already part of 2.0
        ! - computing a route through via points can be optimized in the
        C/C++
        code for better performance, but I currently just prototyped
        this up in
        plpgsql

        Thoughts,
            -Steve
        _________________________________________________
        pgrouting-dev mailing list
        pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
        http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;

    _________________________________________________
    pgrouting-dev mailing list
    pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
    http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
    <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;

_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

5

It’s working! Thanks! :slight_smile:

···

–
Helder Alves

+351912384076

On Mon, Nov 4, 2013 at 6:42 PM, Stephen Woodbridge <woodbri@swoodbridge.com> wrote:

You ways table does not have a column named “id” for now you might have to set up a view like:

create view v_ways as select your_id_col as id, source, target, cost from ways;

then try your query replacing ‘ways’ with ‘v_ways’

-Steve

On 11/4/2013 11:31 AM, Helder Alves wrote:

Hi Steve,

select dmatrix::float8
from pgr_vidstodmatrix(
pgr_pointstovids(

pgr_texttopoints(‘-7.50501,40.26310;-7.48864,40.17530;-7.49901,40.13950;-7.57596,40.12350;-7.61591,40.13230;-7.61935,40.13230;-7.67235,40.13580;-7.67087,40.13660;-7.66510,40.13860;-7.74559,40.15640;-7.74588,40.15730;-7.74746,40.15690;-7.74922,40.15540;-7.74926,40.15310;-7.73537,40.14230;-7.63556,40.18920;-7.64849,40.22630;-7.62354,40.25680;-7.62425,40.26280;-7.62223,40.25830;-7.62179,40.25680;-7.62116,40.25580;-7.64803,40.22390;-7.63916,40.20560;-7.63664,40.20250;-7.63767,40.19970;-7.63623,40.20000;-7.56974,40.26710;-7.49104,40.26500;-7.50473,40.26320’,
4326),
‘ways’),

pgr_texttopoints(‘-7.50501,40.26310;-7.48864,40.17530;-7.49901,40.13950;-7.57596,40.12350;-7.61591,40.13230;-7.61935,40.13230;-7.67235,40.13580;-7.67087,40.13660;-7.66510,40.13860;-7.74559,40.15640;-7.74588,40.15730;-7.74746,40.15690;-7.74922,40.15540;-7.74926,40.15310;-7.73537,40.14230;-7.63556,40.18920;-7.64849,40.22630;-7.62354,40.25680;-7.62425,40.26280;-7.62223,40.25830;-7.62179,40.25680;-7.62116,40.25580;-7.64803,40.22390;-7.63916,40.20560;-7.63664,40.20250;-7.63767,40.19970;-7.63623,40.20000;-7.56974,40.26710;-7.49104,40.26500;-7.50473,40.26320’,
4326),
‘ways’)

While running the query above, I got the error below.

column “id” does not exist
LINE 1: select id, source, target, cost from ways where the_geom && …
^
QUERY: select id, source, target, cost from ways where the_geom &&
‘0103000020E610000001000000050000002E34D769A4651FC05EBA490C020344402E34D769A4651FC0492EFF21FD2E444076ABE7A4F78D1DC0492EFF21FD2E444076ABE7A4F78D1DC05EBA490C020344402E34D769A4651FC05EBA490C02034440’::geometry
CONTEXT: PL/pgSQL function
pgr_vidstodmatrix(integer,geometry,text,double precision) line
57 at FOR over EXECUTE statement

I guess it’s some kind of bug, which is something it may happen when we
are testing something from the develop branch! :slight_smile:

Can you help me with this?

Thanks!

–
Helder Alves
+351912384076

On Wed, Oct 9, 2013 at 5:26 PM, Stephen Woodbridge

<woodbri@swoodbridge.com mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)> wrote:

Another common problem is orienting the returned edges so they match
up end to end. For example:

select st_astext(the_geom) from

pgr_tsptrsp(pgr_texttopoints(‘__2,0;2,1;3,1;2,2;4,1;4,2;2,3;3,__2’,

0), ‘edge_table’, true, true) a, edge_table b where a.id2=b.id

<http://b.id>;

“LINESTRING(2 1,2 2)”
“LINESTRING(2 2,3 2)”
“LINESTRING(3 2,4 2)”
“LINESTRING(4 1,4 2)” – needs to be flipped
“LINESTRING(3 1,4 1)” – needs to be flipped
“LINESTRING(2 1,3 1)” – needs to be flipped
“LINESTRING(2 1,2 2)”
“LINESTRING(2 2,2 3)”
“LINESTRING(2 2,2 3)” – needs to be flipped
“LINESTRING(2 1,2 2)” – needs to be flipped
“LINESTRING(2 0,2 1)” – needs to be flipped
“LINESTRING(2 0,2 1)”

So I wrote a new function pgr_flipedges(ga geometry) that can be
used like this:

select st_astext(e) from (

select unnest(pgr_flipedges(array___agg(the_geom))) as e
from
pgr_tsptrsp(pgr_texttopoints(‘__2,0;2,1;3,1;2,2;4,1;4,2;2,3;3,__2’,

0), ‘edge_table’, true, true) a,
edge_table b

where a.id2=b.id <http://b.id>

) as foo;

“LINESTRING(2 1,2 2)”
“LINESTRING(2 2,3 2)”
“LINESTRING(3 2,4 2)”
“LINESTRING(4 2,4 1)”
“LINESTRING(4 1,3 1)”
“LINESTRING(3 1,2 1)”
“LINESTRING(2 1,2 2)”
“LINESTRING(2 2,2 3)”
“LINESTRING(2 3,2 2)”
“LINESTRING(2 2,2 1)”
“LINESTRING(2 1,2 0)”
“LINESTRING(2 0,2 1)”

Notice how all the edges have been flipped to return a continuous
path from start to end of each adjacent segment in the path.

-Steve
All the mentioned code will eventually get checked into pgrouting
2.1 development branch once it is stable and I have test cases and
docs written for it.

-Steve

On 10/9/2013 10:29 AM, Stephen Woodbridge wrote:

Hi all,

I have been playing with some tools to allow me to integrate TSP
optimization into a web application. I thought I would share
what I have
come up with for comments. One of the things I did was to try
and break
down the process into reusable modular functions. For example
there are
two functions to compute the distance matrix based on either
Euclidean
or kdijkstra distances. One could add other functions to compute
them
based on other algorithms. Also each function does one
conversion so it
is simple to understand and easy to test or replace with another
function that does the transformation in a different way. Then
the final
function glues all the pieces together to get the final result.

Goal:

take a string or points like “x,y;x,y;x,y;…” and compute the TSP
solution to order the points based on either Euclidean distance or
network distances, then compute the route through the network
and return
the route geometry.

Solution in progress:

  1. text to point geometry *
    pgr_texttopoints(pnts text, srid integer DEFAULT(4326))

  2. points to vertex ids *
    pgr_pointtoedgenode(edges text, pnt geometry, tol float8)
    pgr_pointstovids(pnts geometry, edges text, tol float8
    DEFAULT(0.01))

  3. points to edge ids **

  4. points to [edge id, pct] **

  5. points to Euclidean distance matrix *
    pgr_points2dmatrix(pnts geometry, OUT dmatrix double
    precision,
    OUT ids integer)

  6. vertex ids to kdijkstra distance matrix *
    pgr_vidstodmatrix(IN vids integer, IN pnts geometry, IN
    edges
    text, tol float8 DEFAULT(0.1), OUT dmatrix double precision,
    OUT ids
    integer)

  7. distance matrix to TSP to ordered list ***
    select * from pgr_tsp(
    (select dmatrix::float8
    from pgr_vidstodmatrix(
    pgr_pointstovids(

pgr_texttopoints(‘2,0;2,1;3,1;__2,2;4,1;4,2;2,3;3,2’,
0),
‘edge_table’),

pgr_texttopoints(‘2,0;2,1;3,1;__2,2;4,1;4,2;2,3;3,2’, 0),

‘edge_table’)
),
1
);

  1. reorder vids based on ordered list *

  2. compute trsp for pairs of vids in ordered list *,!
    pgr_trsp(sql text, vids integer, directed boolean,
    has_reverse_cost boolean, turn_restrict_sql text DEFAULT NULL::text)

pgr_tsptrsp(pnts geometry, edges text, directed boolean,
has_reverse_cost boolean, tol float8 DEFAULT(0.1), turn_restrict_sql
text DEFAULT NULL::text)

select * from

pgr_tsptrsp(pgr_texttopoints(‘__2,0;2,1;3,1;2,2;4,1;4,2;2,3;3,__2’,

0),
‘edge_table’, true, true);

  1. output results **

NOTES:

    • done
      ** - not done
      *** - already part of 2.0
      ! - computing a route through via points can be optimized in the
      C/C++
      code for better performance, but I currently just prototyped
      this up in
      plpgsql

Thoughts,
-Steve

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev

<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

6

On 11/5/2013 7:53 PM, Helder Alves wrote:

It's working! Thanks! :slight_smile:

Great! As it turns out I had to do the same thing today on a project I was working on.

I'm somewhat conflicted as to the best way to deal with this issue. One way of dealing with this is to pass a sql query into the command or to pass in multiple arguments to all the user to specify all the column names. I don't like all the arguments because it makes the functions complex and harder to maintain. The sql statement is ok for some cases but does not work in all cases. I like the view idea in the cases where the sql statement does not work.

Lots of trade offs - my PRIMARY goal is to have some consistency between function signatures without making them too complex and to keep them easy to understand and remember.

Something to mull over ...

-Steve

--
Helder Alves
+351912384076

On Mon, Nov 4, 2013 at 6:42 PM, Stephen Woodbridge
<woodbri@swoodbridge.com <mailto:woodbri@swoodbridge.com>> wrote:

    You ways table does not have a column named "id" for now you might
    have to set up a view like:

    create view v_ways as select your_id_col as id, source, target, cost
    from ways;

    then try your query replacing 'ways' with 'v_ways'

    -Steve

    On 11/4/2013 11:31 AM, Helder Alves wrote:

        Hi Steve,

             select dmatrix::float8
                     from pgr_vidstodmatrix(
                              pgr_pointstovids(

        pgr_texttopoints('-7.50501,40.__26310;-7.48864,40.17530;-7.__49901,40.13950;-7.57596,40.__12350;-7.61591,40.13230;-7.__61935,40.13230;-7.67235,40.__13580;-7.67087,40.13660;-7.__66510,40.13860;-7.74559,40.__15640;-7.74588,40.15730;-7.__74746,40.15690;-7.74922,40.__15540;-7.74926,40.15310;-7.__73537,40.14230;-7.63556,40.__18920;-7.64849,40.22630;-7.__62354,40.25680;-7.62425,40.__26280;-7.62223,40.25830;-7.__62179,40.25680;-7.62116,40.__25580;-7.64803,40.22390;-7.__63916,40.20560;-7.63664,40.__20250;-7.63767,40.19970;-7.__63623,40.20000;-7.56974,40.__26710;-7.49104,40.26500;-7.__50473,40.26320',
             4326),
                                  'ways'),

        pgr_texttopoints('-7.50501,40.__26310;-7.48864,40.17530;-7.__49901,40.13950;-7.57596,40.__12350;-7.61591,40.13230;-7.__61935,40.13230;-7.67235,40.__13580;-7.67087,40.13660;-7.__66510,40.13860;-7.74559,40.__15640;-7.74588,40.15730;-7.__74746,40.15690;-7.74922,40.__15540;-7.74926,40.15310;-7.__73537,40.14230;-7.63556,40.__18920;-7.64849,40.22630;-7.__62354,40.25680;-7.62425,40.__26280;-7.62223,40.25830;-7.__62179,40.25680;-7.62116,40.__25580;-7.64803,40.22390;-7.__63916,40.20560;-7.63664,40.__20250;-7.63767,40.19970;-7.__63623,40.20000;-7.56974,40.__26710;-7.49104,40.26500;-7.__50473,40.26320',
             4326),
                              'ways')

        While running the query above, I got the error below.

             column "id" does not exist
             LINE 1: select id, source, target, cost from ways where
        the_geom && ...
                             ^
             QUERY: select id, source, target, cost from ways where
        the_geom &&

        '__0103000020E6100000010000000500__00002E34D769A4651FC05EBA490C02__0344402E34D769A4651FC0492EFF21__FD2E444076ABE7A4F78D1DC0492EFF__21FD2E444076ABE7A4F78D1DC05EBA__490C020344402E34D769A4651FC05E__BA490C02034440'::geometry
             CONTEXT: PL/pgSQL function
             pgr_vidstodmatrix(integer,__geometry,text,double
        precision) line
             57 at FOR over EXECUTE statement

        I guess it's some kind of bug, which is something it may happen
        when we
        are testing something from the develop branch! :slight_smile:

        Can you help me with this?

        Thanks!

        --
        Helder Alves
        +351912384076 <tel:%2B351912384076>

        On Wed, Oct 9, 2013 at 5:26 PM, Stephen Woodbridge
        <woodbri@swoodbridge.com <mailto:woodbri@swoodbridge.com>
        <mailto:woodbri@swoodbridge.__com
        <mailto:woodbri@swoodbridge.com>>> wrote:

             Another common problem is orienting the returned edges so
        they match
             up end to end. For example:

                select st_astext(the_geom) from

        pgr_tsptrsp(pgr_texttopoints('____2,0;2,1;3,1;2,2;4,1;4,2;2,3;__3,__2',

             0), 'edge_table', true, true) a, edge_table b where
        a.id2=b.id <http://b.id>
             <http://b.id>;

             "LINESTRING(2 1,2 2)"
             "LINESTRING(2 2,3 2)"
             "LINESTRING(3 2,4 2)"
             "LINESTRING(4 1,4 2)" -- needs to be flipped
             "LINESTRING(3 1,4 1)" -- needs to be flipped
             "LINESTRING(2 1,3 1)" -- needs to be flipped
             "LINESTRING(2 1,2 2)"
             "LINESTRING(2 2,2 3)"
             "LINESTRING(2 2,2 3)" -- needs to be flipped
             "LINESTRING(2 1,2 2)" -- needs to be flipped
             "LINESTRING(2 0,2 1)" -- needs to be flipped
             "LINESTRING(2 0,2 1)"

             So I wrote a new function pgr_flipedges(ga geometry) that
        can be
             used like this:

             select st_astext(e) from (
                select unnest(pgr_flipedges(array_____agg(the_geom))) as e
                  from

        pgr_tsptrsp(pgr_texttopoints('____2,0;2,1;3,1;2,2;4,1;4,2;2,3;__3,__2',

             0), 'edge_table', true, true) a,
                       edge_table b
                 where a.id2=b.id <http://b.id> <http://b.id>

             ) as foo;

             "LINESTRING(2 1,2 2)"
             "LINESTRING(2 2,3 2)"
             "LINESTRING(3 2,4 2)"
             "LINESTRING(4 2,4 1)"
             "LINESTRING(4 1,3 1)"
             "LINESTRING(3 1,2 1)"
             "LINESTRING(2 1,2 2)"
             "LINESTRING(2 2,2 3)"
             "LINESTRING(2 3,2 2)"
             "LINESTRING(2 2,2 1)"
             "LINESTRING(2 1,2 0)"
             "LINESTRING(2 0,2 1)"

             Notice how all the edges have been flipped to return a
        continuous
             path from start to end of each adjacent segment in the path.

             -Steve
             All the mentioned code will eventually get checked into
        pgrouting
             2.1 development branch once it is stable and I have test
        cases and
             docs written for it.

             -Steve

             On 10/9/2013 10:29 AM, Stephen Woodbridge wrote:

                 Hi all,

                 I have been playing with some tools to allow me to
        integrate TSP
                 optimization into a web application. I thought I would
        share
                 what I have
                 come up with for comments. One of the things I did was
        to try
                 and break
                 down the process into reusable modular functions. For
        example
                 there are
                 two functions to compute the distance matrix based on
        either
                 Euclidean
                 or kdijkstra distances. One could add other functions
        to compute
                 them
                 based on other algorithms. Also each function does one
                 conversion so it
                 is simple to understand and easy to test or replace
        with another
                 function that does the transformation in a different
        way. Then
                 the final
                 function glues all the pieces together to get the final
        result.

                 Goal:

                 take a string or points like "x,y;x,y;x,y;..." and
        compute the TSP
                 solution to order the points based on either Euclidean
        distance or
                 network distances, then compute the route through the
        network
                 and return
                 the route geometry.

                 Solution in progress:

                 1. text to point geometry *
                      pgr_texttopoints(pnts text, srid integer
        DEFAULT(4326))

                 2. points to vertex ids *
                      pgr_pointtoedgenode(edges text, pnt geometry, tol
        float8)
                      pgr_pointstovids(pnts geometry, edges text, tol
        float8
                 DEFAULT(0.01))

                 3. points to edge ids **

                 4. points to [edge id, pct] **

                 5. points to Euclidean distance matrix *
                      pgr_points2dmatrix(pnts geometry, OUT dmatrix double
                 precision,
                 OUT ids integer)

                 6. vertex ids to kdijkstra distance matrix *
                      pgr_vidstodmatrix(IN vids integer, IN pnts
        geometry, IN
                 edges
                 text, tol float8 DEFAULT(0.1), OUT dmatrix double
        precision,
                 OUT ids
                 integer)

                 7. distance matrix to TSP to ordered list ***
                 select * from pgr_tsp(
                       (select dmatrix::float8
                          from pgr_vidstodmatrix(
                                   pgr_pointstovids(

                   pgr_texttopoints('2,0;2,1;3,1;____2,2;4,1;4,2;2,3;3,2',
                 0),
                                       'edge_table'),

        pgr_texttopoints('2,0;2,1;3,1;____2,2;4,1;4,2;2,3;3,2', 0),

                                   'edge_table')
                       ),
                       1
                 );

                 8. reorder vids based on ordered list *

                 9. compute trsp for pairs of vids in ordered list *,!
                      pgr_trsp(sql text, vids integer, directed boolean,
                 has_reverse_cost boolean, turn_restrict_sql text
        DEFAULT NULL::text)

                      pgr_tsptrsp(pnts geometry, edges text, directed
        boolean,
                 has_reverse_cost boolean, tol float8 DEFAULT(0.1),
        turn_restrict_sql
                 text DEFAULT NULL::text)

                      select * from

        pgr_tsptrsp(pgr_texttopoints('____2,0;2,1;3,1;2,2;4,1;4,2;2,3;__3,__2',

                 0),
                 'edge_table', true, true);

                 10. output results **

                 NOTES:
                 * - done
                 ** - not done
                 *** - already part of 2.0
                 ! - computing a route through via points can be
        optimized in the
                 C/C++
                 code for better performance, but I currently just
        prototyped
                 this up in
                 plpgsql

                 Thoughts,
                     -Steve
                 ___________________________________________________
                 pgrouting-dev mailing list
        pgrouting-dev@lists.osgeo.org
        <mailto:pgrouting-dev@lists.osgeo.org>
        <mailto:pgrouting-dev@lists.__osgeo.org
        <mailto:pgrouting-dev@lists.osgeo.org>>
        http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev&gt;

        <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;\_\_&gt;

             ___________________________________________________
             pgrouting-dev mailing list
        pgrouting-dev@lists.osgeo.org
        <mailto:pgrouting-dev@lists.osgeo.org>
        <mailto:pgrouting-dev@lists.__osgeo.org
        <mailto:pgrouting-dev@lists.osgeo.org>>
        http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev&gt;

             <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;\_\_&gt;

        _________________________________________________
        pgrouting-dev mailing list
        pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
        http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;

    _________________________________________________
    pgrouting-dev mailing list
    pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
    http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
    <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;

_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

7

Hello Helder,

Did you notice that I checked in a new version of pgr_vidstodmatrix() with a different signature that is 3x faster. Also the function you are using below will likely go away as it was just a quick prototype so you should move your code to the new function.

Thank you for giving them a try.

-Steve

On 11/5/2013 7:53 PM, Helder Alves wrote:

It's working! Thanks! :slight_smile:

--
Helder Alves
+351912384076

On Mon, Nov 4, 2013 at 6:42 PM, Stephen Woodbridge
<woodbri@swoodbridge.com <mailto:woodbri@swoodbridge.com>> wrote:

    You ways table does not have a column named "id" for now you might
    have to set up a view like:

    create view v_ways as select your_id_col as id, source, target, cost
    from ways;

    then try your query replacing 'ways' with 'v_ways'

    -Steve

    On 11/4/2013 11:31 AM, Helder Alves wrote:

        Hi Steve,

             select dmatrix::float8
                     from pgr_vidstodmatrix(
                              pgr_pointstovids(

        pgr_texttopoints('-7.50501,40.__26310;-7.48864,40.17530;-7.__49901,40.13950;-7.57596,40.__12350;-7.61591,40.13230;-7.__61935,40.13230;-7.67235,40.__13580;-7.67087,40.13660;-7.__66510,40.13860;-7.74559,40.__15640;-7.74588,40.15730;-7.__74746,40.15690;-7.74922,40.__15540;-7.74926,40.15310;-7.__73537,40.14230;-7.63556,40.__18920;-7.64849,40.22630;-7.__62354,40.25680;-7.62425,40.__26280;-7.62223,40.25830;-7.__62179,40.25680;-7.62116,40.__25580;-7.64803,40.22390;-7.__63916,40.20560;-7.63664,40.__20250;-7.63767,40.19970;-7.__63623,40.20000;-7.56974,40.__26710;-7.49104,40.26500;-7.__50473,40.26320',
             4326),
                                  'ways'),

        pgr_texttopoints('-7.50501,40.__26310;-7.48864,40.17530;-7.__49901,40.13950;-7.57596,40.__12350;-7.61591,40.13230;-7.__61935,40.13230;-7.67235,40.__13580;-7.67087,40.13660;-7.__66510,40.13860;-7.74559,40.__15640;-7.74588,40.15730;-7.__74746,40.15690;-7.74922,40.__15540;-7.74926,40.15310;-7.__73537,40.14230;-7.63556,40.__18920;-7.64849,40.22630;-7.__62354,40.25680;-7.62425,40.__26280;-7.62223,40.25830;-7.__62179,40.25680;-7.62116,40.__25580;-7.64803,40.22390;-7.__63916,40.20560;-7.63664,40.__20250;-7.63767,40.19970;-7.__63623,40.20000;-7.56974,40.__26710;-7.49104,40.26500;-7.__50473,40.26320',
             4326),
                              'ways')

        While running the query above, I got the error below.

             column "id" does not exist
             LINE 1: select id, source, target, cost from ways where
        the_geom && ...
                             ^
             QUERY: select id, source, target, cost from ways where
        the_geom &&

        '__0103000020E6100000010000000500__00002E34D769A4651FC05EBA490C02__0344402E34D769A4651FC0492EFF21__FD2E444076ABE7A4F78D1DC0492EFF__21FD2E444076ABE7A4F78D1DC05EBA__490C020344402E34D769A4651FC05E__BA490C02034440'::geometry
             CONTEXT: PL/pgSQL function
             pgr_vidstodmatrix(integer,__geometry,text,double
        precision) line
             57 at FOR over EXECUTE statement

        I guess it's some kind of bug, which is something it may happen
        when we
        are testing something from the develop branch! :slight_smile:

        Can you help me with this?

        Thanks!

        --
        Helder Alves
        +351912384076 <tel:%2B351912384076>

        On Wed, Oct 9, 2013 at 5:26 PM, Stephen Woodbridge
        <woodbri@swoodbridge.com <mailto:woodbri@swoodbridge.com>
        <mailto:woodbri@swoodbridge.__com
        <mailto:woodbri@swoodbridge.com>>> wrote:

             Another common problem is orienting the returned edges so
        they match
             up end to end. For example:

                select st_astext(the_geom) from

        pgr_tsptrsp(pgr_texttopoints('____2,0;2,1;3,1;2,2;4,1;4,2;2,3;__3,__2',

             0), 'edge_table', true, true) a, edge_table b where
        a.id2=b.id <http://b.id>
             <http://b.id>;

             "LINESTRING(2 1,2 2)"
             "LINESTRING(2 2,3 2)"
             "LINESTRING(3 2,4 2)"
             "LINESTRING(4 1,4 2)" -- needs to be flipped
             "LINESTRING(3 1,4 1)" -- needs to be flipped
             "LINESTRING(2 1,3 1)" -- needs to be flipped
             "LINESTRING(2 1,2 2)"
             "LINESTRING(2 2,2 3)"
             "LINESTRING(2 2,2 3)" -- needs to be flipped
             "LINESTRING(2 1,2 2)" -- needs to be flipped
             "LINESTRING(2 0,2 1)" -- needs to be flipped
             "LINESTRING(2 0,2 1)"

             So I wrote a new function pgr_flipedges(ga geometry) that
        can be
             used like this:

             select st_astext(e) from (
                select unnest(pgr_flipedges(array_____agg(the_geom))) as e
                  from

        pgr_tsptrsp(pgr_texttopoints('____2,0;2,1;3,1;2,2;4,1;4,2;2,3;__3,__2',

             0), 'edge_table', true, true) a,
                       edge_table b
                 where a.id2=b.id <http://b.id> <http://b.id>

             ) as foo;

             "LINESTRING(2 1,2 2)"
             "LINESTRING(2 2,3 2)"
             "LINESTRING(3 2,4 2)"
             "LINESTRING(4 2,4 1)"
             "LINESTRING(4 1,3 1)"
             "LINESTRING(3 1,2 1)"
             "LINESTRING(2 1,2 2)"
             "LINESTRING(2 2,2 3)"
             "LINESTRING(2 3,2 2)"
             "LINESTRING(2 2,2 1)"
             "LINESTRING(2 1,2 0)"
             "LINESTRING(2 0,2 1)"

             Notice how all the edges have been flipped to return a
        continuous
             path from start to end of each adjacent segment in the path.

             -Steve
             All the mentioned code will eventually get checked into
        pgrouting
             2.1 development branch once it is stable and I have test
        cases and
             docs written for it.

             -Steve

             On 10/9/2013 10:29 AM, Stephen Woodbridge wrote:

                 Hi all,

                 I have been playing with some tools to allow me to
        integrate TSP
                 optimization into a web application. I thought I would
        share
                 what I have
                 come up with for comments. One of the things I did was
        to try
                 and break
                 down the process into reusable modular functions. For
        example
                 there are
                 two functions to compute the distance matrix based on
        either
                 Euclidean
                 or kdijkstra distances. One could add other functions
        to compute
                 them
                 based on other algorithms. Also each function does one
                 conversion so it
                 is simple to understand and easy to test or replace
        with another
                 function that does the transformation in a different
        way. Then
                 the final
                 function glues all the pieces together to get the final
        result.

                 Goal:

                 take a string or points like "x,y;x,y;x,y;..." and
        compute the TSP
                 solution to order the points based on either Euclidean
        distance or
                 network distances, then compute the route through the
        network
                 and return
                 the route geometry.

                 Solution in progress:

                 1. text to point geometry *
                      pgr_texttopoints(pnts text, srid integer
        DEFAULT(4326))

                 2. points to vertex ids *
                      pgr_pointtoedgenode(edges text, pnt geometry, tol
        float8)
                      pgr_pointstovids(pnts geometry, edges text, tol
        float8
                 DEFAULT(0.01))

                 3. points to edge ids **

                 4. points to [edge id, pct] **

                 5. points to Euclidean distance matrix *
                      pgr_points2dmatrix(pnts geometry, OUT dmatrix double
                 precision,
                 OUT ids integer)

                 6. vertex ids to kdijkstra distance matrix *
                      pgr_vidstodmatrix(IN vids integer, IN pnts
        geometry, IN
                 edges
                 text, tol float8 DEFAULT(0.1), OUT dmatrix double
        precision,
                 OUT ids
                 integer)

                 7. distance matrix to TSP to ordered list ***
                 select * from pgr_tsp(
                       (select dmatrix::float8
                          from pgr_vidstodmatrix(
                                   pgr_pointstovids(

                   pgr_texttopoints('2,0;2,1;3,1;____2,2;4,1;4,2;2,3;3,2',
                 0),
                                       'edge_table'),

        pgr_texttopoints('2,0;2,1;3,1;____2,2;4,1;4,2;2,3;3,2', 0),

                                   'edge_table')
                       ),
                       1
                 );

                 8. reorder vids based on ordered list *

                 9. compute trsp for pairs of vids in ordered list *,!
                      pgr_trsp(sql text, vids integer, directed boolean,
                 has_reverse_cost boolean, turn_restrict_sql text
        DEFAULT NULL::text)

                      pgr_tsptrsp(pnts geometry, edges text, directed
        boolean,
                 has_reverse_cost boolean, tol float8 DEFAULT(0.1),
        turn_restrict_sql
                 text DEFAULT NULL::text)

                      select * from

        pgr_tsptrsp(pgr_texttopoints('____2,0;2,1;3,1;2,2;4,1;4,2;2,3;__3,__2',

                 0),
                 'edge_table', true, true);

                 10. output results **

                 NOTES:
                 * - done
                 ** - not done
                 *** - already part of 2.0
                 ! - computing a route through via points can be
        optimized in the
                 C/C++
                 code for better performance, but I currently just
        prototyped
                 this up in
                 plpgsql

                 Thoughts,
                     -Steve
                 ___________________________________________________
                 pgrouting-dev mailing list
        pgrouting-dev@lists.osgeo.org
        <mailto:pgrouting-dev@lists.osgeo.org>
        <mailto:pgrouting-dev@lists.__osgeo.org
        <mailto:pgrouting-dev@lists.osgeo.org>>
        http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev&gt;

        <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;\_\_&gt;

             ___________________________________________________
             pgrouting-dev mailing list
        pgrouting-dev@lists.osgeo.org
        <mailto:pgrouting-dev@lists.osgeo.org>
        <mailto:pgrouting-dev@lists.__osgeo.org
        <mailto:pgrouting-dev@lists.osgeo.org>>
        http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev&gt;

             <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;\_\_&gt;

        _________________________________________________
        pgrouting-dev mailing list
        pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
        http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;

    _________________________________________________
    pgrouting-dev mailing list
    pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
    http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
    <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;

_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

8

Hi Steve,

Thanks for the update!

I’m trying the new code but is not clear to me what’s the best query to get the total distance (in meters or kilometers) / time (in secs, minutes or hours) for the route generated by TSP function (using a distance matrix) and also how to get the geometry data needed to get that same route represented as a QGIS layer.

I guess I’m missing something but after reading everything thoroughly I’m not getting there…

···

–
Helder Alves

+351912384076

On Sun, Nov 10, 2013 at 2:40 PM, Stephen Woodbridge <woodbri@swoodbridge.com> wrote:

Hello Helder,

Did you notice that I checked in a new version of pgr_vidstodmatrix() with a different signature that is 3x faster. Also the function you are using below will likely go away as it was just a quick prototype so you should move your code to the new function.

Thank you for giving them a try.

-Steve

On 11/5/2013 7:53 PM, Helder Alves wrote:

It’s working! Thanks! :slight_smile:

–
Helder Alves
+351912384076

On Mon, Nov 4, 2013 at 6:42 PM, Stephen Woodbridge

<woodbri@swoodbridge.com mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)> wrote:

You ways table does not have a column named “id” for now you might
have to set up a view like:

create view v_ways as select your_id_col as id, source, target, cost
from ways;

then try your query replacing ‘ways’ with ‘v_ways’

-Steve

On 11/4/2013 11:31 AM, Helder Alves wrote:

Hi Steve,

select dmatrix::float8
from pgr_vidstodmatrix(
pgr_pointstovids(

pgr_texttopoints(‘-7.50501,40.__26310;-7.48864,40.17530;-7.__49901,40.13950;-7.57596,40.__12350;-7.61591,40.13230;-7.__61935,40.13230;-7.67235,40.__13580;-7.67087,40.13660;-7.__66510,40.13860;-7.74559,40.__15640;-7.74588,40.15730;-7.__74746,40.15690;-7.74922,40.__15540;-7.74926,40.15310;-7.__73537,40.14230;-7.63556,40.__18920;-7.64849,40.22630;-7.__62354,40.25680;-7.62425,40.__26280;-7.62223,40.25830;-7.__62179,40.25680;-7.62116,40.__25580;-7.64803,40.22390;-7.__63916,40.20560;-7.63664,40.__20250;-7.63767,40.19970;-7.__63623,40.20000;-7.56974,40.__26710;-7.49104,40.26500;-7.__50473,40.26320’,
4326),
‘ways’),

pgr_texttopoints(‘-7.50501,40.__26310;-7.48864,40.17530;-7.__49901,40.13950;-7.57596,40.__12350;-7.61591,40.13230;-7.__61935,40.13230;-7.67235,40.__13580;-7.67087,40.13660;-7.__66510,40.13860;-7.74559,40.__15640;-7.74588,40.15730;-7.__74746,40.15690;-7.74922,40.__15540;-7.74926,40.15310;-7.__73537,40.14230;-7.63556,40.__18920;-7.64849,40.22630;-7.__62354,40.25680;-7.62425,40.__26280;-7.62223,40.25830;-7.__62179,40.25680;-7.62116,40.__25580;-7.64803,40.22390;-7.__63916,40.20560;-7.63664,40.__20250;-7.63767,40.19970;-7.__63623,40.20000;-7.56974,40.__26710;-7.49104,40.26500;-7.__50473,40.26320’,

4326),
‘ways’)

While running the query above, I got the error below.

column “id” does not exist
LINE 1: select id, source, target, cost from ways where
the_geom && …
^
QUERY: select id, source, target, cost from ways where
the_geom &&

‘__0103000020E6100000010000000500__00002E34D769A4651FC05EBA490C02__0344402E34D769A4651FC0492EFF21__FD2E444076ABE7A4F78D1DC0492EFF__21FD2E444076ABE7A4F78D1DC05EBA__490C020344402E34D769A4651FC05E__BA490C02034440’::geometry
CONTEXT: PL/pgSQL function
pgr_vidstodmatrix(integer,__geometry,text,double

precision) line
57 at FOR over EXECUTE statement

I guess it’s some kind of bug, which is something it may happen
when we
are testing something from the develop branch! :slight_smile:

Can you help me with this?

Thanks!

–
Helder Alves

+351912384076 tel:%2B351912384076

On Wed, Oct 9, 2013 at 5:26 PM, Stephen Woodbridge
<woodbri@swoodbridge.com mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)

<mailto:woodbri@swoodbridge.__com

mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)>> wrote:

Another common problem is orienting the returned edges so
they match
up end to end. For example:

select st_astext(the_geom) from

pgr_tsptrsp(pgr_texttopoints(‘____2,0;2,1;3,1;2,2;4,1;4,2;2,3;__3,__2’,

0), ‘edge_table’, true, true) a, edge_table b where
a.id2=b.id <http://b.id>
<http://b.id>;

“LINESTRING(2 1,2 2)”
“LINESTRING(2 2,3 2)”
“LINESTRING(3 2,4 2)”
“LINESTRING(4 1,4 2)” – needs to be flipped
“LINESTRING(3 1,4 1)” – needs to be flipped
“LINESTRING(2 1,3 1)” – needs to be flipped
“LINESTRING(2 1,2 2)”
“LINESTRING(2 2,2 3)”
“LINESTRING(2 2,2 3)” – needs to be flipped
“LINESTRING(2 1,2 2)” – needs to be flipped
“LINESTRING(2 0,2 1)” – needs to be flipped
“LINESTRING(2 0,2 1)”

So I wrote a new function pgr_flipedges(ga geometry) that
can be
used like this:

select st_astext(e) from (

select unnest(pgr_flipedges(array_____agg(the_geom))) as e
from

pgr_tsptrsp(pgr_texttopoints(‘____2,0;2,1;3,1;2,2;4,1;4,2;2,3;__3,__2’,

0), ‘edge_table’, true, true) a,
edge_table b

where a.id2=b.id <http://b.id> <http://b.id>

) as foo;

“LINESTRING(2 1,2 2)”
“LINESTRING(2 2,3 2)”
“LINESTRING(3 2,4 2)”
“LINESTRING(4 2,4 1)”
“LINESTRING(4 1,3 1)”
“LINESTRING(3 1,2 1)”
“LINESTRING(2 1,2 2)”
“LINESTRING(2 2,2 3)”
“LINESTRING(2 3,2 2)”
“LINESTRING(2 2,2 1)”
“LINESTRING(2 1,2 0)”
“LINESTRING(2 0,2 1)”

Notice how all the edges have been flipped to return a
continuous
path from start to end of each adjacent segment in the path.

-Steve
All the mentioned code will eventually get checked into
pgrouting
2.1 development branch once it is stable and I have test
cases and
docs written for it.

-Steve

On 10/9/2013 10:29 AM, Stephen Woodbridge wrote:

Hi all,

I have been playing with some tools to allow me to
integrate TSP
optimization into a web application. I thought I would
share
what I have
come up with for comments. One of the things I did was
to try
and break
down the process into reusable modular functions. For
example
there are
two functions to compute the distance matrix based on
either
Euclidean
or kdijkstra distances. One could add other functions
to compute
them
based on other algorithms. Also each function does one
conversion so it
is simple to understand and easy to test or replace
with another
function that does the transformation in a different
way. Then
the final
function glues all the pieces together to get the final
result.

Goal:

take a string or points like “x,y;x,y;x,y;…” and
compute the TSP
solution to order the points based on either Euclidean
distance or
network distances, then compute the route through the
network
and return
the route geometry.

Solution in progress:

  1. text to point geometry *
    pgr_texttopoints(pnts text, srid integer
    DEFAULT(4326))

  2. points to vertex ids *
    pgr_pointtoedgenode(edges text, pnt geometry, tol
    float8)
    pgr_pointstovids(pnts geometry, edges text, tol
    float8
    DEFAULT(0.01))

  3. points to edge ids **

  4. points to [edge id, pct] **

  5. points to Euclidean distance matrix *
    pgr_points2dmatrix(pnts geometry, OUT dmatrix double
    precision,
    OUT ids integer)

  6. vertex ids to kdijkstra distance matrix *
    pgr_vidstodmatrix(IN vids integer, IN pnts
    geometry, IN
    edges
    text, tol float8 DEFAULT(0.1), OUT dmatrix double
    precision,
    OUT ids
    integer)

  7. distance matrix to TSP to ordered list ***
    select * from pgr_tsp(
    (select dmatrix::float8
    from pgr_vidstodmatrix(
    pgr_pointstovids(

pgr_texttopoints(‘2,0;2,1;3,1;____2,2;4,1;4,2;2,3;3,2’,
0),
‘edge_table’),

pgr_texttopoints(‘2,0;2,1;3,1;____2,2;4,1;4,2;2,3;3,2’, 0),

‘edge_table’)
),
1
);

  1. reorder vids based on ordered list *

  2. compute trsp for pairs of vids in ordered list *,!
    pgr_trsp(sql text, vids integer, directed boolean,
    has_reverse_cost boolean, turn_restrict_sql text
    DEFAULT NULL::text)

pgr_tsptrsp(pnts geometry, edges text, directed
boolean,
has_reverse_cost boolean, tol float8 DEFAULT(0.1),
turn_restrict_sql
text DEFAULT NULL::text)

select * from

pgr_tsptrsp(pgr_texttopoints(‘____2,0;2,1;3,1;2,2;4,1;4,2;2,3;__3,__2’,

0),
‘edge_table’, true, true);

  1. output results **

NOTES:

    • done
      ** - not done
      *** - already part of 2.0
      ! - computing a route through via points can be
      optimized in the
      C/C++
      code for better performance, but I currently just
      prototyped
      this up in
      plpgsql

Thoughts,
-Steve

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)

<mailto:pgrouting-dev@lists.__osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)>
http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>

<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>__>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)

<mailto:pgrouting-dev@lists.__osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)>
http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>

<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>__>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

9

On 11/12/2013 2:51 PM, Helder Alves wrote:

Hi Steve,

Thanks for the update!

I'm trying the new code but is not clear to me what's the best query to
get the total distance (in meters or kilometers) / time (in secs,
minutes or hours) for the route generated by TSP function (using a
distance matrix) and also how to get the geometry data needed to get
that same route represented as a QGIS layer.

OK, when you make your distance matrix, the values in it are based on the cost function that you use to generate it.

So for example it you have two columns in your edge table, like cost_distance and cost_time, then when you create your distance matrix and select the edges using cost_time as cost, then your distance matrix is based on time. The units are whatever you use in the columns. Likewise if you build your matrix with cost_distance as cost then your distance matrix is based on the cost_distance values in whatever units you used for that column.

TSP ONLY orders the nodes, if you need the routes between the nodes then those have to be computed again based on the ordered nodes.

I say "again", because we computed them internally when we computed the distance matrix. But these were not cached anywhere, so they will have to be computed again after the TSP has ordered the nodes.

I have been side tracked, looking into whether or not I can integrate a local OSRM instance into pgrouting because if you don't need the dynamic graph definition, ie: you can live with a static graph definition, then OSRM would allow for some significant performance gains in computing distance matrices and routes.

I have also looked at some additional wrapping of the TSP and routing with an eye toward caching the routes generated in dmatrix creation for later use to generate the routes.

So the bottom line is you are needing the stuff I am developing. I need it also, but it takes time to design and code stuff, especially while putting out other fires. And all the code (whatever that might turn out to be) is not there yet.

-Steve

I guess I'm missing something but after reading everything thoroughly
I'm not getting there...

--
Helder Alves
+351912384076

On Sun, Nov 10, 2013 at 2:40 PM, Stephen Woodbridge
<woodbri@swoodbridge.com <mailto:woodbri@swoodbridge.com>> wrote:

    Hello Helder,

    Did you notice that I checked in a new version of
    pgr_vidstodmatrix() with a different signature that is 3x faster.
    Also the function you are using below will likely go away as it was
    just a quick prototype so you should move your code to the new function.

    Thank you for giving them a try.

    -Steve

    On 11/5/2013 7:53 PM, Helder Alves wrote:

        It's working! Thanks! :slight_smile:

        --
        Helder Alves
        +351912384076 <tel:%2B351912384076>

        On Mon, Nov 4, 2013 at 6:42 PM, Stephen Woodbridge
        <woodbri@swoodbridge.com <mailto:woodbri@swoodbridge.com>
        <mailto:woodbri@swoodbridge.__com
        <mailto:woodbri@swoodbridge.com>>> wrote:

             You ways table does not have a column named "id" for now
        you might
             have to set up a view like:

             create view v_ways as select your_id_col as id, source,
        target, cost
             from ways;

             then try your query replacing 'ways' with 'v_ways'

             -Steve

             On 11/4/2013 11:31 AM, Helder Alves wrote:

                 Hi Steve,

                      select dmatrix::float8
                              from pgr_vidstodmatrix(
                                       pgr_pointstovids(

        pgr_texttopoints('-7.50501,40.____26310;-7.48864,40.17530;-7.____49901,40.13950;-7.57596,40.____12350;-7.61591,40.13230;-7.____61935,40.13230;-7.67235,40.____13580;-7.67087,40.13660;-7.____66510,40.13860;-7.74559,40.____15640;-7.74588,40.15730;-7.____74746,40.15690;-7.74922,40.____15540;-7.74926,40.15310;-7.____73537,40.14230;-7.63556,40.____18920;-7.64849,40.22630;-7.____62354,40.25680;-7.62425,40.____26280;-7.62223,40.25830;-7.____62179,40.25680;-7.62116,40.____25580;-7.64803,40.22390;-7.____63916,40.20560;-7.63664,40.____20250;-7.63767,40.19970;-7.____63623,40.20000;-7.56974,40.____26710;-7.49104,40.26500;-7.____50473,40.26320',
                      4326),
                                           'ways'),

        pgr_texttopoints('-7.50501,40.____26310;-7.48864,40.17530;-7.____49901,40.13950;-7.57596,40.____12350;-7.61591,40.13230;-7.____61935,40.13230;-7.67235,40.____13580;-7.67087,40.13660;-7.____66510,40.13860;-7.74559,40.____15640;-7.74588,40.15730;-7.____74746,40.15690;-7.74922,40.____15540;-7.74926,40.15310;-7.____73537,40.14230;-7.63556,40.____18920;-7.64849,40.22630;-7.____62354,40.25680;-7.62425,40.____26280;-7.62223,40.25830;-7.____62179,40.25680;-7.62116,40.____25580;-7.64803,40.22390;-7.____63916,40.20560;-7.63664,40.____20250;-7.63767,40.19970;-7.____63623,40.20000;-7.56974,40.____26710;-7.49104,40.26500;-7.____50473,40.26320',

                      4326),
                                       'ways')

                 While running the query above, I got the error below.

                      column "id" does not exist
                      LINE 1: select id, source, target, cost from ways
        where
                 the_geom && ...
                                      ^
                      QUERY: select id, source, target, cost from ways
        where
                 the_geom &&

        '____0103000020E6100000010000000500______00002E34D769A4651FC05EBA490C02______0344402E34D769A4651FC0492EFF21______FD2E444076ABE7A4F78D1DC0492EFF______21FD2E444076ABE7A4F78D1DC05EBA______490C020344402E34D769A4651FC05E____BA490C02034440'::geometry
                      CONTEXT: PL/pgSQL function
                      pgr_vidstodmatrix(integer,____geometry,text,double

                 precision) line
                      57 at FOR over EXECUTE statement

                 I guess it's some kind of bug, which is something it
        may happen
                 when we
                 are testing something from the develop branch! :slight_smile:

                 Can you help me with this?

                 Thanks!

                 --
                 Helder Alves
        +351912384076 <tel:%2B351912384076> <tel:%2B351912384076>

                 On Wed, Oct 9, 2013 at 5:26 PM, Stephen Woodbridge
                 <woodbri@swoodbridge.com
        <mailto:woodbri@swoodbridge.com>
        <mailto:woodbri@swoodbridge.__com <mailto:woodbri@swoodbridge.com>>
                 <mailto:woodbri@swoodbridge.
        <mailto:woodbri@swoodbridge.>____com

                 <mailto:woodbri@swoodbridge.__com
        <mailto:woodbri@swoodbridge.com>>>> wrote:

                      Another common problem is orienting the returned
        edges so
                 they match
                      up end to end. For example:

                         select st_astext(the_geom) from

        pgr_tsptrsp(pgr_texttopoints('______2,0;2,1;3,1;2,2;4,1;4,2;2,__3;__3,__2',

                      0), 'edge_table', true, true) a, edge_table b where
                 a.id2=b.id <http://b.id> <http://b.id>
                      <http://b.id>;

                      "LINESTRING(2 1,2 2)"
                      "LINESTRING(2 2,3 2)"
                      "LINESTRING(3 2,4 2)"
                      "LINESTRING(4 1,4 2)" -- needs to be flipped
                      "LINESTRING(3 1,4 1)" -- needs to be flipped
                      "LINESTRING(2 1,3 1)" -- needs to be flipped
                      "LINESTRING(2 1,2 2)"
                      "LINESTRING(2 2,2 3)"
                      "LINESTRING(2 2,2 3)" -- needs to be flipped
                      "LINESTRING(2 1,2 2)" -- needs to be flipped
                      "LINESTRING(2 0,2 1)" -- needs to be flipped
                      "LINESTRING(2 0,2 1)"

                      So I wrote a new function pgr_flipedges(ga
        geometry) that
                 can be
                      used like this:

                      select st_astext(e) from (
                         select
        unnest(pgr_flipedges(array_______agg(the_geom))) as e
                           from

        pgr_tsptrsp(pgr_texttopoints('______2,0;2,1;3,1;2,2;4,1;4,2;2,__3;__3,__2',

                      0), 'edge_table', true, true) a,
                                edge_table b
                          where a.id2=b.id <http://b.id> <http://b.id>
        <http://b.id>

                      ) as foo;

                      "LINESTRING(2 1,2 2)"
                      "LINESTRING(2 2,3 2)"
                      "LINESTRING(3 2,4 2)"
                      "LINESTRING(4 2,4 1)"
                      "LINESTRING(4 1,3 1)"
                      "LINESTRING(3 1,2 1)"
                      "LINESTRING(2 1,2 2)"
                      "LINESTRING(2 2,2 3)"
                      "LINESTRING(2 3,2 2)"
                      "LINESTRING(2 2,2 1)"
                      "LINESTRING(2 1,2 0)"
                      "LINESTRING(2 0,2 1)"

                      Notice how all the edges have been flipped to return a
                 continuous
                      path from start to end of each adjacent segment in
        the path.

                      -Steve
                      All the mentioned code will eventually get checked
        into
                 pgrouting
                      2.1 development branch once it is stable and I
        have test
                 cases and
                      docs written for it.

                      -Steve

                      On 10/9/2013 10:29 AM, Stephen Woodbridge wrote:

                          Hi all,

                          I have been playing with some tools to allow
        me to
                 integrate TSP
                          optimization into a web application. I thought
        I would
                 share
                          what I have
                          come up with for comments. One of the things I
        did was
                 to try
                          and break
                          down the process into reusable modular
        functions. For
                 example
                          there are
                          two functions to compute the distance matrix
        based on
                 either
                          Euclidean
                          or kdijkstra distances. One could add other
        functions
                 to compute
                          them
                          based on other algorithms. Also each function
        does one
                          conversion so it
                          is simple to understand and easy to test or
        replace
                 with another
                          function that does the transformation in a
        different
                 way. Then
                          the final
                          function glues all the pieces together to get
        the final
                 result.

                          Goal:

                          take a string or points like "x,y;x,y;x,y;..." and
                 compute the TSP
                          solution to order the points based on either
        Euclidean
                 distance or
                          network distances, then compute the route
        through the
                 network
                          and return
                          the route geometry.

                          Solution in progress:

                          1. text to point geometry *
                               pgr_texttopoints(pnts text, srid integer
                 DEFAULT(4326))

                          2. points to vertex ids *
                               pgr_pointtoedgenode(edges text, pnt
        geometry, tol
                 float8)
                               pgr_pointstovids(pnts geometry, edges
        text, tol
                 float8
                          DEFAULT(0.01))

                          3. points to edge ids **

                          4. points to [edge id, pct] **

                          5. points to Euclidean distance matrix *
                               pgr_points2dmatrix(pnts geometry, OUT
        dmatrix double
                          precision,
                          OUT ids integer)

                          6. vertex ids to kdijkstra distance matrix *
                               pgr_vidstodmatrix(IN vids integer, IN pnts
                 geometry, IN
                          edges
                          text, tol float8 DEFAULT(0.1), OUT dmatrix double
                 precision,
                          OUT ids
                          integer)

                          7. distance matrix to TSP to ordered list ***
                          select * from pgr_tsp(
                                (select dmatrix::float8
                                   from pgr_vidstodmatrix(
                                            pgr_pointstovids(

          pgr_texttopoints('2,0;2,1;3,1;______2,2;4,1;4,2;2,3;3,2',
                          0),
                                                'edge_table'),

        pgr_texttopoints('2,0;2,1;3,1;______2,2;4,1;4,2;2,3;3,2', 0),

                                            'edge_table')
                                ),
                                1
                          );

                          8. reorder vids based on ordered list *

                          9. compute trsp for pairs of vids in ordered
        list *,!
                               pgr_trsp(sql text, vids integer,
        directed boolean,
                          has_reverse_cost boolean, turn_restrict_sql text
                 DEFAULT NULL::text)

                               pgr_tsptrsp(pnts geometry, edges text,
        directed
                 boolean,
                          has_reverse_cost boolean, tol float8 DEFAULT(0.1),
                 turn_restrict_sql
                          text DEFAULT NULL::text)

                               select * from

        pgr_tsptrsp(pgr_texttopoints('______2,0;2,1;3,1;2,2;4,1;4,2;2,__3;__3,__2',

                          0),
                          'edge_table', true, true);

                          10. output results **

                          NOTES:
                          * - done
                          ** - not done
                          *** - already part of 2.0
                          ! - computing a route through via points can be
                 optimized in the
                          C/C++
                          code for better performance, but I currently just
                 prototyped
                          this up in
                          plpgsql

                          Thoughts,
                              -Steve

          _____________________________________________________

                          pgrouting-dev mailing list
        pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
                 <mailto:pgrouting-dev@lists.__osgeo.org
        <mailto:pgrouting-dev@lists.osgeo.org>>
                 <mailto:pgrouting-dev@lists.
        <mailto:pgrouting-dev@lists.>____osgeo.org <http://osgeo.org>
                 <mailto:pgrouting-dev@lists.__osgeo.org
        <mailto:pgrouting-dev@lists.osgeo.org>>>
        http://lists.osgeo.org/______mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev&gt;

        <http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev&gt;\_\_&gt;

        <http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev&gt;

        <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;\_\_&gt;\_\_&gt;

                      _____________________________________________________
                      pgrouting-dev mailing list
        pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
                 <mailto:pgrouting-dev@lists.__osgeo.org
        <mailto:pgrouting-dev@lists.osgeo.org>>
                 <mailto:pgrouting-dev@lists.
        <mailto:pgrouting-dev@lists.>____osgeo.org <http://osgeo.org>
                 <mailto:pgrouting-dev@lists.__osgeo.org
        <mailto:pgrouting-dev@lists.osgeo.org>>>
        http://lists.osgeo.org/______mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev&gt;

        <http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev&gt;\_\_&gt;

          <http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev&gt;

        <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;\_\_&gt;\_\_&gt;

                 ___________________________________________________
                 pgrouting-dev mailing list
        pgrouting-dev@lists.osgeo.org
        <mailto:pgrouting-dev@lists.osgeo.org>
        <mailto:pgrouting-dev@lists.__osgeo.org
        <mailto:pgrouting-dev@lists.osgeo.org>>
        http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev&gt;

        <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;\_\_&gt;

             ___________________________________________________
             pgrouting-dev mailing list
        pgrouting-dev@lists.osgeo.org
        <mailto:pgrouting-dev@lists.osgeo.org>
        <mailto:pgrouting-dev@lists.__osgeo.org
        <mailto:pgrouting-dev@lists.osgeo.org>>
        http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev&gt;
             <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;\_\_&gt;

        _________________________________________________
        pgrouting-dev mailing list
        pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
        http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;

    _________________________________________________
    pgrouting-dev mailing list
    pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
    http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
    <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;

_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

10

OK, Steve… Thanks for the explanation!

It helps a lot because one of my doubts was precisely that need to compute the routes again, after those same routes to have been computed already. I thought I was missing some point there but now I understand that is the only way.

I’ll continue my exploration into pgRouting world for a couple of weeks more and after that I must come up with a plan where I’ll try to find out a way of contributing somehow to your RFC’s efforts, as clearly they are headed to the same features I need.

···

–
Helder Alves

+351912384076

On Tue, Nov 12, 2013 at 8:23 PM, Stephen Woodbridge <woodbri@swoodbridge.com> wrote:

On 11/12/2013 2:51 PM, Helder Alves wrote:

Hi Steve,

Thanks for the update!

I’m trying the new code but is not clear to me what’s the best query to
get the total distance (in meters or kilometers) / time (in secs,
minutes or hours) for the route generated by TSP function (using a
distance matrix) and also how to get the geometry data needed to get
that same route represented as a QGIS layer.

OK, when you make your distance matrix, the values in it are based on the cost function that you use to generate it.

So for example it you have two columns in your edge table, like cost_distance and cost_time, then when you create your distance matrix and select the edges using cost_time as cost, then your distance matrix is based on time. The units are whatever you use in the columns. Likewise if you build your matrix with cost_distance as cost then your distance matrix is based on the cost_distance values in whatever units you used for that column.

TSP ONLY orders the nodes, if you need the routes between the nodes then those have to be computed again based on the ordered nodes.

I say “again”, because we computed them internally when we computed the distance matrix. But these were not cached anywhere, so they will have to be computed again after the TSP has ordered the nodes.

I have been side tracked, looking into whether or not I can integrate a local OSRM instance into pgrouting because if you don’t need the dynamic graph definition, ie: you can live with a static graph definition, then OSRM would allow for some significant performance gains in computing distance matrices and routes.

I have also looked at some additional wrapping of the TSP and routing with an eye toward caching the routes generated in dmatrix creation for later use to generate the routes.

So the bottom line is you are needing the stuff I am developing. I need it also, but it takes time to design and code stuff, especially while putting out other fires. And all the code (whatever that might turn out to be) is not there yet.

-Steve

I guess I’m missing something but after reading everything thoroughly
I’m not getting there…

–
Helder Alves
+351912384076

On Sun, Nov 10, 2013 at 2:40 PM, Stephen Woodbridge

<woodbri@swoodbridge.com mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)> wrote:

Hello Helder,

Did you notice that I checked in a new version of
pgr_vidstodmatrix() with a different signature that is 3x faster.
Also the function you are using below will likely go away as it was
just a quick prototype so you should move your code to the new function.

Thank you for giving them a try.

-Steve

On 11/5/2013 7:53 PM, Helder Alves wrote:

It’s working! Thanks! :slight_smile:

–
Helder Alves

+351912384076 tel:%2B351912384076

On Mon, Nov 4, 2013 at 6:42 PM, Stephen Woodbridge
<woodbri@swoodbridge.com mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)

<mailto:woodbri@swoodbridge.__com
mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)>> wrote:

You ways table does not have a column named “id” for now
you might
have to set up a view like:

create view v_ways as select your_id_col as id, source,
target, cost
from ways;

then try your query replacing ‘ways’ with ‘v_ways’

-Steve

On 11/4/2013 11:31 AM, Helder Alves wrote:

Hi Steve,

select dmatrix::float8
from pgr_vidstodmatrix(
pgr_pointstovids(

pgr_texttopoints(‘-7.50501,40.____26310;-7.48864,40.17530;-7.____49901,40.13950;-7.57596,40.____12350;-7.61591,40.13230;-7.____61935,40.13230;-7.67235,40.____13580;-7.67087,40.13660;-7.____66510,40.13860;-7.74559,40.____15640;-7.74588,40.15730;-7.____74746,40.15690;-7.74922,40.____15540;-7.74926,40.15310;-7.____73537,40.14230;-7.63556,40.____18920;-7.64849,40.22630;-7.____62354,40.25680;-7.62425,40.____26280;-7.62223,40.25830;-7.____62179,40.25680;-7.62116,40.____25580;-7.64803,40.22390;-7.____63916,40.20560;-7.63664,40.____20250;-7.63767,40.19970;-7.____63623,40.20000;-7.56974,40.____26710;-7.49104,40.26500;-7.____50473,40.26320’,
4326),
‘ways’),

pgr_texttopoints(‘-7.50501,40.____26310;-7.48864,40.17530;-7.____49901,40.13950;-7.57596,40.____12350;-7.61591,40.13230;-7.____61935,40.13230;-7.67235,40.____13580;-7.67087,40.13660;-7.____66510,40.13860;-7.74559,40.____15640;-7.74588,40.15730;-7.____74746,40.15690;-7.74922,40.____15540;-7.74926,40.15310;-7.____73537,40.14230;-7.63556,40.____18920;-7.64849,40.22630;-7.____62354,40.25680;-7.62425,40.____26280;-7.62223,40.25830;-7.____62179,40.25680;-7.62116,40.____25580;-7.64803,40.22390;-7.____63916,40.20560;-7.63664,40.____20250;-7.63767,40.19970;-7.____63623,40.20000;-7.56974,40.____26710;-7.49104,40.26500;-7.____50473,40.26320’,

4326),
‘ways’)

While running the query above, I got the error below.

column “id” does not exist
LINE 1: select id, source, target, cost from ways
where
the_geom && …
^
QUERY: select id, source, target, cost from ways
where
the_geom &&

‘____0103000020E6100000010000000500______00002E34D769A4651FC05EBA490C02______0344402E34D769A4651FC0492EFF21______FD2E444076ABE7A4F78D1DC0492EFF______21FD2E444076ABE7A4F78D1DC05EBA______490C020344402E34D769A4651FC05E____BA490C02034440’::geometry
CONTEXT: PL/pgSQL function
pgr_vidstodmatrix(integer,____geometry,text,double

precision) line
57 at FOR over EXECUTE statement

I guess it’s some kind of bug, which is something it
may happen
when we
are testing something from the develop branch! :slight_smile:

Can you help me with this?

Thanks!

–
Helder Alves

+351912384076 tel:%2B351912384076 tel:%2B351912384076

On Wed, Oct 9, 2013 at 5:26 PM, Stephen Woodbridge
<woodbri@swoodbridge.com
mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)
<mailto:woodbri@swoodbridge.__com mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)>

<mailto:woodbri@swoodbridge.
mailto:[woodbri@swoodbridge](mailto:woodbri@swoodbridge).____com

<mailto:woodbri@swoodbridge.__com
mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)>>> wrote:

Another common problem is orienting the returned
edges so
they match
up end to end. For example:

select st_astext(the_geom) from

pgr_tsptrsp(pgr_texttopoints(‘______2,0;2,1;3,1;2,2;4,1;4,2;2,__3;__3,__2’,

0), ‘edge_table’, true, true) a, edge_table b where
a.id2=b.id <http://b.id> <http://b.id>
<http://b.id>;

“LINESTRING(2 1,2 2)”
“LINESTRING(2 2,3 2)”
“LINESTRING(3 2,4 2)”
“LINESTRING(4 1,4 2)” – needs to be flipped
“LINESTRING(3 1,4 1)” – needs to be flipped
“LINESTRING(2 1,3 1)” – needs to be flipped
“LINESTRING(2 1,2 2)”
“LINESTRING(2 2,2 3)”
“LINESTRING(2 2,2 3)” – needs to be flipped
“LINESTRING(2 1,2 2)” – needs to be flipped
“LINESTRING(2 0,2 1)” – needs to be flipped
“LINESTRING(2 0,2 1)”

So I wrote a new function pgr_flipedges(ga
geometry) that
can be
used like this:

select st_astext(e) from (
select

unnest(pgr_flipedges(array_______agg(the_geom))) as e
from

pgr_tsptrsp(pgr_texttopoints(‘______2,0;2,1;3,1;2,2;4,1;4,2;2,__3;__3,__2’,

0), ‘edge_table’, true, true) a,
edge_table b
where a.id2=b.id <http://b.id> <http://b.id>

<http://b.id>

) as foo;

“LINESTRING(2 1,2 2)”
“LINESTRING(2 2,3 2)”
“LINESTRING(3 2,4 2)”
“LINESTRING(4 2,4 1)”
“LINESTRING(4 1,3 1)”
“LINESTRING(3 1,2 1)”
“LINESTRING(2 1,2 2)”
“LINESTRING(2 2,2 3)”
“LINESTRING(2 3,2 2)”
“LINESTRING(2 2,2 1)”
“LINESTRING(2 1,2 0)”
“LINESTRING(2 0,2 1)”

Notice how all the edges have been flipped to return a
continuous
path from start to end of each adjacent segment in
the path.

-Steve
All the mentioned code will eventually get checked
into
pgrouting
2.1 development branch once it is stable and I
have test
cases and
docs written for it.

-Steve

On 10/9/2013 10:29 AM, Stephen Woodbridge wrote:

Hi all,

I have been playing with some tools to allow
me to
integrate TSP
optimization into a web application. I thought
I would
share
what I have
come up with for comments. One of the things I
did was
to try
and break
down the process into reusable modular
functions. For
example
there are
two functions to compute the distance matrix
based on
either
Euclidean
or kdijkstra distances. One could add other
functions
to compute
them
based on other algorithms. Also each function
does one
conversion so it
is simple to understand and easy to test or
replace
with another
function that does the transformation in a
different
way. Then
the final
function glues all the pieces together to get
the final
result.

Goal:

take a string or points like “x,y;x,y;x,y;…” and
compute the TSP
solution to order the points based on either
Euclidean
distance or
network distances, then compute the route
through the
network
and return
the route geometry.

Solution in progress:

  1. text to point geometry *
    pgr_texttopoints(pnts text, srid integer
    DEFAULT(4326))

  2. points to vertex ids *
    pgr_pointtoedgenode(edges text, pnt
    geometry, tol
    float8)
    pgr_pointstovids(pnts geometry, edges
    text, tol
    float8
    DEFAULT(0.01))

  3. points to edge ids **

  4. points to [edge id, pct] **

  5. points to Euclidean distance matrix *
    pgr_points2dmatrix(pnts geometry, OUT
    dmatrix double
    precision,
    OUT ids integer)

  6. vertex ids to kdijkstra distance matrix *
    pgr_vidstodmatrix(IN vids integer, IN pnts
    geometry, IN
    edges
    text, tol float8 DEFAULT(0.1), OUT dmatrix double
    precision,
    OUT ids
    integer)

  7. distance matrix to TSP to ordered list ***
    select * from pgr_tsp(
    (select dmatrix::float8
    from pgr_vidstodmatrix(
    pgr_pointstovids(

pgr_texttopoints(‘2,0;2,1;3,1;______2,2;4,1;4,2;2,3;3,2’,
0),
‘edge_table’),

pgr_texttopoints(‘2,0;2,1;3,1;______2,2;4,1;4,2;2,3;3,2’, 0),

‘edge_table’)
),
1
);

  1. reorder vids based on ordered list *

  2. compute trsp for pairs of vids in ordered
    list *,!
    pgr_trsp(sql text, vids integer,
    directed boolean,
    has_reverse_cost boolean, turn_restrict_sql text
    DEFAULT NULL::text)

pgr_tsptrsp(pnts geometry, edges text,
directed
boolean,
has_reverse_cost boolean, tol float8 DEFAULT(0.1),
turn_restrict_sql
text DEFAULT NULL::text)

select * from

pgr_tsptrsp(pgr_texttopoints(‘______2,0;2,1;3,1;2,2;4,1;4,2;2,__3;__3,__2’,

0),
‘edge_table’, true, true);

  1. output results **

NOTES:

    • done
      ** - not done
      *** - already part of 2.0
      ! - computing a route through via points can be
      optimized in the
      C/C++
      code for better performance, but I currently just
      prototyped
      this up in
      plpgsql

Thoughts,
-Steve

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
<mailto:pgrouting-dev@lists.__osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)>

<mailto:pgrouting-dev@lists.
mailto:[pgrouting-dev@lists](mailto:pgrouting-dev@lists).____osgeo.org <http://osgeo.org>
<mailto:pgrouting-dev@lists.__osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)>>
http://lists.osgeo.org/______mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev>

<http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>__>

<http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>

<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>>>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
<mailto:pgrouting-dev@lists.__osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)>

<mailto:pgrouting-dev@lists.
mailto:[pgrouting-dev@lists](mailto:pgrouting-dev@lists).____osgeo.org <http://osgeo.org>
<mailto:pgrouting-dev@lists.__osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)>>
http://lists.osgeo.org/______mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev>

<http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>__>

<http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>

<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev

<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>>>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
<mailto:pgrouting-dev@lists.__osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)>
http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>

<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>__>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
<mailto:pgrouting-dev@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)>
http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>
<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

11

Hi Steve,

Where did you put pgr_trsptsp in the source tree?

I can’t find it…

Thanks!

···

–
Helder Alves

12

On 12/12/2013 12:49 PM, Helder Alves wrote:

Hi Steve,

Where did you put pgr_trsptsp in the source tree?

I don't think I did anything like that. IIRC, the discussion was to use pgr_vidsToDMatrix() that uses kdijkstra to compute the distance matrix, then use TSP to get the ordered list of points then call trsp with an array of locations to get point to point routes with via points. Read src/trsp/doc/index.rst in the develop branch.

You might be thinking about:
https://github.com/pgRouting/pgrouting/tree/develop/src/kdijkstra

  Where I Added a new version of pgr_vidsToDMatrix written in C that is 3X fast…

-Steve

I can't find it...

Thanks!

--
Helder Alves

_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

13

I’ve already compiled that version… :wink:

Can you please check the query below?

select * from pgr_trsp(
‘select id, source, target, cost, reverse_cost from ways’,
pgr_pointstovids(
pgr_texttopoints(‘-8.6406,40.65374;-8.6637,40.64008;-8.6923,40.63095;-8.7411,40.63105’, 4326),
‘ways’), – array of vids
false, – directed graph?
false – has_reverse_cost?
);

This is the result I get from the query:

seq;id1;id2;cost
1;-1;0;0
2;-1;0;0
3;-1;0;0

If I run a standalone pointstovids query, these are the vids I get: “{228347,228369,98306,146098}”

I must tell you that the geometry between 228347 and 146098 is just fine and routable, and to go from a vid to the other you have to go though 228369 and 98306.

Do you have any idea of what is going on here?

Thanks! :slight_smile:

···

–
Helder Alves

+351912384076

On Thu, Dec 12, 2013 at 6:28 PM, Stephen Woodbridge <woodbri@swoodbridge.com> wrote:

On 12/12/2013 12:49 PM, Helder Alves wrote:

Hi Steve,

Where did you put pgr_trsptsp in the source tree?

I don’t think I did anything like that. IIRC, the discussion was to use pgr_vidsToDMatrix() that uses kdijkstra to compute the distance matrix, then use TSP to get the ordered list of points then call trsp with an array of locations to get point to point routes with via points. Read src/trsp/doc/index.rst in the develop branch.

You might be thinking about:
https://github.com/pgRouting/pgrouting/tree/develop/src/kdijkstra

Where I Added a new version of pgr_vidsToDMatrix written in C that is 3X fast…

-Steve

I can’t find it…

Thanks!

–
Helder Alves

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

14

On 12/12/2013 2:07 PM, Helder Alves wrote:

I've already compiled that version... :wink:

Can you please check the query below?

select * from pgr_trsp(
     'select id, source, target, cost, reverse_cost from ways',
     pgr_pointstovids(

  pgr_texttopoints('-8.6406,40.65374;-8.6637,40.64008;-8.6923,40.63095;-8.7411,40.63105', 4326),
        'ways'), -- array of vids
     false, -- directed graph?
     false -- has_reverse_cost?
     );

This is the result I get from the query:

seq;id1;id2;cost
1;-1;0;0
2;-1;0;0
3;-1;0;0

If I run a standalone pointstovids query, these are the vids I get:
"{228347,228369,98306,146098}"

So you are saying:

select * from pgr_pointstovids(pgr_texttopoints(
'-8.6406,40.65374;-8.6637,40.64008;-8.6923,40.63095;-8.7411,40.63105', 4326), 'ways');

returns:

{228347,228369,98306,146098}

and:

select * from pgr_trsp(
   'select id, source, target, cost, reverse_cost from ways',
   '{228347,228369,98306,146098}'::integer,
   false, false);

is returning:

  seq;id1;id2;cost
  1;-1;0;0
  2;-1;0;0
  3;-1;0;0

Hmmm, what do you get with:

select * from pgr_trsp(
   'select id, source, target, cost, reverse_cost from ways',
   228347, 228369, false, false);

select * from pgr_trsp(
   'select id, source, target, cost, reverse_cost from ways',
   228369, 98306, false, false);

select * from pgr_trsp(
   'select id, source, target, cost, reverse_cost from ways',
   98306, 146098, false, false);

I must tell you that the geometry between 228347 and 146098 is just fine
and routable, and to go from a vid to the other you have to go though
228369 and 98306.

Have you read and run these tools?

http://imaptools.com:8081/pgr2-doc/2.0/en/doc/src/tutorial/analytics.html
http://imaptools.com:8081/pgr2-doc/2.0/en/src/common/doc/functions/node_network.html

Do you have any idea of what is going on here?

You have to break it down to simple queries to find the root cause of the problem.

-Steve

Thanks! :slight_smile:

--
Helder Alves
+351912384076

On Thu, Dec 12, 2013 at 6:28 PM, Stephen Woodbridge
<woodbri@swoodbridge.com <mailto:woodbri@swoodbridge.com>> wrote:

    On 12/12/2013 12:49 PM, Helder Alves wrote:

        Hi Steve,

        Where did you put pgr_trsptsp in the source tree?

    I don't think I did anything like that. IIRC, the discussion was to
    use pgr_vidsToDMatrix() that uses kdijkstra to compute the distance
    matrix, then use TSP to get the ordered list of points then call
    trsp with an array of locations to get point to point routes with
    via points. Read src/trsp/doc/index.rst in the develop branch.

    You might be thinking about:
    https://github.com/pgRouting/__pgrouting/tree/develop/src/__kdijkstra <https://github.com/pgRouting/pgrouting/tree/develop/src/kdijkstra&gt;

      Where I Added a new version of pgr_vidsToDMatrix written in C that
    is 3X fast…

    -Steve

        I can't find it...

        Thanks!

        --
        Helder Alves

        _________________________________________________
        pgrouting-dev mailing list
        pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
        http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;

    _________________________________________________
    pgrouting-dev mailing list
    pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
    http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
    <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;

_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

15

https://github.com/pgRouting/pgrouting/wiki/Working-with-OSM-Data

Please feel free to add to this if you have useful information on working with OSM data.

Thanks,
   -Steve

On 12/12/2013 2:49 PM, Stephen Woodbridge wrote:

On 12/12/2013 2:07 PM, Helder Alves wrote:

I've already compiled that version... :wink:

Can you please check the query below?

select * from pgr_trsp(
     'select id, source, target, cost, reverse_cost from ways',
     pgr_pointstovids(

pgr_texttopoints('-8.6406,40.65374;-8.6637,40.64008;-8.6923,40.63095;-8.7411,40.63105',
4326),
        'ways'), -- array of vids
     false, -- directed graph?
     false -- has_reverse_cost?
     );

This is the result I get from the query:

seq;id1;id2;cost
1;-1;0;0
2;-1;0;0
3;-1;0;0

If I run a standalone pointstovids query, these are the vids I get:
"{228347,228369,98306,146098}"

So you are saying:

select * from pgr_pointstovids(pgr_texttopoints(
'-8.6406,40.65374;-8.6637,40.64008;-8.6923,40.63095;-8.7411,40.63105',
4326), 'ways');

returns:

{228347,228369,98306,146098}

and:

select * from pgr_trsp(
   'select id, source, target, cost, reverse_cost from ways',
   '{228347,228369,98306,146098}'::integer,
   false, false);

is returning:

  seq;id1;id2;cost
  1;-1;0;0
  2;-1;0;0
  3;-1;0;0

Hmmm, what do you get with:

select * from pgr_trsp(
   'select id, source, target, cost, reverse_cost from ways',
   228347, 228369, false, false);

select * from pgr_trsp(
   'select id, source, target, cost, reverse_cost from ways',
   228369, 98306, false, false);

select * from pgr_trsp(
   'select id, source, target, cost, reverse_cost from ways',
   98306, 146098, false, false);

I must tell you that the geometry between 228347 and 146098 is just fine
and routable, and to go from a vid to the other you have to go though
228369 and 98306.

Have you read and run these tools?

http://imaptools.com:8081/pgr2-doc/2.0/en/doc/src/tutorial/analytics.html
http://imaptools.com:8081/pgr2-doc/2.0/en/src/common/doc/functions/node_network.html

Do you have any idea of what is going on here?

You have to break it down to simple queries to find the root cause of
the problem.

-Steve

Thanks! :slight_smile:

--
Helder Alves
+351912384076

On Thu, Dec 12, 2013 at 6:28 PM, Stephen Woodbridge
<woodbri@swoodbridge.com <mailto:woodbri@swoodbridge.com>> wrote:

    On 12/12/2013 12:49 PM, Helder Alves wrote:

        Hi Steve,

        Where did you put pgr_trsptsp in the source tree?

    I don't think I did anything like that. IIRC, the discussion was to
    use pgr_vidsToDMatrix() that uses kdijkstra to compute the distance
    matrix, then use TSP to get the ordered list of points then call
    trsp with an array of locations to get point to point routes with
    via points. Read src/trsp/doc/index.rst in the develop branch.

    You might be thinking about:

https://github.com/pgRouting/__pgrouting/tree/develop/src/__kdijkstra
<https://github.com/pgRouting/pgrouting/tree/develop/src/kdijkstra&gt;

      Where I Added a new version of pgr_vidsToDMatrix written in C that
    is 3X fast…

    -Steve

        I can't find it...

        Thanks!

        --
        Helder Alves

        _________________________________________________
        pgrouting-dev mailing list
        pgrouting-dev@lists.osgeo.org
<mailto:pgrouting-dev@lists.osgeo.org>
        http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;

    _________________________________________________
    pgrouting-dev mailing list
    pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
    http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
    <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;

_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

16

Hi again Steve!

You got it right.

All the simple pgr_trsp queries you suggested returned:

seq;id1;id2;cost
0;-1;0;0

The result from pgr_analyzegraph check is “OK”.

SELECT id1 as path, ST_Length_Spheroid(st_astext(st_linemerge(st_union(b.the_geom))), ‘SPHEROID[“GRS_1980”,6378137,298.257222101]’)
FROM pgr_kdijkstraPath(
‘SELECT id, source, target, cost, reverse_cost FROM ways’,
98306, array[146098], true, true) a,
ways b
WHERE a.id3=b.id
GROUP by id1
ORDER by id1;

Definitely I think something is not OK. The output of the query above is the following one:

path;st_length_spheroid
146098;4374.81625857547

As may be guessing already, this query for the other 2 pairs of vids (228347, 228369 and 228369,98306) also returned the expected distances.

What do you suggest as next step?

···

–
Helder Alves

17

On 12/12/2013 7:13 PM, Helder Alves wrote:

Hi again Steve!

You got it right.

All the simple pgr_trsp queries you suggested returned:

*seq;id1;id2;cost*
0;-1;0;0

The result from pgr_analyzegraph check is "OK".

    SELECT id1 as path,
    ST_Length_Spheroid(st_astext(st_linemerge(st_union(b.the_geom))),
    'SPHEROID["GRS_1980",6378137,298.257222101]')
       FROM pgr_kdijkstraPath(
           'SELECT id, source, target, cost, reverse_cost FROM ways',
           98306, array[146098], true, true) a,
                 ways b
    WHERE a.id3=b.id <http://b.id>
    GROUP by id1
    ORDER by id1;

Definitely I think something is not OK. The output of the query above is
the following one:

*path;st_length_spheroid*
146098;4374.81625857547

As may be guessing already, this query for the other 2 pairs of vids
(228347, 228369 and 228369,98306) also returned the expected distances.

What do you suggest as next step?

https://github.com/pgRouting/pgrouting/wiki/Working-with-OSM-Data

This is a script that I use to create a big rectangular grid of overlapping horizontal and vertical lines that I call pgr_nodenetwork on, the join it back to the original table to make a useful table for pgRouting. Mostly I offer it so you can see how to:

1. run pgr_nodenetwork
2. create a new table using a join
3. and then create a topology

You probably need to run the three steps above to get a usable table for pgRouting.

-Steve

~/work/osrm-tools$ cat mk-testdb2
#/bin/sh

DBNAME=osrm_test
DBUSER=postgres
DBHOST=mappy

dropdb -U $DBUSER -h $DBHOST $DBNAME
createdb -U $DBUSER -h $DBHOST $DBNAME

psql -U $DBUSER -h $DBHOST $DBNAME <<EOF
create extension postgis;
create extension pgrouting;

-- create 50x50 grid of overlapping lines horizontal and vertical

create table ddunnoded (
   id serial not null primary key,
   name text,
   dir_travel character(1),
   speed_cat character(1)
);
select addgeometrycolumn('ddunnoded', 'the_geom', 4326, 'LINESTRING', 2);

insert into ddunnoded (dir_travel, speed_cat, name, the_geom)
select case when s1%7 = 0 then 'F' when s1%7 = 4 then 'T' else 'B' end,
        (random()*4+1)::character,
        'H'||s1,
        st_setsrid(st_makeline(st_makepoint(-77.0, 42.0+(3.0/50.0*(s1-1))),
                               st_makepoint(-74.0, 42.0+(3.0/50.0*(s1-1)))), 4326)
   from (select generate_series(1,50) as s1) as foo
union all
select case when s1%11 = 0 then 'F' when s1%11 = 7 then 'T' else 'B' end,
        (random()*4+1)::character,
        'V'||s1,
        st_setsrid(st_makeline(st_makepoint(-77.0+(3.0/50.0*(s1-1)), 42.0),
                               st_makepoint(-77.0+(3.0/50.0*(s1-1)), 45.0)), 4326)
   from (select generate_series(1,50) as s1) as foo;

-- node the grid so we can use it
select pgr_nodenetwork('ddunnoded',0.000001);

-- cat m/sec kph mph
-- 1 25 90 56
-- 2 18 65 40
-- 3 15 54 33
-- 4 10 36 22
-- 5 5 18 11

-- copy the noded table into a table we can use for a graph
-- and add the required columns
create table ddnoded2 (
   gid serial not null primary key,
   id integer,
   name text,
   source integer,
   target integer,
   dir_travel character(1),
   speed_cat character(1),
   roundabout character(1) default 'N',
   tunnel character(1) default 'N',
   bridge character(1) default 'N',
   len_m float8,
   cost float8
);
select addgeometrycolumn('ddnoded2', 'the_geom', 4326, 'LINESTRING', 2);

insert into ddnoded2 (id, name, dir_travel, speed_cat, len_m, cost, the_geom)
select a.id,
        name,
        dir_travel,
        speed_cat,
        st_length2d_spheroid(a.the_geom, 'SPHEROID["GRS_1980",6378137,298.257222101]') as len_m,
        st_length2d_spheroid(a.the_geom, 'SPHEROID["GRS_1980",6378137,298.257222101]') / case when speed_cat='1' then 25.0
            when speed_cat='2' then 18.0
            when speed_cat='3' then 15.0
            when speed_cat='4' then 10.0
            else 5.0 end as cost,
        a.the_geom
   from ddunnoded_noded a, ddunnoded b
  where a.old_id=b.id
  order by a.old_id, a.sub_id;

-- now create a topology
select pgr_createtopology('ddnoded2', 0.000001, id:='gid');

create table ddnoded2_restrictions (
     id serial not null primary key,
     n_via integer,
     n_from integer,
     n_to integer,
     is_forbidden boolean,
     to_way_id integer
);

-- Total query runtime: 8080 ms.
EOF

18

Steve,

Thanks for your time. Definitely will try that!

As I had no problem creating the vertices table and the graph check returned “OK”, I assumed everything was OK.

–
Helder Alves

On Dec 13, 2013 1:57 AM, “Stephen Woodbridge” <woodbri@swoodbridge.com> wrote:

On 12/12/2013 7:13 PM, Helder Alves wrote:

Hi again Steve!

You got it right.

All the simple pgr_trsp queries you suggested returned:

seq;id1;id2;cost
0;-1;0;0

The result from pgr_analyzegraph check is “OK”.

SELECT id1 as path,
ST_Length_Spheroid(st_astext(st_linemerge(st_union(b.the_geom))),
‘SPHEROID[“GRS_1980”,6378137,298.257222101]’)
FROM pgr_kdijkstraPath(
‘SELECT id, source, target, cost, reverse_cost FROM ways’,
98306, array[146098], true, true) a,
ways b
WHERE a.id3=b.id <http://b.id>
GROUP by id1
ORDER by id1;

Definitely I think something is not OK. The output of the query above is
the following one:

path;st_length_spheroid
146098;4374.81625857547

As may be guessing already, this query for the other 2 pairs of vids
(228347, 228369 and 228369,98306) also returned the expected distances.

What do you suggest as next step?

https://github.com/pgRouting/pgrouting/wiki/Working-with-OSM-Data

This is a script that I use to create a big rectangular grid of overlapping horizontal and vertical lines that I call pgr_nodenetwork on, the join it back to the original table to make a useful table for pgRouting. Mostly I offer it so you can see how to:

  1. run pgr_nodenetwork
  2. create a new table using a join
  3. and then create a topology

You probably need to run the three steps above to get a usable table for pgRouting.

-Steve

~/work/osrm-tools$ cat mk-testdb2
#/bin/sh

DBNAME=osrm_test
DBUSER=postgres
DBHOST=mappy

dropdb -U $DBUSER -h $DBHOST $DBNAME
createdb -U $DBUSER -h $DBHOST $DBNAME

psql -U $DBUSER -h $DBHOST $DBNAME <<EOF
create extension postgis;
create extension pgrouting;

– create 50x50 grid of overlapping lines horizontal and vertical

create table ddunnoded (
id serial not null primary key,
name text,
dir_travel character(1),
speed_cat character(1)
);
select addgeometrycolumn(‘ddunnoded’, ‘the_geom’, 4326, ‘LINESTRING’, 2);

insert into ddunnoded (dir_travel, speed_cat, name, the_geom)
select case when s1%7 = 0 then ‘F’ when s1%7 = 4 then ‘T’ else ‘B’ end,
(random()4+1)::character,
‘H’||s1,
st_setsrid(st_makeline(st_makepoint(-77.0, 42.0+(3.0/50.0(s1-1))),
st_makepoint(-74.0, 42.0+(3.0/50.0*(s1-1)))), 4326)
from (select generate_series(1,50) as s1) as foo
union all
select case when s1%11 = 0 then ‘F’ when s1%11 = 7 then ‘T’ else ‘B’ end,
(random()4+1)::character,
‘V’||s1,
st_setsrid(st_makeline(st_makepoint(-77.0+(3.0/50.0(s1-1)), 42.0),
st_makepoint(-77.0+(3.0/50.0*(s1-1)), 45.0)), 4326)
from (select generate_series(1,50) as s1) as foo;

– node the grid so we can use it
select pgr_nodenetwork(‘ddunnoded’,0.000001);

– cat m/sec kph mph
– 1 25 90 56
– 2 18 65 40
– 3 15 54 33
– 4 10 36 22
– 5 5 18 11

– copy the noded table into a table we can use for a graph
– and add the required columns
create table ddnoded2 (
gid serial not null primary key,
id integer,
name text,
source integer,
target integer,
dir_travel character(1),
speed_cat character(1),
roundabout character(1) default ‘N’,
tunnel character(1) default ‘N’,
bridge character(1) default ‘N’,
len_m float8,
cost float8
);
select addgeometrycolumn(‘ddnoded2’, ‘the_geom’, 4326, ‘LINESTRING’, 2);

insert into ddnoded2 (id, name, dir_travel, speed_cat, len_m, cost, the_geom)
select a.id,
name,
dir_travel,
speed_cat,
st_length2d_spheroid(a.the_geom, ‘SPHEROID[“GRS_1980”,6378137,298.257222101]’) as len_m,
st_length2d_spheroid(a.the_geom, ‘SPHEROID[“GRS_1980”,6378137,298.257222101]’) / case when speed_cat=‘1’ then 25.0
when speed_cat=‘2’ then 18.0
when speed_cat=‘3’ then 15.0
when speed_cat=‘4’ then 10.0
else 5.0 end as cost,
a.the_geom
from ddunnoded_noded a, ddunnoded b
where a.old_id=b.id
order by a.old_id, a.sub_id;

– now create a topology
select pgr_createtopology(‘ddnoded2’, 0.000001, id:=‘gid’);

create table ddnoded2_restrictions (
id serial not null primary key,
n_via integer,
n_from integer,
n_to integer,
is_forbidden boolean,
to_way_id integer
);

– Total query runtime: 8080 ms.
EOF

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

19

Hi Steve,

I’m back to the TSP work.

select * from pgr_tsp(
(select dmatrix::float8
from pgr_vidstodmatrix(
‘select id, source, target, cost, reverse_cost from ways’,
pgr_pointstovids(
pgr_texttopoints(‘-8.6637,40.6403;-8.6406,40.6539;-8.6923,40.6312;-8.7411,40.6312’, 4326),
‘ways’),
true, true, true) as dmatrix),
1
);

The query above return the following results:

seq;id
0;1
1;0
2;3
3;2

Computing pgr_dijkstra for that sequence (i.e., 1 >> 0 >> 3 >> 2) I get:

1975.82193954407

7098.18548705077

6299.05064340774

However, this is not the right sequence, which I can prove computing pgr_dijkstra for the sequence 1 >> 0 >> 2 >> 3:

1975.82193954407
2723.3692284753
4374.81625857547

Do you have any idea of whatever might be wrong here?

Thanks for you help! :slight_smile:

···

–
Helder Alves