Generating pleasant running tours
With the aim of generating pleasant itineraries, we began by formalizing what makes a path pleasant for a runner. We consider the pleasantness, or quality, of an itinerary as the extent to which its characteristics match runners’ preferences. We split this quality into two aspects: the quality of the path segments that compose the itinerary; and the form, or geometry, of the whole path. The quality of every path segment depends on various criteria (e.g. whether it’s a pedestrian path, as well as its environment and proximity to traffic) that must be translated into a numerical score that can be used as input to the itinerary-generation algorithm.
Using OpenStreetMap (OSM) data and standard routing libraries, we began by building a routing graph. The nodes of this graph are the road crossings, and the arcs are the road segments that link the crossings. Then, based on OSM attributes, we computed a pleasantness score for each arc according to standard runners’ preferences. For example, paths along hiking trails, parks or riversides were assigned a much higher score than paths close to main roads or motorways.
Given the scored routing graph, a starting point, a target distance and an elevation gain, we focused on generating appropriate tours—i.e. loops of the requested length—that maximize the pleasantness score on the visited arcs. We formulated this optimization problem as an arc-orienteering problem, which can be seen as a combination of two well-known NP-hard problems: a knapsack problem, where the goal is to select the best locations on a map for the runner within a (distance) budget constraint; and a travelling salesman problem, where the goal is to find the shortest route that visits these locations.
To solve this problem, we proposed a heuristic algorithm based on a greedy randomized adaptive search procedure (6). Starting from a trivial short tour, the algorithm iteratively computes possible extensions of the current tour and randomly selects one among the best of these to increase its length. This procedure can be repeated until no improvement is found, or the processing time limit is reached (see Animation 1(a) below). There’s a trade-off parameter that balances the greediness and randomness of the algorithm to allow for an efficient exploration of the solution space; the algorithm can be executed in parallel with different trade-offs to produce a variety of results.
While this method allowed the computation of high-scoring tours, we observed that some artefacts can appear, such as artificial detours (those that a user would never choose to take) and generally unnatural-looking paths (involving many unnecessary turns). This wasn’t surprising, since we were only focusing on the score. To improve the geometry of the results, we designed a post-processing step that smoothens the tours: see Animation 1(b). We were also able to rank the generated tours according to their geometric properties (e.g. number of turns) to favour the simpler, more natural-looking ones.
As pointed out by our user study, runners appreciate flexibility in their itineraries and like to feel free to modify them as they go. Sometimes, they’re simply unable to follow the proposed path due to unplanned factors (e.g. construction work, the weather or tiredness). Also, since it’s impossible to account for the subjective preferences of every runner, we believe it’s important to acknowledge that users know best. To ensure they get the most pleasant run, we should support them by adapting the proposed itinerary to suit their needs.
To support such flexibility, we provide a set of alternative paths—see Animation 1(c)—that may be interesting to explore for the runner with each computed tour. The idea behind this is to highlight alternatives to subsections of the original tour that are roughly equivalent, or better, in terms of pleasantness. In addition, we allow users to change their duration or distance targets at any time, and dynamically update the tour accordingly, using a variant of our main heuristic. This makes it possible for runners to deviate and explore beyond the precise initial itinerary, while still ensuring that the quality of the run matches their preferences.