[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](http://afrispatial.co.za)
t: 0218620670
c: 0845965680
f: 0866164820
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@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users
Hi Gavin,
I don’t know anyone who has tried it with more than 40 points. It’s just a guess, but the pgRouting TSP is using a genetic algorithm library. Eventually the evaluation of each generation isn’t good for a large amount of points.
But as Steve mentioned, there might be special algorithms for your use case. Unfortunately they are not available in pgRouting. I think they were even on the GSoC ideas list already, but never chosen by a student.
Daniel
On Tue, May 1, 2012 at 4:58 AM, Stephen Woodbridge <woodbri@swoodbridge.com> wrote:
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@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users
–
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
Web: http://georepublic.de