So, here is another look at this problem, by looking at the data the needs to flow through the problem.
I am ambivalent about using the ARRAY objects but they are convenient for representing ordered collections of objects and specifically the dmatrix data.
Solve TSP based on Euclidean distances:
1. list of N points to optimize using TSP
REC(seq, x, y) or ARRAY[P1, P2, P3, ..., PN]
2. compute euclidean dmatrix from points
ARRAY[
ARRAY[0.0, d2, d3, d4, ..., dN],
ARRAY[d1, 0.0, d3, d4, ..., dN],
ARRAY[d1, d2, 0.0, d4, ..., dN],
ARRAY[d1, d2, d3, 0.0, ..., dN],
...,
ARRAY[d1, d2, d3, d4, ..., 0.0]
]
3. solve TSP and get order list of dmatrix indices
ARRAY[i1, i2, i3, i4, ..., iN]
4. return ordered list of edge pairs
REC(1, n1, n2, LINESTRING(P[i1], P[i2]))
REC(2, n2, n3, LINESTRING(P[i2], P[i3]))
REC(3, n3, n4, LINESTRING(P[i3], P[i4]))
REC(4, n4, n5, LINESTRING(P[i4], P[i5]))
...
REC(N, nN, n1, LINESTRING(P[iN], P[i1]))
The above is the simple case. We don't need to compute routes. This would also have application of solving non-routing optimization problems where you have a distance/cost matrix and need to optimize the path through it.
Solve TSP based on Driving Distance:
1. list of N points to optimize using TSP
REC(seq, x, y) or ARRAY[P1, P2, P3, ..., PN]
2. map points to list of N node_ids
ARRAY[N1, N2, N3, ..., NN]
3. compute dmatrix by routing between nodes
this step needs to keep more information like the list of edges for
for each route in the matrix, so we can reconstitute the optimized
route in the final step. This needs some error handling to deal with
duplicate nodes, unreachable nodes (ie: failure to route to or from
a node).
ARRAY[
ARRAY[0.0, d2, d3, d4, ..., dN],
ARRAY[d1, 0.0, d3, d4, ..., dN],
ARRAY[d1, d2, 0.0, d4, ..., dN],
ARRAY[d1, d2, d3, 0.0, ..., dN],
...,
ARRAY[d1, d2, d3, d4, ..., 0.0]
]
4. solve TSP and get order list of matrix indices
ARRAY[i1, i2, i3, i4, ..., iN]
5. return ordered list of routes
REC(1, n1, n2, route_from_dmatrix(n1, n2))
REC(1, n2, n3, route_from_dmatrix(n2, n3))
REC(1, n3, n4, route_from_dmatrix(n3, n4))
REC(1, n4, n5, route_from_dmatrix(n4, n5))
...
REC(1, nN, n1, route_from_dmatrix(nN, n1))
For this we need to cache the computed routes so we don't compute them twice. I think that this can get done using a WITH clause to cache the routes in a temp table and use a aggregate to assemble the dmatrix. Something like:
WITH distances (i, j, dist, route) as
select * from compute_routes(node_ids, ...)
select * from TSP(make_dmatrix_symmetric(i, j, dist));
There are also some optimizations that can be done if we are working with symmetric case vs a non-symmetric case.
Anyway, this is as far as I have gotten try to look at how the data needs to flow between the various sub processes to generate a result.
Thoughts,
-Steve