3

I have created the "ways" (=edges) and "ways_vertices_pgr" (=nodes) tables from OSM road data with osm2pgrouting in PostGIS. I work with this data in QGIS.

structure of table "ways"

structure of table "ways_vertices_pgr"

Given a set of ids from the "ways_vertices_pgr" table I would like to tackle the following task:

  • perform a travelling salesperson problem
  • create a vector layer that represents the result

So far I have managed to create a cost matrix with pgr_dijkstraCostMatrix, and pass it to the pgr_TSP function.

SELECT seq, node, the_geom FROM pgr_TSP(
    $$
    SELECT * FROM pgr_dijkstraCostMatrix(
        'SELECT gid AS id, source, target, cost, reverse_cost FROM ways',
        (
            SELECT ARRAY[9769, 20604, 48398, 42533, 49819, 41141, 45520] node_array
        ),
        directed := false
    )
    $$,
    start_id := 9769,
    randomize := false
) as res
JOIN ways_vertices_pgr
ON ways_vertices_pgr.id = res.node;

The result is the sequence, in which the nodes should be travelled:

result of pgr_tsp

From here I am stuck.

How do I connect the dots, to create a full path from this which can be represented as a vector layer?

My naive approach is to use pgr_dijkstra on every segment of the path and then create a large table from the result. It is a real pain to implement this in PostgreSQL, though and I haven't managed to do that. This approach seems to be too complicated and not very elegant, anyways.

  • a small leap for convenience would be to use pgr_dijkstraVia, with your node ids in seq order as array. that still lacks a certain elegance, since it's adding another call to the routing engine (which, if use right, is blazingly fast, so not to worry much), but the alternative would be to join the edge table on ambiguous node AND LEAD(node) = source OR target constructs. – ThingumaBob May 24 at 7:42
2

Use this query to get the route for the sequence of given nodes.

select fd.seq as seq,
       fd.geo as geo
from   (
  SELECT ROW_NUMBER() OVER (ORDER BY now() ASC) AS seq,
         (
           SELECT (ST_Collect(foo.geo))
           FROM   (
             SELECT e.the_geom as geo
             FROM   pgr_dijkstra('SELECT gid as id,source, target, rcost_len AS cost FROM edges', orig, dest, false, false) AS r,
                    edges AS e
             WHERE r.id2 = e.gid
           ) AS foo
         ) AS geo
  FROM (
    select unnest(myarray[:array_upper(myarray,1)-1]) as orig,
           unnest(myarray[2:]) as dest
    from  (
      select array[79302,89789,55379] myarray
    ) b
  ) c
) fd
where fd.geo is not null; 

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.