[GIS] Can anyone explain me the TSP pgRouting function

pgroutingpostgistravelling salesman

I have no problems using Dijkstra or A* functions, but when I try to run TSP, I really don't know where to start.

What I'm, trying is to get the 'best route' to link four points (typical TSP problem), but I do not know how to implement this.
According the documentation:

SELECT seq, id1, id2, round(cost::numeric, 2) AS cost
FROM pgr_tsp('SELECT id, x, y FROM vertex_table ORDER BY id', 6, 5);

My questions are:

What means "cost::numeric" and specially "::"? I have seen it before, but still don't know what it is.
Should I have another table with the points with x and y fields? Because if tsp refers to a "vertex table" that I supose will be the point table, where is the edge table (e.g streets) that I queried with Dijkstra?
And what means that 5 and 6?

Sorry if this a strange question, but I'm trying to run this function but I can't do it, and I don't find any documentation but the official docs, (that I don't understand).

Best Answer

With pgRouting 2.0 there are two different TSP functions, see: http://docs.pgrouting.org/2.0/en/src/tsp/doc/index.html#pgr-tsp

The first one has as first argument a SQL statement (that's the one you are using), the second one requires a distance matrix.

The advantage of the distance matrix is, that it's up to you, how exact you want to calculate the distances. The first function only calculates the euclidean distances.

So in your case you select first all points you want to visit as the first argument, where you must know for each point its id and coordinates: SELECT id, x, y FROM vertex_table.

The second argument is the start point ID, which must be also part of your "SELECT" before, and the third argument is optional. It's the ID of the last point to visit.

So in your example you first select all points with id, x and y attributes (must also return ID 5 and 6), the first point to visit must be ID 5 and the last point to visit is point 6.

cost::numeric that you cast the cost attribute to be of type numeric.

Related Solutions

[GIS] How to use the pgRouting TSP function

According to the examples and the documentation, you should only be loading the five nodes you are interested in in the select query, so I added a where clause to your select query. You also had a trailing comma, following the list of ids in parameter two that I removed.

So give this a try and see if it works better:

SELECT vertex_id
FROM tsp('SELECT id as source_id, lon AS x, lat AS y 
          FROM point_layer where id in (23,221,63,432,335)','23,221,63,432,335',63);

Here is a link to the doc: http://pgrouting.org/docs/1.x/tsp.html

[GIS] driving time to the nearest facility using pgrouting

Here is my solution (it can be improved for sure!). I wrote this function:

RETURNS TABLE(node integer, cost double precision) AS
$BODY$
DECLARE
    node integer;
BEGIN
FOR node IN SELECT DISTINCT (temp.node_id) FROM temp 
-- WHERE node_id = 6626 (temporary filter to speed up testing)
LOOP
RETURN QUERY EXECUTE
'SELECT pgr_drivingdistance.id1, pgr_drivingdistance.cost AS cost
 FROM pgr_drivingdistance(''
      SELECT gid AS id,
          source::integer,
          target::integer,
          avg_cost_min::double precision AS cost
      FROM ways'',
      ' || node || ' ,
      60,
      false,
      false)';
END LOOP;
RETURN;
END;
$BODY$

and this script to be run for minimum driving distance calculation:

-- create table (temp) with closest network node to points included in facilities table (facs)
DROP TABLE IF EXISTS temp;
CREATE temp TABLE temp AS (SELECT facs.id AS fac_id, 
  (SELECT nodes.id AS node_id 
   FROM  ways_vertices_pgr as nodes
   ORDER BY facs.geom <#> nodes.the_geom LIMIT 1)
FROM facs
-- WHERE fac_type = --use this line as filter on facility types
ORDER BY fac_id)
;
-- use isochrones_fac function to calculate driving time from nodes in temp table
-- aggregate by node returning minimum value and join geometry from the node table

CREATE TABLE posts_mincost -- modify output table name
AS (SELECT output.id,
    output.min_cost,
    vertices.the_geom
   FROM (SELECT isochrones_fac.node AS id,
            min(isochrones_fac.cost) AS min_cost
           FROM isochrones_fac() isochrones_fac(node, cost)
          GROUP BY isochrones_fac.node
          ORDER BY isochrones_fac.node) output,
    nodes_gbe AS vertices
  WHERE output.id = vertices.id);

It seems working good (about 15 seconds for 100 facilities, 58000 nodes, max 60 min of driving distance). I'm quite happy considering my sql programming level!! ;)

This is a snapshot of an output of a spline interpolation:

Any further suggestion is welcome,of course!!

Best Answer

Related Solutions

[GIS] How to use the pgRouting TSP function

[GIS] driving time to the nearest facility using pgrouting

Related Question