[pgrouting-users] tsp strange results

[Gavin Fleming]

Hi all

I successfully recompiled tsp to accept > 40 nodes. On a sample area
with 420 water meters for which I need an optimum sequence for a meter
reader to walk, tsp() took 2h to run. It didn't fail but produced
unusable output.

Should I not expect reliable results with pgRouting tsp with this number
of nodes or am I missing something?

I think this might be a case where the internodal cost matrix needs to
be derived first from the network before tsp is solved? and perhaps
substituting gaul with something like Concorde [1]?

This is the network with meters:



This is the tsp solution:



and this is the tsp_dijkstra (and tsp_astar) result:



For comparison here is the GRASS v.net.salesman solution, which took 2
min. (My only problem here is I don't know how to get the sequence out):




[1] http://www.tsp.gatech.edu/concorde/index.html

-- 
regards

Gavin

Gavin Fleming
http://afrispatial.co.za
t: 0218620670
c: 0845965680
f: 0866164820