[pgrouting-dev] New TSP algorithm and refactoring - take 2

[Stephen Woodbridge]

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