[pgrouting-dev] Building some tools to work with TSP
Helder Alves
helderalvespt at gmail.com
Tue Nov 12 11:51:08 PST 2013
Hi Steve,
Thanks for the update!
I'm trying the new code but is not clear to me what's the best query to get
the total distance (in meters or kilometers) / time (in secs, minutes or
hours) for the route generated by TSP function (using a distance matrix)
and also how to get the geometry data needed to get that same route
represented as a QGIS layer.
I guess I'm missing something but after reading everything thoroughly I'm
not getting there...
--
Helder Alves
+351912384076
On Sun, Nov 10, 2013 at 2:40 PM, Stephen Woodbridge <woodbri at swoodbridge.com
> wrote:
> 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
>>
>>
> _______________________________________________
> 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/20131112/7591a2da/attachment-0001.html>
More information about the pgrouting-dev
mailing list