[pgrouting-users] tsp strange results

[Daniel Kastl]

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 at 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<http://staff.ustc.edu.cn/~xujm/Graph16.pdf>
> [2] http://www.freewebs.com/**duncanroper/Euler_and_**
> Koinisberg_Bridges_Roper.pdf<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<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 <Pgrouting-users at lists.osgeo.org>
>> http://lists.osgeo.org/**mailman/listinfo/pgrouting-**users<http://lists.osgeo.org/mailman/listinfo/pgrouting-users>
>>
>
> ______________________________**_________________
> Pgrouting-users mailing list
> Pgrouting-users at lists.osgeo.**org <Pgrouting-users at lists.osgeo.org>
> http://lists.osgeo.org/**mailman/listinfo/pgrouting-**users<http://lists.osgeo.org/mailman/listinfo/pgrouting-users>
>



-- 
Georepublic UG & Georepublic Japan
eMail: daniel.kastl at georepublic.de
Web: http://georepublic.de
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20120501/ac46adda/attachment.html