<div dir="ltr">Hi Steve,<div><br></div><div>Thanks for the update!</div><div><br></div><div>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.</div>
<div><br></div><div>I guess I'm missing something but after reading everything thoroughly I'm not getting there... </div><div><br></div><div class="gmail_extra"><div><div dir="ltr"><div>--</div><div>Helder Alves <br>
</div>+351912384076<br></div></div>
<br><br><div class="gmail_quote">On Sun, Nov 10, 2013 at 2:40 PM, Stephen Woodbridge <span dir="ltr"><<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
Hello Helder,<br>
<br>
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.<br>
<br>
Thank you for giving them a try.<br>
<br>
-Steve<div class="im"><br>
<br>
On 11/5/2013 7:53 PM, Helder Alves wrote:<br>
</div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div class="im">
It's working! Thanks! :-)<br>
<br>
--<br>
Helder Alves<br>
<a href="tel:%2B351912384076" value="+351912384076" target="_blank">+351912384076</a><br>
<br>
<br>
On Mon, Nov 4, 2013 at 6:42 PM, Stephen Woodbridge<br></div><div class="im">
<<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a> <mailto:<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.<u></u>com</a>>> wrote:<br>
<br>
You ways table does not have a column named "id" for now you might<br>
have to set up a view like:<br>
<br>
create view v_ways as select your_id_col as id, source, target, cost<br>
from ways;<br>
<br>
then try your query replacing 'ways' with 'v_ways'<br>
<br>
-Steve<br>
<br>
<br>
On 11/4/2013 11:31 AM, Helder Alves wrote:<br>
<br>
Hi Steve,<br>
<br>
select dmatrix::float8[]<br>
from pgr_vidstodmatrix(<br>
pgr_pointstovids(<br>
<br>
<br></div>
pgr_texttopoints('-7.50501,40.<u></u>__26310;-7.48864,40.17530;-7._<u></u>_49901,40.13950;-7.57596,40.__<u></u>12350;-7.61591,40.13230;-7.__<u></u>61935,40.13230;-7.67235,40.__<u></u>13580;-7.67087,40.13660;-7.__<u></u>66510,40.13860;-7.74559,40.__<u></u>15640;-7.74588,40.15730;-7.__<u></u>74746,40.15690;-7.74922,40.__<u></u>15540;-7.74926,40.15310;-7.__<u></u>73537,40.14230;-7.63556,40.__<u></u>18920;-7.64849,40.22630;-7.__<u></u>62354,40.25680;-7.62425,40.__<u></u>26280;-7.62223,40.25830;-7.__<u></u>62179,40.25680;-7.62116,40.__<u></u>25580;-7.64803,40.22390;-7.__<u></u>63916,40.20560;-7.63664,40.__<u></u>20250;-7.63767,40.19970;-7.__<u></u>63623,40.20000;-7.56974,40.__<u></u>26710;-7.49104,40.26500;-7.__<u></u>50473,40.26320',<br>
4326),<br>
'ways'),<br>
<br>
<br>
pgr_texttopoints('-7.50501,40.<u></u>__26310;-7.48864,40.17530;-7._<u></u>_49901,40.13950;-7.57596,40.__<u></u>12350;-7.61591,40.13230;-7.__<u></u>61935,40.13230;-7.67235,40.__<u></u>13580;-7.67087,40.13660;-7.__<u></u>66510,40.13860;-7.74559,40.__<u></u>15640;-7.74588,40.15730;-7.__<u></u>74746,40.15690;-7.74922,40.__<u></u>15540;-7.74926,40.15310;-7.__<u></u>73537,40.14230;-7.63556,40.__<u></u>18920;-7.64849,40.22630;-7.__<u></u>62354,40.25680;-7.62425,40.__<u></u>26280;-7.62223,40.25830;-7.__<u></u>62179,40.25680;-7.62116,40.__<u></u>25580;-7.64803,40.22390;-7.__<u></u>63916,40.20560;-7.63664,40.__<u></u>20250;-7.63767,40.19970;-7.__<u></u>63623,40.20000;-7.56974,40.__<u></u>26710;-7.49104,40.26500;-7.__<u></u>50473,40.26320',<div class="im">
<br>
4326),<br>
'ways')<br>
<br>
<br>
<br>
While running the query above, I got the error below.<br>
<br>
column "id" does not exist<br>
LINE 1: select id, source, target, cost from ways where<br>
the_geom && ...<br>
^<br>
QUERY: select id, source, target, cost from ways where<br>
the_geom &&<br>
<br></div>
'__<u></u>0103000020E6100000010000000500<u></u>__<u></u>00002E34D769A4651FC05EBA490C02<u></u>__<u></u>0344402E34D769A4651FC0492EFF21<u></u>__<u></u>FD2E444076ABE7A4F78D1DC0492EFF<u></u>__<u></u>21FD2E444076ABE7A4F78D1DC05EBA<u></u>__<u></u>490C020344402E34D769A4651FC05E<u></u>__BA490C02034440'::geometry<br>
CONTEXT: PL/pgSQL function<br>
pgr_vidstodmatrix(integer[],__<u></u>geometry[],text,double<div class="im"><br>
precision) line<br>
57 at FOR over EXECUTE statement<br>
<br>
<br>
I guess it's some kind of bug, which is something it may happen<br>
when we<br>
are testing something from the develop branch! :-)<br>
<br>
Can you help me with this?<br>
<br>
Thanks!<br>
<br>
<br>
<br>
<br>
<br>
--<br>
Helder Alves<br></div>
<a href="tel:%2B351912384076" value="+351912384076" target="_blank">+351912384076</a> <tel:%2B351912384076><div class="im"><br>
<br>
<br>
On Wed, Oct 9, 2013 at 5:26 PM, Stephen Woodbridge<br>
<<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a> <mailto:<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.<u></u>com</a>><br></div>
<mailto:<a href="mailto:woodbri@swoodbridge." target="_blank">woodbri@swoodbridge.</a>__<u></u>com<div class="im"><br>
<mailto:<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.<u></u>com</a>>>> wrote:<br>
<br>
Another common problem is orienting the returned edges so<br>
they match<br>
up end to end. For example:<br>
<br>
select st_astext(the_geom) from<br>
<br></div>
pgr_tsptrsp(pgr_texttopoints('<u></u>____2,0;2,1;3,1;2,2;4,1;4,2;2,<u></u>3;__3,__2',<div class="im"><br>
<br>
0), 'edge_table', true, true) a, edge_table b where<br>
a.id2=<a href="http://b.id" target="_blank">b.id</a> <<a href="http://b.id" target="_blank">http://b.id</a>><br>
<<a href="http://b.id" target="_blank">http://b.id</a>>;<br>
<br>
<br>
"LINESTRING(2 1,2 2)"<br>
"LINESTRING(2 2,3 2)"<br>
"LINESTRING(3 2,4 2)"<br>
"LINESTRING(4 1,4 2)" -- needs to be flipped<br>
"LINESTRING(3 1,4 1)" -- needs to be flipped<br>
"LINESTRING(2 1,3 1)" -- needs to be flipped<br>
"LINESTRING(2 1,2 2)"<br>
"LINESTRING(2 2,2 3)"<br>
"LINESTRING(2 2,2 3)" -- needs to be flipped<br>
"LINESTRING(2 1,2 2)" -- needs to be flipped<br>
"LINESTRING(2 0,2 1)" -- needs to be flipped<br>
"LINESTRING(2 0,2 1)"<br>
<br>
So I wrote a new function pgr_flipedges(ga geometry[]) that<br>
can be<br>
used like this:<br>
<br>
select st_astext(e) from (<br></div><div class="im">
select unnest(pgr_flipedges(array____<u></u>_agg(the_geom))) as e<br>
from<br>
<br></div>
pgr_tsptrsp(pgr_texttopoints('<u></u>____2,0;2,1;3,1;2,2;4,1;4,2;2,<u></u>3;__3,__2',<div class="im"><br>
<br>
0), 'edge_table', true, true) a,<br>
edge_table b<br></div>
where a.id2=<a href="http://b.id" target="_blank">b.id</a> <<a href="http://b.id" target="_blank">http://b.id</a>> <<a href="http://b.id" target="_blank">http://b.id</a>><div><div class="h5">
<br>
<br>
) as foo;<br>
<br>
"LINESTRING(2 1,2 2)"<br>
"LINESTRING(2 2,3 2)"<br>
"LINESTRING(3 2,4 2)"<br>
"LINESTRING(4 2,4 1)"<br>
"LINESTRING(4 1,3 1)"<br>
"LINESTRING(3 1,2 1)"<br>
"LINESTRING(2 1,2 2)"<br>
"LINESTRING(2 2,2 3)"<br>
"LINESTRING(2 3,2 2)"<br>
"LINESTRING(2 2,2 1)"<br>
"LINESTRING(2 1,2 0)"<br>
"LINESTRING(2 0,2 1)"<br>
<br>
Notice how all the edges have been flipped to return a<br>
continuous<br>
path from start to end of each adjacent segment in the path.<br>
<br>
-Steve<br>
All the mentioned code will eventually get checked into<br>
pgrouting<br>
2.1 development branch once it is stable and I have test<br>
cases and<br>
docs written for it.<br>
<br>
-Steve<br>
<br>
<br>
On 10/9/2013 10:29 AM, Stephen Woodbridge wrote:<br>
<br>
Hi all,<br>
<br>
I have been playing with some tools to allow me to<br>
integrate TSP<br>
optimization into a web application. I thought I would<br>
share<br>
what I have<br>
come up with for comments. One of the things I did was<br>
to try<br>
and break<br>
down the process into reusable modular functions. For<br>
example<br>
there are<br>
two functions to compute the distance matrix based on<br>
either<br>
Euclidean<br>
or kdijkstra distances. One could add other functions<br>
to compute<br>
them<br>
based on other algorithms. Also each function does one<br>
conversion so it<br>
is simple to understand and easy to test or replace<br>
with another<br>
function that does the transformation in a different<br>
way. Then<br>
the final<br>
function glues all the pieces together to get the final<br>
result.<br>
<br>
Goal:<br>
<br>
take a string or points like "x,y;x,y;x,y;..." and<br>
compute the TSP<br>
solution to order the points based on either Euclidean<br>
distance or<br>
network distances, then compute the route through the<br>
network<br>
and return<br>
the route geometry.<br>
<br>
Solution in progress:<br>
<br>
1. text to point geometry *<br>
pgr_texttopoints(pnts text, srid integer<br>
DEFAULT(4326))<br>
<br>
2. points to vertex ids *<br>
pgr_pointtoedgenode(edges text, pnt geometry, tol<br>
float8)<br>
pgr_pointstovids(pnts geometry[], edges text, tol<br>
float8<br>
DEFAULT(0.01))<br>
<br>
3. points to edge ids **<br>
<br>
4. points to [edge id, pct] **<br>
<br>
5. points to Euclidean distance matrix *<br>
pgr_points2dmatrix(pnts geometry[], OUT dmatrix double<br>
precision[],<br>
OUT ids integer[])<br>
<br>
6. vertex ids to kdijkstra distance matrix *<br>
pgr_vidstodmatrix(IN vids integer[], IN pnts<br>
geometry[], IN<br>
edges<br>
text, tol float8 DEFAULT(0.1), OUT dmatrix double<br>
precision[],<br>
OUT ids<br>
integer[])<br>
<br>
7. distance matrix to TSP to ordered list ***<br>
select * from pgr_tsp(<br>
(select dmatrix::float8[]<br>
from pgr_vidstodmatrix(<br>
pgr_pointstovids(<br>
<br></div></div>
pgr_texttopoints('2,0;2,1;3,1;<u></u>____2,2;4,1;4,2;2,3;3,2',<br>
0),<br>
'edge_table'),<br>
<br>
<br>
pgr_texttopoints('2,0;2,1;3,1;<u></u>____2,2;4,1;4,2;2,3;3,2', 0),<div class="im"><br>
<br>
'edge_table')<br>
),<br>
1<br>
);<br>
<br>
8. reorder vids based on ordered list *<br>
<br>
9. compute trsp for pairs of vids in ordered list *,!<br>
pgr_trsp(sql text, vids integer[], directed boolean,<br>
has_reverse_cost boolean, turn_restrict_sql text<br>
DEFAULT NULL::text)<br>
<br>
pgr_tsptrsp(pnts geometry[], edges text, directed<br>
boolean,<br>
has_reverse_cost boolean, tol float8 DEFAULT(0.1),<br>
turn_restrict_sql<br>
text DEFAULT NULL::text)<br>
<br>
select * from<br>
<br></div>
pgr_tsptrsp(pgr_texttopoints('<u></u>____2,0;2,1;3,1;2,2;4,1;4,2;2,<u></u>3;__3,__2',<div class="im"><br>
<br>
0),<br>
'edge_table', true, true);<br>
<br>
<br>
10. output results **<br>
<br>
NOTES:<br>
* - done<br>
** - not done<br>
*** - already part of 2.0<br>
! - computing a route through via points can be<br>
optimized in the<br>
C/C++<br>
code for better performance, but I currently just<br>
prototyped<br>
this up in<br>
plpgsql<br>
<br>
Thoughts,<br>
-Steve<br></div>
______________________________<u></u>_____________________<div class="im"><br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.<u></u>osgeo.org</a>><br></div><div class="im">
<mailto:<a href="mailto:pgrouting-dev@lists." target="_blank">pgrouting-dev@lists.</a>__<a href="http://osgeo.org" target="_blank"><u></u>osgeo.org</a><br>
<mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.<u></u>osgeo.org</a>>><br>
<a href="http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/____<u></u>mailman/listinfo/pgrouting-dev</a><br>
<<a href="http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/__<u></u>mailman/listinfo/pgrouting-dev</a><u></u>><br>
<br>
<<a href="http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/__<u></u>mailman/listinfo/pgrouting-dev</a><br>
<<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><u></u>>__><br>
<br>
<br>
______________________________<u></u>_____________________<br></div><div class="im">
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.<u></u>osgeo.org</a>><br></div><div class="im">
<mailto:<a href="mailto:pgrouting-dev@lists." target="_blank">pgrouting-dev@lists.</a>__<a href="http://osgeo.org" target="_blank"><u></u>osgeo.org</a><br>
<mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.<u></u>osgeo.org</a>>><br>
<a href="http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/____<u></u>mailman/listinfo/pgrouting-dev</a><br>
<<a href="http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/__<u></u>mailman/listinfo/pgrouting-dev</a><u></u>><br>
<br>
<<a href="http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/__<u></u>mailman/listinfo/pgrouting-dev</a><br>
<<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><u></u>>__><br>
<br>
<br>
<br>
<br></div><div class="im">
______________________________<u></u>___________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a> <mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.<u></u>osgeo.org</a>><br>
<a href="http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/__<u></u>mailman/listinfo/pgrouting-dev</a><br>
<<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><u></u>><br>
<br>
<br>
______________________________<u></u>___________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a> <mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.<u></u>osgeo.org</a>><br>
<a href="http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/__<u></u>mailman/listinfo/pgrouting-dev</a><br>
<<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><u></u>><br>
<br>
<br>
<br>
<br>
______________________________<u></u>_________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><br>
<br>
</div></blockquote><div class=""><div class="h5">
<br>
______________________________<u></u>_________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><br>
</div></div></blockquote></div><br></div></div>