Re: [GRASS-user] traveling salesman problem in air
Martina Schäfer wrote: Interesting discussion!! I've created the centroids but unfortunately, the visibility network module repeatedly crashed (I am using GRASS 6.4 on Mac OS, but tried on Windows XP as well) with the message out of memory. I am new to GRASS, any advice how to deal with that? http://grass.osgeo.org/wiki/Bugs Moritz wrote: And for the possible need to check possibilities of reduction of memory usage in v.net.visibility. It shouldn't run out of memory, maybe it is some run away loop or incorrect malloc call? if this were raster maps I'd ask how big the region settings were. how much system RAM? how many centroids are we talking about? Hamish ___ grass-user mailing list grass-user@lists.osgeo.org http://lists.osgeo.org/mailman/listinfo/grass-user
Re: [GRASS-user] traveling salesman problem in air
Martina, On Wed, Apr 15, 2009 at 10:42 PM, Martina Schäfer martina.scha...@ebc.uu.se wrote: Interesting discussion!! I've created the centroids but unfortunately, the visibility network module repeatedly crashed (I am using GRASS 6.4 on Mac OS, but tried on Windows XP as well) with the message out of memory. The problem has been identified and fixed in 6.4.0svn, 6.5.svn and 7.svn. It was a memory leak where memory was allocated but not released: My test: Spearfish, using valgrind: v.net.visibility input=roads output=graph Original memory leak: ==3746== LEAK SUMMARY: ==3746==definitely lost: 18,522,763 bytes in 661,297 blocks. ==3746==indirectly lost: 396,532,048 bytes in 991,328 blocks. After fix: ==16713== LEAK SUMMARY: ==16713==definitely lost: 7,660 bytes in 44 blocks. ==16713==indirectly lost: 3,624 bytes in 8 blocks. There is still a tiny loss somewhere in the vector library but that's marginal (and released when the module exits). Options for you now: - update and compile from SVN - ask someone to compile for you :) - wait for the next release of 6.4.0. Thanks for reporting this. Ah, please report later if it now works for you. Best Markus ___ grass-user mailing list grass-user@lists.osgeo.org http://lists.osgeo.org/mailman/listinfo/grass-user
[GRASS-user] traveling salesman problem in air
Dear GRASS experts! I encountered an interesting problem and am curious about solutions. A helicopter company has got a file from a client regarding a forest inventory. The file contains 1430 polygons representing areas to be visited. Now we want to calculate the optimal route to visit all polygons. In contrast to a traveling salesman , we don't have a network of routes as the helicopter can fly everywhere. Would it be a solution to have the distance betweeen areas as the cost? I used a tool in MapInfo that connects successive closest points which worked very nice but not optimal. Anyone knows of other solutions? Regards, Martina ___ grass-user mailing list grass-user@lists.osgeo.org http://lists.osgeo.org/mailman/listinfo/grass-user
Re: [GRASS-user] traveling salesman problem in air
On 15/04/09 09:19, Wolf Bergenheim wrote: On 15.04.2009 10:05, Moritz Lennert wrote: On 15/04/09 08:55, Martina Schäfer wrote: Dear GRASS experts! I encountered an interesting problem and am curious about solutions. A helicopter company has got a file from a client regarding a forest inventory. The file contains 1430 polygons representing areas to be visited. Now we want to calculate the optimal route to visit all polygons. In contrast to a traveling salesman , we don't have a network of routes as the helicopter can fly everywhere. Would it be a solution to have the distance betweeen areas as the cost? I used a tool in MapInfo that connects successive closest points which worked very nice but not optimal. Anyone knows of other solutions? Maybe v.net.visibility to create a network and then v.net.salesman ? Exactly what I was going to suggest. the network created by v.net.visibility will connect all polygon nodes to all visible polygon nodes. The net will then consist of of these points plus the edges that make up the polygons. Depending on the size of the polygons and of the whole area, I imagine that this could be simplified by just using the centroids of the polygons, or ? Moritz ___ grass-user mailing list grass-user@lists.osgeo.org http://lists.osgeo.org/mailman/listinfo/grass-user
Re: [GRASS-user] traveling salesman problem in air
Yes, the centroids should be fine. it actually did not work to run v.net.visibility when I tried but I'll give it another try with the centroids. Thanks! Martina Moritz Lennert skrev: On 15/04/09 09:19, Wolf Bergenheim wrote: On 15.04.2009 10:05, Moritz Lennert wrote: On 15/04/09 08:55, Martina Schäfer wrote: Dear GRASS experts! I encountered an interesting problem and am curious about solutions. A helicopter company has got a file from a client regarding a forest inventory. The file contains 1430 polygons representing areas to be visited. Now we want to calculate the optimal route to visit all polygons. In contrast to a traveling salesman , we don't have a network of routes as the helicopter can fly everywhere. Would it be a solution to have the distance betweeen areas as the cost? I used a tool in MapInfo that connects successive closest points which worked very nice but not optimal. Anyone knows of other solutions? Maybe v.net.visibility to create a network and then v.net.salesman ? Exactly what I was going to suggest. the network created by v.net.visibility will connect all polygon nodes to all visible polygon nodes. The net will then consist of of these points plus the edges that make up the polygons. Depending on the size of the polygons and of the whole area, I imagine that this could be simplified by just using the centroids of the polygons, or ? Moritz ___ grass-user mailing list grass-user@lists.osgeo.org http://lists.osgeo.org/mailman/listinfo/grass-user
Re: [GRASS-user] traveling salesman problem in air
On 15/04/09 09:46, Martina Schäfer wrote: Yes, the centroids should be fine. it actually did not work to run v.net.visibility when I tried but I'll give it another try with the centroids. Keep us posted. This is an interesting application of these modules... Moritz ___ grass-user mailing list grass-user@lists.osgeo.org http://lists.osgeo.org/mailman/listinfo/grass-user
Re: [GRASS-user] traveling salesman problem in air
Sorry if I'm beside the point, but I insist, being myself interested in this topic... My suggestion of a delaunay triangle net to join polygons centroids seems to be totally beside the point :-( I would just like to know why. Probably sth I did not catch ? Thank you VB Le mercredi 15 avril 2009 à 18:04 +0200, Moritz Lennert a écrit : On 15/04/09 09:46, Martina Schäfer wrote: Yes, the centroids should be fine. it actually did not work to run v.net.visibility when I tried but I'll give it another try with the centroids. Keep us posted. This is an interesting application of these modules... Moritz ___ grass-user mailing list grass-user@lists.osgeo.org http://lists.osgeo.org/mailman/listinfo/grass-user ___ grass-user mailing list grass-user@lists.osgeo.org http://lists.osgeo.org/mailman/listinfo/grass-user
Re: [GRASS-user] traveling salesman problem in air
On 15/04/09 18:11, Vincent Bain wrote: Sorry if I'm beside the point, but I insist, being myself interested in this topic... My suggestion of a delaunay triangle net to join polygons centroids seems to be totally beside the point :-( I would just like to know why. Probably sth I did not catch ? Haven't thought this through completely, but: v.delaunay will only create links between centroids close to each other, whereas v.net.visibility will create links between all centroids. This leaves v.net.salesman with a larger option of paths to choose from. As we are not bound to any paths, this seems more appropriate to me. Does this sound convincing ? Moritz ___ grass-user mailing list grass-user@lists.osgeo.org http://lists.osgeo.org/mailman/listinfo/grass-user
Re: [GRASS-user] traveling salesman problem in air
On Wednesday 15 April 2009, Vincent Bain wrote: Don't know if it makes sense, but I would try v.delaunay to build a net between closest centroids (given that each centroid is roughtly centered on its area). Vincent That seems like a good judgement call, considering that the resulting network of connecting every centroid could become very large. This problem reminded me of a similar task, where we wanted to visit data loggers in the field and were not constrained to any existing 'network'. I found that a cost-surface (in this case accumulated slope gradient) gave us a nice constraint on how to use a simple network derived from v.delaunay. Some notes on that operation here: http://casoilresource.lawr.ucdavis.edu/drupal/node/698 Cheers, Dylan -- Dylan Beaudette Soil Resource Laboratory http://casoilresource.lawr.ucdavis.edu/ University of California at Davis 530.754.7341 ___ grass-user mailing list grass-user@lists.osgeo.org http://lists.osgeo.org/mailman/listinfo/grass-user
Re: [GRASS-user] traveling salesman problem in air
On 15.04.2009 23:42, Martina Schäfer wrote: Interesting discussion!! I've created the centroids but unfortunately, the visibility network module repeatedly crashed (I am using GRASS 6.4 on Mac OS, but tried on Windows XP as well) with the message out of memory. I am new to GRASS, any advice how to deal with that? Hmm... yes I can see how that can be a problem... How much memory does your computer have and how many centroids did you say you have? Have you tried with the area polygons instead? --Wolf -- :3 ) Wolf Bergenheim ( 8: ___ grass-user mailing list grass-user@lists.osgeo.org http://lists.osgeo.org/mailman/listinfo/grass-user
Re: [GRASS-user] traveling salesman problem in air
On 15/04/09 22:42, Martina Schäfer wrote: Interesting discussion!! I've created the centroids but unfortunately, the visibility network module repeatedly crashed (I am using GRASS 6.4 on Mac OS, but tried on Windows XP as well) with the message out of memory. I am new to GRASS, any advice how to deal with that? I really want to see if this works, so I will continue trying! Well, this seems to be an argument for the v.delaunay approach... And for the possible need to check possibilities of reduction of memory usage in v.net.visibility. Moritz ___ grass-user mailing list grass-user@lists.osgeo.org http://lists.osgeo.org/mailman/listinfo/grass-user
