UKC

I've had a great idea for a silly jaunt but I'm struggling to plan a route. I want to be able to tell the computer all the points I want to go to and it to show me options for the shortest/flatest way to link them. There are a lot of points (more than 80). Please can anyone recommend me any websites or software that will do this.

Cheers

I'm afraid that you have stumbled on quite a difficult problem.

In mathematics/computer science this problem is called the traveling salesman problem (https://en.wikipedia.org/wiki/Travelling_salesman_problem) and it's quite hard to solve.

It's an active stream of research that large companies (Amazon, DHL, etc.) spent a lot of money on researching faster/better algorithms for.

All this means, that while there is a large number of computer programs which can give you the shortest route between two points, there are not nearly as many programs which do what you want.

If you have some programming capabilities, something like Google OR tools could work. (https://developers.google.com/optimization/routing/tsp)

GIS software also sometimes has these features, possibly through installing extensions.

I'm a PhD student active in a research branch adjacent to TSPs, so if you have any questions feel free to ask.

Thank you for your input.  Failing exactly what I'm after, can anyone recommend something that will link my points along existing footpaths/roads via the shortest distance to give me a starting point and I'll fudge it by hand from there. It's fine to cover the same ground more than once.

Put any two points into Google maps walking and it’ll can give you shortest distance. Repeat for each pair you wish to link.

I'm wanting to plug in all my points and for the program to tell me the most efficient way to link them.

As Jesse said above that is the TSP, your initial version which involves minimising distance and ascent is a hard version of the TSP, but just trying to link them with footpaths is still the TSP, to brute force consider all routes is 79 choices for the first route, then 78 choices for the 2nd leg and so on, 79x78x77x…x1 is a number 117 digits long that’s significantly more than the number of sub atomic particles in the universe and not something any non quantum computer is ever going to be able to do.

There are algorithms which will give a best guess at the best route or a bound on it, but with a problem of 80 vertices it is still going to need lots of computing and clever mathematics I would think.

Nobody knows the best way to link up all the wainwrights as an example, but lots of people have spent lots of time looking at the map and come up with a reasonable route, but there may be better routes not yet discovered.

Thanks. I might lay all the maps out in the garden tomorrow and start making groups of target points, come up with a logical way to link the points in each group then link the groups.

If you're technically minded, Google has a suite of tools for finding solutions to problems like this. As said above, there isn't a simple algorithm that will do it, and as such you are unlikely to find software that would both map the routes between the nodes and find the most efficient ordering. This page has some examples, it might not be much use to you, but it's interesting: https://developers.google.com/optimization/routing/tsp

In terms of finding a solution, plotting the points on a map and using some of your own judgement for potential routes is probably the best way. There will be some where the next point to head for is obvious, and a little judgement on route is needed, and others where you might need to test out several options. PlotARoute is pretty good for mapping a reasonable on foot route between points.

Or a slime mold:

https://www.sci.news/biology/slime-mold-problems-linear-time-06759.html

The slime mold only finds a “good enough” solution, not the optimum.  There are math/computer/algorithmic solutions that do likewise but I don’t know of a trivially accessible online version.

The OP’s suggestion of optimising small groups of places is a pragmatic way to go.  

Edit: when walking off road on PROWs and tracks on access land, minimising the distance is not guaranteed to minimise either the ascent/descent or the quagmire or other access problems!  If only the OSM database had every path scored for surface quality, obstacles and so on…

Thanks I didn’t consider slime mould as a solution. You are full of good ideas.

This shows that large TSP solutions are possible with the UKs biggest pub crawl, but not easy. I can’t imagine how they did this.

https://www.math.uwaterloo.ca/tsp/pubs/#:~:text=It%20is%20the%20solution%20....

I think it comes down to pub distribution being highly in-homogeneous with dense clumps linked to population density. If you plotted a heat map of postcode densities it would match pub density quite closely and would look like punctate clumps of light connected by filamentous webs against a dark background.

This in-homogenous distribution lets you cut the search space down dramatically.  Imagine a nation of just two well separated cities, with half the pubs in each city.  You can trivially prove the optimum route does one whole city then moves on to the other, and doesn’t zig-zag between them.  This turns the problem it to two successive TSP problems each of half the size. With computationally complexity scaling as the exponent of the size of the problems, halving it makes a massive difference to tractability.  What I think they do is to keep sub-dividing the problem in an intelligent way that probably isolates the domains until a domain is solvable.  Given how insanely far compute hardware has come (in terms of memory, speed and operations/second), you don’t have to sub-divide that much before individual domains are solvable by brute force and ignorance.

One of many examples of how “binary space partitioning” of data can turn a computationally expensive problem in to something manageable.

The critical question is, can the problem be solved in less time than it takes for one of the pubs to go bust, close and be turned in to a house?

Are you factoring in height loss and gain? Obviously you aren't going to criss cross, so you can cluster them in sectors yourself. Often score orienteering you work clockwise (or anti) around the imaginary circle of your map, you still zig zag, but never cross the centre to the opposite sector. 

Yes, I've sorted something similar to that. I drew a line between all the pairs/strings of points that you would definitely link one after the other which reduced loads of dots to a smaller number of lines which was easier to manage.

The brain strain are always the outliers which don't immediately appear to have an ideal fit, these I guess in your non competitive problem can just be measured individually. 

Yes. I found the biggest outlier and figured I need to start or finish there. Most of the other outliers can be done out via one and back via another.

Is this any use?

https://www.routexl.co.uk/

I've used the solver in Excel to try and find the optimal orienteering route for a couple of permanent courses with the height gain/loss basically just being a <100/>100 percentage factor on the distance. Took a fair bit of effort to measure everything from orienteering maps, would be easier if using "normal" OS maps giving grid locations.

But there's no way it'll work with 80 points - however if there are some obvious links between clusters then you can deal with each cluster separately - I split one 25 point course into a 16 & 9.

https://www.ocad.com/en/route-analyzer/

If you're in a club with a log in or are feeling relatively wealthy to subscribe to ocad. Not sure if it does score events though, just optimum line between points. 

Other's have done a good job of explaining why this sounds like a TSP problem and why TSP is a computationally expensive problem to solve.  Nothing further to add.

This however, "flatest way to link them", caught my eye and no one appears to have addressed it.

Given this is UKC .. presumably you are planning a round of some sorts.

This reads like a job for either:  Naismith's rule or Scarf's equivalence between distance and climb.

https://en.wikipedia.org/wiki/Naismith%27s_rule

Naismith's rule:  allow 1 hour for every 3 miles (approximately 5 kilometers) of distance, plus an additional hour for every 2,000 feet (approximately 600 meters) of ascent.

Scarf's equivalence:  a more nuanced version of Naismith's that allows for personalization to the individual by introducing a personal pace variable.  

However - both of these have known assumptions/variables that need consideration before being put into use.

1. Assumes typical terrain (not scrambling)
2. Normal conditions (not winter)
3. Does not account for breaks/delays
4. Does not account for loads carried
5. etc .. 

If you truly wanted the "flatest" path between nodes i.e. the true elevation between 2x points inc ups & downs along the way .. that itself is also non-trivial to calculate . 

See here for how it can be calculated:  https://www.gpsvisualizer.com/tutorials/elevation_gain.php

With gpx data you can use this page to calculate elevation gain (Ensure you click the Add DEM button) :  https://www.gpsvisualizer.com/profile_input

That being said .. generating multiple possible gpx tracks between each of your points and then generating the elevation gain for each isn't going to be fun at all.

I think you're strategy to simply where possible makes most sense.  Truly trying to calculate all possible paths/tracks between each of your 80(?) nodes, then trying to generate a gpx track for each and then an elevation gain is going to be exceptionally computationally expensive to achieve.  

Come back and let us know what you decide to do. 

(Would make a good comp science project)

This all sounds v complicated! If you're looking for quantifiably shortest/ flattest, it sounds hard.

If you're looking for pragmatic you can create courses in Garmin Connect by adding your waypoints. The site will then link them together via popular routes used by Garmin users.

It's a bit fiddly but you can use waypoints and edit the tracks as you wish. It won't optimise the route for you but may help you get started.

Thanks all.  I'm getting there with this now.  I'll show you what I produced once I've run/walked it and no doubt someone else will come along and think of a better route, but that's half the fun!

Once you've mastered your system, try the 214 Wainwrights, see if your route is better than the current or previous record holders.