[pgrouting-users] tsp strange results

[Stephen Woodbridge]

Hi Gavin,

I'm not sure the TSP is the right solution for this. I think you might 
want to be looking for "The Chinese Postman Problem" [1]. Your problem 
has the added complexity of needing to visit meters on both sides of the 
street. I think Eulerian Cycles [2] that are used for example to do snow 
plow planning might be more suited to your needs because you have to 
plan at least one pass down each side of the street. That said, neither 
of these are available in pgRouting.

I have not tried to use the pgRouting TSP code, although I have used 
other solvers. Regardless, I'm unsure of the issues related to pgRouting 
TSP.

If this is something that could be funded and you are interested please 
contact me off list to discuss.

-Steve W


[1] http://staff.ustc.edu.cn/~xujm/Graph16.pdf
[2] 
http://www.freewebs.com/duncanroper/Euler_and_Koinisberg_Bridges_Roper.pdf

On 4/30/2012 3:20 PM, Gavin Fleming wrote:
> [apologies for repeat - hopefully screenshots come through this time]
>
> 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.:
>
>
>
>
> [1] http://www.tsp.gatech.edu/concorde/index.html
>
> --
> regards
>
> Gavin
>
> Gavin Fleming
> http://afrispatial.co.za
> t: 0218620670
> c: 0845965680
> f: 0866164820
>
>
>
>
> _______________________________________________
> Pgrouting-users mailing list
> Pgrouting-users at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-users