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