Distance between lots of points on a map

Question

I have a 20,000 point array of gps locations.

They represent points on a forest path that need to be checked. I need to figure out how many km of forest path needs checking.

1. Group the points into routes.
2. Measure the shorted path of each route

Which algorithms should I consider and in which order.

Should I get the shortest path and break it up into routes or get the routes and then find the shorted path of each.

Answer 1

The question seems to be similar to a constrained vehicle routing problem. You can try a heuristic for example the savings algorithmus: http://neo.lcc.uma.es/vrp/solution-methods/heuristics/savings-algorithms/.

Answer 2

My other soulution:

This asumes you have more info which you did not have yet posted:

You probably have more info than just the coordinates of the points. Who has created this points? In your graphic, they look as they are on a path. Are they recorded while driving on that path with a vehicle? Then you have a time stamp, and therefore an order of points that are in sequnce, and thefore already are related to a path.

So the first step would be to assign the points to a path. (You also could draw all forest paths known as vectors to a digital map and match the points to the neareast path automatically)

You need the paths when you cannot directly reach each node on a straight line in betwwen them (e.g driving by vehicle or walking in wood when river avoids direct straight line path)

Then once you have a graph with nodes on links, use a minimum spaning tree to calculate the sum of path lengths in kilomter.

For visting the points you often will have to return to a branch, so then a travelling salesman algorith will help to give the kilomters needed to visit all nodes.

Answer 3

This solution asumes that you only have the points and don't know on which forest path th e points are, and in which order, etc.

I would try it this way:

1 connect each node with each other with a link, and as link weight use the distance (or better the number of seconds when going with 2km/h in meters in between the nodes: low speed asuming walking in the wood is slower then on a existimg forest road)

2 if the forest has diffuclties (mountains, vallley, river):

2a: ascent/descent: raise the link weight, using the altitudinal difference, look in outdoor planning resources, how many meters ascent has impact to travellling time. (300m could be one addionional hour as rough estimate)

2b: valley, river or other limits: either again raise the weight or remove the link if one cannot directly go from one point to the other. (e.g draw the valley as polygon and remove all links that cross the polygon)

Are there already paths/ forest roads in the wood?
Yes, draw them as links into the modell (graph), to use link weight, e,.g 5km/h walking speed.

Now you have a graph with nodes and the links with hopefully realistic link weight related to travelling speed between nodes.

Now use Shortes path (Dijkstras Algorithm) and travelling salesman algorithm.

If that all is to much work (could be some months for somebody with a degree in computer science) , plan it manually: draw a raster of 1000 x 1000m and let the human intelligence do its job.

Since 20.000 points which have to be checked by walking, needs a high effort, it is addionally worth to evaluate automatic planning versus human experience. Try both variants and look which is more efficient.

(I think that people with outdoor experience when having a good map with countour lines and the check points on it, will do a better job, asuming preorganizing by point two quadrants asignement and quadrants to people.)