[pgrouting-dev] Building some tools to work with TSP
Stephen Woodbridge
woodbri at swoodbridge.com
Tue Nov 12 12:23:10 PST 2013
On 11/12/2013 2:51 PM, Helder Alves wrote:
> 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.
OK, when you make your distance matrix, the values in it are based on
the cost function that you use to generate it.
So for example it you have two columns in your edge table, like
cost_distance and cost_time, then when you create your distance matrix
and select the edges using cost_time as cost, then your distance matrix
is based on time. The units are whatever you use in the columns.
Likewise if you build your matrix with cost_distance as cost then your
distance matrix is based on the cost_distance values in whatever units
you used for that column.
TSP ONLY orders the nodes, if you need the routes between the nodes then
those have to be computed again based on the ordered nodes.
I say "again", because we computed them internally when we computed the
distance matrix. But these were not cached anywhere, so they will have
to be computed again after the TSP has ordered the nodes.
I have been side tracked, looking into whether or not I can integrate a
local OSRM instance into pgrouting because if you don't need the dynamic
graph definition, ie: you can live with a static graph definition, then
OSRM would allow for some significant performance gains in computing
distance matrices and routes.
I have also looked at some additional wrapping of the TSP and routing
with an eye toward caching the routes generated in dmatrix creation for
later use to generate the routes.
So the bottom line is you are needing the stuff I am developing. I need
it also, but it takes time to design and code stuff, especially while
putting out other fires. And all the code (whatever that might turn out
to be) is not there yet.
-Steve
> 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 <mailto: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 <tel:%2B351912384076>
>
>
> On Mon, Nov 4, 2013 at 6:42 PM, Stephen Woodbridge
> <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.com>
> <mailto: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> <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>>
> <mailto:woodbri at swoodbridge.
> <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>
> <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>
> <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>>
> <mailto:pgrouting-dev at lists.
> <mailto:pgrouting-dev at lists.>____osgeo.org <http://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>__>
>
>
> <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>>
> <mailto:pgrouting-dev at lists.
> <mailto:pgrouting-dev at lists.>____osgeo.org <http://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>__>
>
>
> <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>
> <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