[pgrouting-dev] Building some tools to work with TSP
Stephen Woodbridge
woodbri at swoodbridge.com
Sun Nov 10 06:40:42 PST 2013
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! :-)
>
> --
> 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