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

[Stephen Woodbridge]

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