[pgrouting-dev] Building some tools to work with TSP
Helder Alves
helderalvespt at gmail.com
Tue Nov 5 16:53:22 PST 2013
It's working! Thanks! :-)
--
Helder Alves
+351912384076
On Mon, Nov 4, 2013 at 6:42 PM, Stephen Woodbridge
<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 &&
>> '0103000020E610000001000000050000002E34D769A4651FC05EBA490C02
>> 0344402E34D769A4651FC0492EFF21FD2E444076ABE7A4F78D1DC0492EFF
>> 21FD2E444076ABE7A4F78D1DC05EBA490C020344402E34D769A4651FC05E
>> 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
>>
>>
>> On Wed, Oct 9, 2013 at 5:26 PM, Stephen Woodbridge
>> <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>;
>>
>>
>> "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>
>>
>> ) 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>
>> 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
>>
>>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20131106/5a1fe1ae/attachment.html>
More information about the pgrouting-dev
mailing list