pgr_tsp returning weird results

[zimmicz]

Hi, I'm a pgRouting newbie with postgres 9.4, postgis 2.2 and pgrouting 2.0 installed. I used osm2pgrouting to import data for the Czech Republic and used the default mapconfig xml.

osm2pgrouting \
    -file czech-republic-latest.osm" \
    -conf "/usr/share/osm2pgrouting/mapconfig_for_cars.xml" \
    -dbname mzi_osm_routing \
    -user zimmi \
    -host localhost \
    -prefixtables osm_ \
    -clean &

Everything went fine, I got osm_ways and osm_ways_vertices_pgr tables. I tried the dijkstra algorithm first with the following sql statement:

SELECT the_geom 
FROM osm_ways
WHERE gid IN (
    SELECT id2
    FROM (
        SELECT * 
        FROM pgr_dijkstra('
            SELECT gid as id, 
                source::int4, 
                target::int4, 
                maxspeed_forward::float8 as cost 
                FROM osm_ways', 
            80855, 
            123778, 
            false, 
            false
        )
    ) a
);

Worked fine and the result viewed in QGIS was correct. However, when I run he traveling salesman problem algorithm, I got really weird result.

SELECT the_geom 
FROM osm_ways
WHERE gid IN (
    SELECT id2
    FROM (
        SELECT * 
        FROM pgr_tsp('
            SELECT id::integer, 
                ST_X(the_geom) as x,
                ST_Y(the_geom) as y
                FROM osm_ways_vertices_pgr
                WHERE id in (140657, 140777, 248013, 20559)', 
            140657
        )
    ) a
);

See the screenshot below, those squares represent edges. Note that all the points lie near to each other (thus the only one being displayed), yet edges from different locations come as a result. When I checked one of the displaced edges, neither target nor source were of the same value as my initial WHERE condition.

Am I missing something?

[cvvergara]

@zimmicz I wonder if you can install 2.1, and do a build installation. from https://github.com/pgRouting/pgrouting click on the download button and follow this instructions: http://docs.pgrouting.org/2.1/doc/src/installation/build.html#for-linux

[zimmicz]

Hoped I could get away without building :) I'll try asap. Is it possible to have two different versions of pgrouting, or do i have to remove 2.0? Thanks.

Update: built pgrouting 2.1 and updated the extension with ALTER EXTENSION pgrouting UPDATE TO "2.1.0";. The result of tsp is still the same.

[woodbri]

You should be able to do:

create extension pgrouting version 2.0.0;
--or
create extension pgrouting version 2.1.0;

[woodbri]

Two comments on your pgr_trsp query:

1. why are you only including 4 segments and not the whole graph like with dijkstra
2. you do not have enough arguments to the function pgr_costResult[] pgr_trsp(sql text, source integer, target integer, directed boolean, has_rcost boolean [,restrict_sql text]);

[cvvergara]

@zimmicz I think for the moment we don't have a package for ubuntu, so it has to be built

[zimmicz]

@woodbri

1. because I'm not working with edges, I'm working with nodes.
2. 2.0 pgr_tsp takes 3 arguments, the last one being optional.

@cvvergara see my update above, I upgraded to 2.1.0, still no luck. Is there something wrong with the query itself?

[woodbri]

@zimmicz Sorry miss read the problem as trsp not tsp.

So for tsp, you give it a list of locations like you are doing. What it returns, is an optimized list of vertices (based on Euclidean distances) of the solution. It does not return routes only a list of node ids. If you want the routes for the solution, you will need to iterate through pairs of the ordered vertices and compute the routes.

[zimmicz]

@woodbri Oh that's so obvious! I'm such a dumbhead :-/ Given any number of nodes, tsp gives me the order of their visit, but it doesn't give edges to go through. So the next step should probably be to send the matrix into the dijkstra or another algorithm, to get the result, right?

[cvvergara]

@woodbri Yeah, trsp and tsp are quite annoying for reading... I always also get messed up. I will suggest name change for future versions. If someone likes short naming they can just wrap it in a function.

[cvvergara]

@zimmicz So you got an order say: 140657, 140777, 248013, 20559 was your result

• choice (1)

pgr_dijkstra( <edges_sql>, 140657, 140777);
pgr_dijkstra( <edges_sql>, 140777, 248013);
pgr_dijkstra( <edges_sql>,  248013, 20559);

• choice for version 2.2 Right now I am working on a:

pgr_dijstraViaVertices( <edges_sql> , ARRAY[140657, 140777, 248013, 20559])

• choice (2) use trsp, but @woodbri has more experience on that. @woodbri can you explain?

[zimmicz]

Thank you, I'm closing this.

[woodbri]

You can probably do something like this:

select * from pgr_dijkstra( <edges_sql>::text,  (SELECT array_agg(id) as ids
  FROM pgr_tsp('{{0,1,2,3},{1,0,4,5},{2,4,0,6},{3,5,6,0}}'::float8[],1,2)));

where you put in real data for your vertices.