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?
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 ?
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.
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
Le mercredi 15 avril 2009 à 08:55 +0200, Martina Schäfer a écrit :
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
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 ?
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 ?
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...
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.
To my mind v.delaunay was a way to /begin/ solving the problem, given
that proximity of surrounding points is already the criteria for
triangulation.
Whatever the right choice, it may be interesting, on a set of data, to
test both ways. In the case of a big network v.delaunay would provide a
lighter net, perhaps easier to handle for v.net.salesman.
Vincent
Le mercredi 15 avril 2009 à 18:23 +0200, Moritz Lennert a écrit :
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.
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:
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!
/Martina
------------------------------------------------------------------------
Moritz Lennert skrev:
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...
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?
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.
On Wed, Apr 15, 2009 at 10:42 PM, Martina Schäfer
<Martina.Schafer@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.
