[pgrouting-dev] New TSP algorithm and refactoring

[Stephen Woodbridge]

Hi All,

Here is collection of ideas that have been bouncing around in my head 
regarding the TSP. There are a couple motivating factors to this:

1. eliminate the GAUL dependency
    I have a public domain simulated annealing algorithm that is very
    fast and very small (a single C file).

2. refactor the code into modules/layers that can be access separately
    for example it would be nice to solve TSP problem independent of
    any routing based on just a cost or distance matrix.

So I'm think of something like this:

create function tsp(dist double precision[][])
    returns integer[]

create function tsp(sql text)
    returns integer[]

Where the distance matrix "dist" is the input. I'm not sure if it is 
better to use arrays, or records as input, or to make it a set returning 
function the returns records of (seq, index). "seq" could be used to 
force the order if needed, and the "index" would be the row numbers in 
the matrix.

In set theory, there is no guarantee of record order with an explicit 
ORDER BY. Using and ARRAY[][] would allow us to preserve order but it is 
more awkward to work with.

Anyway, some ideas are:

-- build a distance set based on euclidean distance for the set of node

create function build_distance_matrix(node_ids[])
    returns REC(n1, n2, dist, edges[])

-- build a distance set using method and edge_table for nodes
-- this probably needs more args for cost, rcost, turn restrictions
-- etc.

create function build_distance_matrix(method, edge_table, node_ids[])
    returns REC(n1, n2, dist, edges[])

Still thinking this through, but what I want to end up with is a query 
like this pseudo query

with input as select array[n1, n2, n3, ...]
      dmatrix as select *
                   from build_dmatrix('dijkstra', 'myedges', input)
select b.seq, b.node1, b.node2, b.dist, b.edges[]
   from
     ( select rowid from tsp(dmatrix) ) a,
     ( select * from unnest(dmatrix) ) b
   where
         b.seq=a.rowid;

This assumes:

dmatrix[][] looks like:

ARRAY[
   ARRAY[seq, node1, node2, dist, edges[]],
   ...
]

input is an array of the nodes that we want to make a tour of.

Also if you just have an array of distances and you can feed it to tsp 
along with the nodes and it will solve it with any routing.

I would like input back from people that have used the existing TSP and 
anyone that has some thoughts on these ideas and how to best structure 
the queries.

Thanks,
   -Steve