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

Stephen Woodbridge woodbri at swoodbridge.com
Tue Nov 5 18:15:32 PST 2013


On 11/5/2013 7:53 PM, Helder Alves wrote:
> It's working! Thanks! :-)

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 at swoodbridge.com <mailto:woodbri at 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! :-)
>
>         Can you help me with this?
>
>         Thanks!
>
>
>
>
>
>         --
>         Helder Alves
>         +351912384076 <tel:%2B351912384076>
>
>
>         On Wed, Oct 9, 2013 at 5:26 PM, Stephen Woodbridge
>         <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.com>
>         <mailto:woodbri at swoodbridge.__com
>         <mailto:woodbri at 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 at lists.osgeo.org
>         <mailto:pgrouting-dev at lists.osgeo.org>
>         <mailto:pgrouting-dev at lists.__osgeo.org
>         <mailto:pgrouting-dev at 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 at lists.osgeo.org
>         <mailto:pgrouting-dev at lists.osgeo.org>
>         <mailto:pgrouting-dev at lists.__osgeo.org
>         <mailto:pgrouting-dev at 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 at lists.osgeo.org <mailto:pgrouting-dev at 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 at lists.osgeo.org <mailto:pgrouting-dev at 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 at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>



More information about the pgrouting-dev mailing list