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