Round trip route planning for pedestrians
A custom build routing solution that offers the possibility to create round routes that brings you back at the start location.
Typical route planning software is targeted at the use case to bring a user from A to B. Most software packages offer the possibility to create a round route by manually adding way points that need to be visited and some route planning software packages offer solutions for the traveling salesman problem in which case x locations need to be visited preferably in the most optimal way to save time and costs. For runners and hikers that want to plan a trip that brings them back to the start location, these solutions are not optimal. Preferably a user opens the application an only has to say how long or how far he wants to walk / run.
This is a relatively new unexplored science. Some universities do research in this field like the university of Gent which has designed an algorithm that plans round city trips with a required distance. There are also some other round trip planners but after testing those on various locations with various distances it appeared that none can generate a round trip for most locations with a distance within a 10% margin from the required distance. This problem is relatively harder than generic routing since many optimizations that can be used to plan the shortest or fastest route from A to B are not applicable for the round route problem. Secondly where for the generic routing problem there exists a perfect solution that is the shortest or the fastest route for the round route planning problem many solutions exists within the requirements of a 10% margin from the requested distance. Of course there is only one that is closest to the required distance but those solutions are often not the solution an end user would like to see since a end user also requires that a route is nice to walk. E.g. preferable through green spaces (parks and forests), not along heavy traffic roads, with as less traffic lights and other crossings for runners, etcetera.
To give an example of the number of calculations that need to be made on possible routes, assume a Manhattan grid of roads where each crossing is 100 meters apart. At every crossing there are four possible choices: back, straight, left or right. So for a required distance of 200 meters there are 4 to the power 2, which is 16, possible routes with a distance of 200 meters of which only one brings you back to the start. With a required distance of 400 meters there are 4 to the power 4, which is 256 possible roads. With a required distance of 1000 meters the number of possible routes is 2 to the power 10, which is approximately 1 million. For a marathon this leads approximately to a number starting with 7 with 252 zeros behind possible routes. So calculating every possible route within the time that an end user wants to start walking is not possible.
To be able to solve this problem we have designed an algorithm with heuristics that keeps the number of options at every crossing low and first calculates the most probable and preferable paths. By keeping the number of options low the number of possible paths that need to be calculated are also low, since 1 to the power of any number is still one. But even with a factor close to 2 this still leads to a number of possible routes for a marathon in a Manhattan grid of around 3 with a 126 zeros behind it. By using custom build heuristics targeted at the client wishes that are applied in every step of the calculation we were able to achieve that routes get planned usually within a second that fit with the expectations.
Want to try it out? Please see the links below to install the ImagineRun app for your mobile.