Home - General / All posts - most efficient path through a number of points
 Sev452 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
 Graeme947 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.
 Sev452 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.......
 rk400 post(s) #30-Nov-19 12:21 There was an example in m8 doc iirc. Search for Gabriel Network.
 tjhb9,344 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.
 Sev452 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!
 adamw9,321 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.)
 oeaulong253 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?
 adamw9,321 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.
 Sloots473 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
 Sev452 post(s) #30-Nov-19 21:33 That'd be great if you were able Sloots....just let me know if you do!
 mlinth435 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
 mlinth435 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.htmlYou'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.
 mlinth435 post(s) #08-Dec-19 16:20 Sev, can you share the coordinates of your stumps, ideally in some sort of metres units? I've installed the OR tools and there's a Travelling Salesman program there where I can just swap in the coordinates. It runs in seconds.
 Sev452 post(s) #08-Dec-19 22:24 Sure thing, here you go! Hope .kml is ok...Attachments: Boomerang_Point Drawing.kml
 mlinth435 post(s) #14-Dec-19 15:44 Right then, I have a solution using the Operational Research tools above. Here's what I did.Installed the OR tools. There is an example travelling salesman program in the install so all I had to do was replace the coordinatesI projected the points to EPSG:28355, so I had coordinates in metresThe OR program only works on integers, so I multiplied the coordinates by 10 and then roundedSome stumps are so close together they had the same "adjusted" coordinates so I de-duped themFed the coordinates into the programIn the attached MAP file you can find the following:stumps. This is your drawing, although I added myx and myy columns when I messed with the coordinates unique_coords. These are what I created for the algorithm. You can see the solution there already in the column "route_order"travelling salesman output. The program outputs the array positions of the coordinates in the order they should be visited. I ordered the input array by the mfd_id in unique_coords. I converted the output to the from and to columns, then populated the route_order column in the unique_coords table by matching the mfd_id with the "from" column and setting route_order = id. The id is the array position of the coordinates that went into the program.theroute. This is the actual route as a linestumps_with_route. I added the route_order to the stumps tableI can't really tell you how the algorithm works, so that's a bit of a black box here, but the results look plausible and perhaps they are helpful. It runs very quickly - the most time-consuming part was installing the toolkit!MAttachments: travelling_salesman.map
 Dimitri6,129 post(s) #15-Dec-19 06:47 Well, I would respectfully point out that is not a "solution" to finding an optimal path, and it is not a "travelling salesman" solution. If what you want is a path through all stumps that takes considerably longer than an approximately optimal solution well, OK, then it's a "solution."Example: Open the map and look at the path through stumps 100, 101, 102, 103, 104. It's a gross error to not visit stump 155, which is next to 102, but instead to defer that to an extremely long detour later on. The route calculated is full of such gross inefficiencies, jumping back and forth in zig zags over long distances. Another example is how stumps 179 and 178 are next to 37, but are ignored in favor of a very inefficient detour later on. 166 and friends next to 92 is a another example.Zig zags, aboveTasks that are NP-hard are NP-hard because they are difficult to do. Finding an optimal path through many points is NP-hard. In contrast, if you don't care that you'll be rushing around with a lot of unnecessary travel, finding a non-optimal path is trivially easy.The computed route runs very quickly because it is not, repeat not, a travelling salesman solution. I'm surprised they call it that since it clearly is wildly inoptimal. To see what I mean, load the stumps into Release 8 and do a Spanning Tree. You can see how that Spanning tree with some manual editing by eye done in 9 will result in a significantly shorter overall path than the very zig zag path.Above: Spanning tree on stumps, done in 8There is no general solution to NP-hard problems which is not NP-hard. That's a non-negotiable consequence of mathematics which people understandably don't like, but it is what it is and there is no getting around it.Second best are approximate solutions. But those are not usually "one size fits all" because they tend to be highly situation dependent: what makes sense driving a tractor across raw terrain isn't likely the same that makes sense within a constrained road network for taxis. That's why so many routing "solutions" are basically technical hints augmented by human know-how / common sense. Build a spanning tree, use that as a guide and the guy piloting the tractor makes decisions on the fly. It's often like that for vehicle navigation as well, where a savvy cab driver takes the computed route as a guide, while making actual course decisions on the fly based on local knowledge and perception.Attachments: spanning_tree.png zig_zags.png
 tjhb9,344 post(s) #15-Dec-19 08:45 Great eyes, Dimitri.Is it possible that mlinth inadvertently configured the Google algorithm to use multiple travellers? It almost looks that way.Or perhaps Google did that first and foremost, quasi-optimising the distributed case--because that is what their street view camera operations need--and did not bother much about the canonical case of a single traveller.Where would we be without black box open source code (BBOS)?(That is a bit rude. I read through the Python parts of the code base mlinth pointed to, which is exemplary in some ways. It doesn't ever explain what it is doing, but it does generally try to say why it is doing it, and those comments are readable, and it is really good Python. Well, that is just wrappers. I didn't try reading the underlying C. Maybe the what and the why are equally well explained there, with full references. Don't know.)
 mlinth435 post(s) #15-Dec-19 10:07 Well, I just thought it'd be interesting to see what the toolkit came up with. The page on routing dicusses the inherent intractability of such problems, making the same points Dimitri makes. I also deliberately wrote "a solution" and not "the solution".It'd be interesting to see the the length of the overall path in the spanning tree approach - you still have to get from the ends of one branch to the next one, so there is still back-and-forth there.Tim, it's definitely using only one vehicle. I input the points ordered from west to east, it's possible that caused the algorithm to get "stuck" in a local optimum. Will double-check my calculations and have a little play.
 mlinth435 post(s) #15-Dec-19 15:43 I had a little play - here's a new route. It's much smoother and shorter now. I re-cranked everything from scratch and I allowed 4 minutes search time (it converged in about two minutes). I also tried changing the input order of the coordinates - that does seem to make a difference, with a random order generating a shorter path than sorted west-east or north-south. (Can't rule out me making a mistake in preparing the inputs first time round, either).As George Box said, all models are wrong, but some models are useful. It looks like the algorithm here produces reasonable results, so long as the inputs are OK. As Dimitri wrote above, this is all very well in theory, whether it helps in the real world is a different question. Attachments: travelling_salesman.map ts.PNG
 Dimitri6,129 post(s) #16-Dec-19 06:55 That's a really nice result. It's odd that changing the input order of the coordinates would cause a different route to result, but there's no arguing with a good result.
 mlinth435 post(s) #17-Dec-19 19:47 In all honesty I think I must have made a mistake in either the pre- or post-processing first time round! I'm still very much a noob with Manifold 9. The differences in objective function were small when I changed the order. At least it got a discussion going
 adamw9,321 post(s) #16-Dec-19 11:31 I agree with Dimitri, this second result looks very good. Much better than the first. Perhaps the 4 minutes were used to incrementally improve the first result.By the way, regarding the spanning tree - it is useful for estimating how good an approximate solution is. If the length of a solution is 2x the length of the spanning three, the solution is garbage because you do better just following the spanning tree and taking each edge in both directions. Otherwise, the length of a solution cannot be shorter than the length of the spanning tree, and the extra length beyond the length of the spanning tree shows how much the solution can likely be improved. (Speaking very roughly, if you are within 10% of the length of the spanning tree, you can likely declare victory because chances are, the solution simply cannot be improved anymore, barring a miracle. If you are within 50%, well, let's wait 5 more minutes to see if there are any more incremental improvements left, etc.)
 Sev452 post(s) #17-Dec-19 03:51 Wow!, that IS a really nice result, thanks so much for doing that. It's exactly what I was hoping for. I think the machine itself will make it a bit more efficient in that I don't have to go exactly to each point, just within bucket reach.Is it possible to make a tool up for use in Manifold?
 mlinth435 post(s) #17-Dec-19 20:01 That's nice to hear. I'm sure it's possible to build a tool - it's all code - but it's not something that I'd personally be comfortable doing. The example program hardcodes the coordinates - it would be easy enough to modify the program to read coordinates from a file and write the outputs somewhere.
 Sloots473 post(s) #18-Dec-19 11:04 See this link or goto https://youtu.be/JkBPKcf2RDs manually to see my TSP add-in in action. Almost done. The only thing left is the export of the found route back to Manifold. http://www.mppng.nl/manifold/pointlabeler
 tjhb9,344 post(s) #18-Dec-19 16:54 Great UI design Chris, really ergonomic. I like it that you can turn the visualization on and off live, an especially nice detail.You might not know that the video has no sound (only background noise). I think you may be briefly explaining how the Kohonen approach trains the initial circle of points onto the dispersed points, but this can't be understood very well without the words.Any further references to the algorithm you are using (and any libraries) would be interesting.
 Sev452 post(s) #19-Dec-19 00:48 That's really nice Chris....well done. That would be such a handy tool in my line of work (farming!) Not only for stumps with heavy machinery, but things like weed infestation control, watering points traverse etc....this forum never ceases to amaze me. Seriously.
 tjhb9,344 post(s) #19-Dec-19 04:58 So how much would you pay for it, Sev, as an annual fee?How much money would it save you? Seriously.Itâ€™s only fair for you to be honest about this.
 Sev452 post(s) #19-Dec-19 10:23 No problems being honest Tim.Not sure about how an annual fee would go, but lets say this project, I rekon it would save me around 4-5 hrs (complete stab in the dark), so that's worth roughly \$500AU in diesel, wages, machine wear & tear.....I reckon an instance might be say \$100-150? I'd struggle with an annual fee, as this is the first time I will have used it....and I've been doing this job for 30 years. Subscriptions like MS Office etc, which I use every day, financial packages, Adobe etc....I am happy to pay an annual subscription because of the constant use. It's not like I would use it every day, but when I do, it's valuable.So to conclude, the annual subscription would need to be really good value for money, as I could easily go a year or two without using the function, but I'd be happy to pay per instance for the use of it.Hope that helps....
 tjhb9,344 post(s) #19-Dec-19 11:21 Yes that really helps a lot. Thanks.There are innumerable things like this that might be worth writing, and which would nearly be worth writing for free... but would be much much easier to invest time in (and do fairly well) if there were a modest market at the end.Your straightforward comments really help. As a community we need more of this, in my opinion.
 dchall8763 post(s) #09-Jan-20 04:27 I don't think the efficient path is what a farmer would use. Once he gets the equipment out in the field, he's going do work every stump within reach right there. He's not going to bypass stumps to pick them up on the way out. He'll work a high target area and move to the next highest target area. For that type of approach I see this as a proximity problem as worked out by Sloots nearly a decade ago. This heat map shows a hot spot and some warmish spots that would give the farmer a solid bang for his time and fuel budget. After the initial spots are worked, the rest of the stumps are less clustered. These final stumps might benefit from an efficient path analysis. Attachments: Stump Heatmap.jpg
 Sev452 post(s) #24-Jan-20 09:33 I guess my response would be that this is exactly what I would use, and I am a farmer. I think in the past there was no oeasy way other than to get in there and burn diesel, looking for the next closest stump, but we (or I) am constantly looking for ways to improve my efficiency in the field. It's like saying the farmer would just use a laser to level a field, and that was the case 10 years ago, but these days with gps guidance and smart software to operate bucket height, we can reduce earthworks by as much as 55% (I have a field where this was exactly the case, 750 cubic m/ha down to 350).There can be no argument that this method of stump extraction would be more efficient than going in with no methodology whatsoever (or very little).Anyway, I have the map in a gps, and will hopefully provide some useful feedback on how we went!
 Sloots473 post(s) #17-Dec-19 14:50 Here is my solution, using a Kohonen network. It took about 10-20 seconds to generate this route. Genetic Algorithm performed no as good as this, but with less points to visit it does do a good and much faster job. CheersAttachments: tsp.png http://www.mppng.nl/manifold/pointlabeler
 adamw9,321 post(s) #20-Dec-19 13:08 Out of curiosity, I re-created this path and compared its length to length of the path posted above by mlinth and to the length of the spanning tree.The results:Spanning tree (absolute lower bound): 8962.6Path 1 (ts.png): 10550.3 (+17.7%)Path 2 (tsp.png, right above): 11631.7 (+29.7%)Spanning tree 2x (trivial solution used as roughest rule of thumb for attempted solutions): 17920+Frankly, it is impressive that getting within 30% of the spanning tree - which is frequently unachievable - is this easy.
 tonyw599 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.
 ColinD1,963 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 solutionsGiven 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
 Sev452 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)..
 Sev452 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.
 tonyw599 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
 tjhb9,344 post(s) #06-Dec-19 03:34 Tony, I am going to guess that you have never driven a tractor.Is that right?
 tonyw599 post(s) #06-Dec-19 17:23 Yes I have actually, on farms. Both picking up debris piles in fields and cutting, raking and baling hay. So two different types of travel paths. Sev didn't describe the machine, location, terrain, nor size of stumps. For removing that many stumps I envision a tracked excavator with a boom with maybe with a reach of 8-10 m radius either side. No matter, let's see what Sev comes up with.
 Sev452 post(s) #07-Dec-19 05:48 Nice guess Tony, we'll be tackling the problem with a 30t tracked excavator. These machines are generally not good at travelling (hard on the tracks), hence the thoughts about making it more efficient.
 ColinD1,963 post(s) #08-Dec-19 22:16 Depending on the reach of the excavator relative to the distance between the stumps, maybe it is possible that there are locations where several stumps can be removed without the excavator moving. If so then you would want the most efficient distance between the excavator reach circle centroids rather than individual stumps. There is a script for creating a hexagonal array that might be useful. Aussie Nature Shots
 Sev452 post(s) #08-Dec-19 22:27 Yeah I did wonder about that too Colin, but if there was a way to create the line, we would just visually look at where the next ones are and grab them without moving, then progress once they were done. You never really follow the line exactly. The other potential issue is that excavators generally don't change direction easily....but we can handle that manually I rekon....
 ColinD1,963 post(s) #08-Dec-19 22:54 Have a play with the attached Sev using the excavator reach radius. It should give you an idea of where the groups are. Another valuable tjhb contribution.Attachments: Create Hexagonal Grid.map Aussie Nature Shots
 Sev452 post(s) #17-Dec-19 03:54 I'll have a look at it, thanks Colin!