[pgrouting-dev] Building some tools to work with TSP
Helder Alves
helderalvespt at gmail.com
Tue Nov 12 15:45:46 PST 2013
OK, Steve... Thanks for the explanation!
It helps a lot because one of my doubts was precisely that need to compute
the routes again, after those same routes to have been computed already. I
thought I was missing some point there but now I understand that is the
only way.
I'll continue my exploration into pgRouting world for a couple of weeks
more and after that I must come up with a plan where I'll try to find out a
way of contributing somehow to your RFC's efforts, as clearly they are
headed to the same features I need.
--
Helder Alves
+351912384076
On Tue, Nov 12, 2013 at 8:23 PM, Stephen Woodbridge <woodbri at swoodbridge.com
> wrote:
> 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
>>
>>
> _______________________________________________
> 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/e63a42b1/attachment-0001.html>
More information about the pgrouting-dev
mailing list