Subscribe to this thread
Home - General / All posts - most efficient path through a number of points
Sev
439 post(s)
#30-Nov-19 06:24

Hi everyone, I have a drawing with approx 350 points (stumps in a paddock). I was looking for a way to create a line through each point from a nominated start/end point. I'm trying to find the most direct route (shortest) to achieve this. If it is doable, the machine taking the stumps out will save on time and of course diesel.

I thought a spanning tree might be what I was after, but it's not. Screenshot below.

Any thoughts welcomed!

Attachments:
2019-11-30_161949.jpg

Graeme

943 post(s)
#30-Nov-19 07:39

In 8, Transform / select shortest path.. looks as though it will do what you want. Doesn't look as though a comparable transform has made it into 9 as yest.

Sev
439 post(s)
#30-Nov-19 10:34

No that doesn't work, as I need to include every point. Selecting the shortest path will only select the shortest way between two points, and the lines need to already exist.......

rk
343 post(s)
#30-Nov-19 12:21

There was an example in m8 doc iirc. Search for Gabriel Network.

tjhb

8,950 post(s)
#30-Nov-19 14:02

I think rather than a Gabriel Network (too restrictive since an optimal route overall may need to use edges which are not shortest locally), what is needed is a full Delone Triangulation followed by Optimal Routing (probably not Optimal Routing (Visual) in this case because 350 points is a large number to click individually).

However, I doubt that this procedure would finish within reasonable time with 350 points. An optimal tour between 350 points might just be out of reach (not only with Manifold 8 tools).

This is an instance of the Travelling Salesman problem (Wikipedia) which is NP-hard. (I don't really understand what NP-hard means, other than "Are you sure you can afford to solve this problem?".)

However, that Wikipedia page also has a good discussion of approximate and heuristic solutions. E.g. the Christofides algorithm, building upwards from a Minimum Spanning Tree, looks well worth a crack. That would require extra coding, but might give an acceptably good tour for 350 points in a fairly short time.

Sev
439 post(s)
#30-Nov-19 21:33

I did look at Gabriel Network, but it doesn't produce the result I'm chasing. I hadn't realised it was such a difficult task. I'll follow those links you posted. Thanks!

adamw


8,764 post(s)
#02-Dec-19 16:11

(NP-hard means at least as hard as multiple known-hard problems which can be translated to each other, and for which there are no known solutions that complete in polynomial time = not in O(N^2), not in O(N^2048), not in any O(N^ a fixed power). It is possible that a solution to all these problems that completes in polynomial time still exists and just was not found yet, but that's just a theoretical possibility. As a practical matter, if a problem is NP-hard, the exact solution is typically a dumb exhaustive search between all possible solutions, and typically is impossible to find for all inputs except the tiniest ones.)

oeaulong

235 post(s)
#02-Dec-19 19:28

Adam,

Do you know of any more efficient solutions to the TSP if the rule of only one visit per stop was removed?

adamw


8,764 post(s)
#03-Dec-19 08:23

No, but one thing that immediately jumps to mind is that on networks that resemble real-world roads allowing repeat visits opens the door to hierarchical strategies (a sketch: take a big network, compute some kind of a characteristic distance between the nodes, collapse nodes closer than that distance into clusters, find shortest route within each cluster, find shortest route between clusters treating them as mega-nodes, repeat clusterization in either of the two last steps if the number of nodes is still too high to inspect all possible routes).

PS: Actually, after thinking about it more, it seems that allowing repeat visits does not make the problem easier: given a problem with repeat visits you can reduce it to a problem with no repeat visits by replacing edge weights (set the weight of an edge between A and B to the length of the shortest path between them). So, an exact solution remains infeasible. But maybe the approximate solutions can be reasoned out easier.

Sloots

442 post(s)
#30-Nov-19 17:45

This is the travelling salesman problem. Way to hard to solve for 350 points. However a reasonable suboptimal solution can be calculated using e.g. Genetic Algorithms.

I might try to develop an add in for M9 that handles this...


http://www.mppng.nl/manifold/pointlabeler

Sev
439 post(s)
#30-Nov-19 21:33

That'd be great if you were able Sloots....just let me know if you do!

mlinth
425 post(s)
#02-Dec-19 11:29

There's a discussion here on some approaches, with some queries and code.

http://www.georeference.org/forum/t121993.29#122074

mlinth
425 post(s)
#02-Dec-19 11:54

There's an open-source library of OR tools, including a solver for the traveling salesman problem.

https://developers.google.com/optimization/routing/tsp.html

You'd need to write code but Manifold can easily generate the inputs you need; they have an example solving a 280-point problem, so this might get you a good answer.

tonyw
547 post(s)
#02-Dec-19 18:30

Let me propose another approach that throws in the human element. How experienced in the machine operator? My suggestion uses the GIS after the fact as feedback to the operator. So this method relies on the human brain factoring in dozens of factors to decide the route. if you are clearing stumps, likely the trees grew naturally and probably grew in clumps or groves. A planted forest would have regular rows of stumps which is easy, you just follow the rows taking out stumps in one row or if the machine has sufficient reach, take out 3 or 4 rows at a time on the same pass. If the stumps occur in clumps, the operator can decide on the best route mentally factoring in least travel distance to the next clump of trees. Likely the operator will look ahead 3-4 clumps and optimize a short term route and a longer, more generalized route for the day. Other factors the operator will consider in their choice of route is where is their fuel supply to swing by before the tank runs dry, the terrain and obstacles if those are issues, a route that minimizes retracing steps, and where they want to start and end at the end of the day (presumably near their vehicle to go home).

Where the GIS comes in is if you track the machine's path with a GPS during the day, next morning you can provide the operator with a map showing his/her route the previous day. If the operator is open minded, they may learn and adapt and get more efficient by reducing back tracking and wasted movement. So more along the lines of time and motion studies.

If you are the machine operator, then I think is a great problem to solve! And if it was my paddock and my machine, I would pursue the problem just for the challenge.

The other thought is there may not be just one solution for shortest route. This sounds like an optimization problem. You would need to do a Monte Carlo simulation to try a large number of routes because each choice you make on which clump to go to next affects the next best route for many future segments.

Further, if this was my paddock and my machine, I would try each day to best my ratio of stumps removed per lineal travel distance or litres of fuel consumed.

ColinD


1,934 post(s)
#02-Dec-19 19:51

if a problem is NP-hard, the exact solution is typically a dumb exhaustive search between all possible solutions

Given that, why not give the operator a range finder, start at the stump nearest the paddock entry point then move to the next nearest stump, and so on.


Aussie Nature Shots

Sev
439 post(s)
#04-Dec-19 05:30

I'm not sure that would solve it Colin, if there were a number of very close stumps that this path followed, you may track past ones that would be more efficient to grab along the way...(that's just me musing, but I think you could end up doing a lot more km's that way)..

Sev
439 post(s)
#04-Dec-19 05:27

Thanks for the input Tony, the screenshot I attached in my first post is actually the job on hand, so it's all over the place, not really clumps etc...it's over approx 200ha.

We could simply have a go, and load the points into a gps and track around making sure we attempt to be as efficient as possible (likely outcome after this post!). I just thought there may be an algorithm that may make the path more efficient...apparantly not, but I'm enjoying the insights and learning at the same time.

tonyw
547 post(s)
#06-Dec-19 00:11

I'm still intrigued by the problem. So for some fun at the end of the afternoon. Thanks for sharing the area of the paddock. So some rough calculations, it looks like thes stumps are roughly concentrated in 1/2 of the area of the paddock. So let's say 100 ha with stumps. 100 ha is one million square metres. Divided by 350 stumps so on average each stump occupies 2,857 m2 or roughly a square 53 m X 53 m. That let's me visualize the scale of the problem. So the stumps are really spread out, a different kind of forest to which I'm accustomed.

This seems like "rake the leaves problem" where there is a phase of really efficient work and a second cleanup phase that isn't as efficient but on a smaller task (it's late fall where I live in Canada and we're still raking leaves). So with piles of leaves to pickup, the best way seems to tackle the middle of the pile, the highest density of leaves, pick up with maximum efficiency, don't worry about spillage or leaving small leave-strips of leaves behind. Then on a second pass, rake up the scattered leaves and pick those up.

See the attached diag. So paths 1 and 2 get you to the vicinities of the highest stump density. There is some zigging and zagging depending on if you are using an excavator with some reach or if you are going to each stump and grinding it down. The decision of which stump is done on the fly, planning ahead 3-4 stumps. Path #3 is the cleanup and won't be as efficient in terms of stumps removed per metre of travel or per hour. But it's a small number of stumps. Your overall average when combining paths 1, 2 and 3 should be pretty good.

Anyways let us know what you ended up doing. This is one of those situations where a solution (M9) is looking for a problem to solve.

Attachments:
stump path.JPG

tjhb

8,950 post(s)
#06-Dec-19 03:34

Tony, I am going to guess that you have never driven a tractor.

Is that right?

Manifold User Community Use Agreement Copyright (C) 2007-2019 Manifold Software Limited. All rights reserved.