Hi Gavin,<div><br></div><div>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.</div>
<div>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.</div>
<div><br></div><div>Daniel</div><div><br></div><div><br><div class="gmail_quote">On Tue, May 1, 2012 at 4:58 AM, Stephen Woodbridge <span dir="ltr"><<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi Gavin,<br>
<br>
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.<br>
<br>
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.<br>
<br>
If this is something that could be funded and you are interested please contact me off list to discuss.<br>
<br>
-Steve W<br>
<br>
<br>
[1] <a href="http://staff.ustc.edu.cn/~xujm/Graph16.pdf" target="_blank">http://staff.ustc.edu.cn/~<u></u>xujm/Graph16.pdf</a><br>
[2] <a href="http://www.freewebs.com/duncanroper/Euler_and_Koinisberg_Bridges_Roper.pdf" target="_blank">http://www.freewebs.com/<u></u>duncanroper/Euler_and_<u></u>Koinisberg_Bridges_Roper.pdf</a><div class="im"><br>
<br>
On 4/30/2012 3:20 PM, Gavin Fleming wrote:<br>
</div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">
[apologies for repeat - hopefully screenshots come through this time]<br>
<br>
Hi all<br>
<br>
I successfully recompiled tsp to accept > 40 nodes. On a sample area<br>
with 420 water meters for which I need an optimum sequence for a meter<br>
reader to walk, tsp() took 2h to run. It didn't fail but produced<br>
unusable output.<br>
<br>
Should I not expect reliable results with pgRouting tsp with this number<br>
of nodes or am I missing something?<br>
<br>
I think this might be a case where the internodal cost matrix needs to<br>
be derived first from the network before tsp is solved? and perhaps<br>
substituting gaul with something like Concorde [1]?<br>
<br>
This is the network with meters:<br>
<br>
<br>
<br></div><div class="im">
This is the tsp solution:<br>
<br>
<br>
<br></div><div class="im">
and this is the tsp_dijkstra (and tsp_astar) result:<br>
<br>
<br>
<br></div><div class="im">
For comparison here is the GRASS v.net.salesman solution, which took 2 min.:<br>
<br>
<br>
<br>
<br></div><div class="im">
[1] <a href="http://www.tsp.gatech.edu/concorde/index.html" target="_blank">http://www.tsp.gatech.edu/<u></u>concorde/index.html</a><br>
<br>
--<br>
regards<br>
<br>
Gavin<br>
<br>
Gavin Fleming<br>
<a href="http://afrispatial.co.za" target="_blank">http://afrispatial.co.za</a><br>
t: 0218620670<br>
c: 0845965680<br>
f: 0866164820<br>
<br>
<br>
<br>
<br></div><div class="im">
______________________________<u></u>_________________<br>
Pgrouting-users mailing list<br>
<a href="mailto:Pgrouting-users@lists.osgeo.org" target="_blank">Pgrouting-users@lists.osgeo.<u></u>org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-users" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-<u></u>users</a><br>
</div></blockquote><div class="HOEnZb"><div class="h5">
<br>
______________________________<u></u>_________________<br>
Pgrouting-users mailing list<br>
<a href="mailto:Pgrouting-users@lists.osgeo.org" target="_blank">Pgrouting-users@lists.osgeo.<u></u>org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-users" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-<u></u>users</a><br>
</div></div></blockquote></div><br><br clear="all"><div><br></div>-- <br><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse">Georepublic UG & Georepublic Japan<br>eMail: <a href="mailto:daniel.kastl@georepublic.de" style="color:rgb(66,99,171)" target="_blank">daniel.kastl@georepublic.de</a><br>
Web: <a href="http://georepublic.de/" style="color:rgb(66,99,171)" target="_blank">http://georepublic.de</a></span><br>
</div>