I decided to test out Copilot on another MapRun-related challenge: planning the optimal route for a score event. Our Summer League events are, more often than not, planned using OpenOrienteeringMap. This uses OpenStreetMap data for the base map. The format is usually a 45-minute urban score event, using MapRun’s ScoreNxx scoring system. The aim was to take the KML file that describes an event, and determine the best route to take to maximise the score. As a constraint, I would specify the maximum distance that the route should cover (i.e., how fast the competitor was expected to run).
Travelling Salesperson
Having been given Python as the implementation language, Copilot made short work of the first task: extracting the control coordinates from the KML file and converting them into latitude and longitude. When instructed to find the shortest path that included all of the controls, it first used the Haversine formula to calculate the distance between each pair of controls (taking into account the curvature of the earth). It then called the python-tsp (Travelling Salesperson Problems) package to find the shortest route.
With the number of controls in a typical event being around 30 or so, a dynamic programming algorithm took too long. Simulated annealing (a metaheuristic algorithm) returned in a reasonable length of time. Some judicious weighting was needed to persuade the algorithm to start and finish in the correct places. Copilot wrote more code than it needed, as this library also includes a function for calculating great circle distances.
OpenStreetMap Routing
Of course, we’re not typically interested in straight-line distance between controls. Copilot correctly identified OSMnx as the go-to library here. It will download a section of the OpenStreetMap network data. Copilot initially just wanted to base this on the midpoint of the coordinates and some arbitrary radius. It was eventually persuaded to use a bounding box containing all of the coordinates. There is then a convenient nearest_nodes function to find the nearest point on the network for any given coordinate. The shortest_path function from the NetworkX package was then used to calculate the shortest route between each pair of controls. As before, it used TSP to calculate the optimal route to visit all of the controls.
OSMnx has a convenient plot_graph_routes function that draws the network and one or more routes. This showed up some oddities due to the placement of the controls. The nodes in the OSM network are only where lines terminate, whereas a control might be on a bend in a path halfway between the two ends. I had Copilot switch from using nearest_nodes, to use nearest_edges instead. It would then remove the edge and replace it with two edges that joined at the location of the control. It then took me a while to work out that as edges are directional, I needed to do the same thing for the edge going in the other direction.
The Orienteering Problem
As a planner, this solution could already give some useful insight. Unlike the local night league, we try to ensure that nobody can get easily get all of the controls in the time available. This means even the faster runners have to think about what controls they might leave out. What you really want, though, is for the optimal route to change significantly depending on how far you run, forcing competitors to commit early. Rather than a travelling salesman, we needed a solution to what the academic literature unimaginatively calls “the orienteering problem”. It was at this point that Copilot decided to switch to using Google OR-Tools.
OR-Tools has a significantly more complicated interface. Copilot took a fair amount of prompting to come up with working code, but got there in the end. The following is an example of the output for one of this year’s events. Thankfully, the proposed route didn’t use the M3 motorway that divides the area in two!
Limitations
I’ve placed the final code, such as it is, on GitHub. As the README states, there are still some limitations. From an orienteering perspective, the most significant is that the routes always follow linear features, i.e., there are no shortcuts across open areas. In hillier locations, I’m sure the fact that it doesn’t account for climb would lead to sub-optimal routes.
From a technical perspective, as I discovered when trying it on another event, there are edges in the OSM network that don’t have associated lines. The current splitting logic fails when it encounters one of these. I’m sure that’s fixable.