[pgrouting-dev] Building some tools to work with TSP

[Stephen Woodbridge]

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;

"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
) 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
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev