A mathematical approach to determining shortest route covering all roads.
Problem Statement:
Given a finite number of roads, what is the shortest possible route to cover all roads?
The map given is Zwift's new world in the Makuri Islands, Yumezi as released on 05/19/2021. This is the map as retrieved from https://www.zwift.com/yumezi:
Rules and assumptions:
- Road must be covered in full at least once. Multiple passes over the same road are allowed. The Euler path or cycle, if available, would produce the shortest route since a single road is never covered twice by definition. However, for a finite graph, a Euler path or cycle is not guaranteed to exist. In the case of the map given for this challenge, a Euler path is not possible.
- U turns are allowed.
- The full of all roads should be covered, thus to U turn, you should go through the intersection, then U turn.
- Arbitrarily, you don't need to go through all possible paths in an intersection. I.e. in a four corner intersection, you don't need to cover right turn, straight and left turn to touch all parts of the intersection. The goals is to cover all road segments connecting the intersections fully, not all parts of the intersections.
- Similarly, you don't need to cover a road segment in both directions, one direction is sufficient.
- "Roads" include any rideable path in normal exploration mode. This includes pavement, gravel, bridges, dirt, etc... Starting pens and roads from the starting pens to the main road can be excluded.
- There exist a few starting (spawn) points on the map. Chosen route can start from any of the spawn points in any direction (naturally or via U turn.) Additionally, for a true challenge, arbitrary start points should be allowed, though may require the help of a friend.
Approach:
Tooling and main concepts
The map appears to be a series of intersections (vertices), connected by roads (edges) and thus can be represented by a mathematical graph and graph theory can be applied to help with the solution. Additionally, graph theory allows for the weighting of edges to determine "cost" of the route.
Based on graph theory, the first thought that comes up is that this problem is the famous Traveling Salesman problem. However, on inspection, we don't care about hitting all of the intersections, but all of the roads. So, this problem solver doesn't apply here. We could invert this such that the roads are the vertices and the intersections are the edges, but I'm not certain this guarantees complete coverage.
So, additional research is required. I am not a mathematician, in fact I dropped out of advanced math theory classes in college. The actual closer problem description is the Route Inspection problem / Chinese Postman problem which according to Wikipedia is
to find a shortest closed path or circuit that visits every edge of a (connected) undirected graph
Perfect, that describes our problem statement.
Now, I don't enjoy doing complex math by hand (I stop at calculus) and solutions would not be scalable solving this by hand. Thus, to google to search for existing code:
And I find this: https://github.com/supermitch/Chinese-Postman:
I wrote this program to solve the Chinese Postman problem.
Perfect! Thank you supermitch!
Graph Creation
Now all I need is to notate the graph as an input to this program and find the solution.
As previously mentioned, there may be multiple starting points for the journey. So first, task is to enumerate where those are. For this, I could have loaded up Zwift, started each Zwift programmed route and see what's available. However, Zwift insider & Zwift Hacks does this for me: https://zwiftinsider.com/makuri-islands/
From going through the list, 3 main spots of spawning exist. There may be some slight variance for the Zwift programmed routes, but there are 3 road segments that you can start from. Diagram of these is found little later....
Next, I will simplify the map to a more understandable graph by getting rid of the detailed squigglys.
Here I am looking to save some time as the whole graph is kind of complex, so the following simplifications are made:
The Castle section at the top is pretty detailed and consists of around 10 road segments itself. When creating an initial graph, this entire village is simplified to a singular graph vertex. I think this was ok since there are numerous entries and exits to this area of the map. The consolidated graph I created has 4 edges attached to this vertex, thus there is great confidence that I could work out the exact paths through this village after the problem was solved and still hit all the roads. In hindsight, this was completely true, navigating all of the road segments was simple while I passed through/around this village 3 separate times. However, I lose the ability to optimize the route by simplifying this to one point, more options are available with all of the road segments included in the computation
Similarly, the "box" village at bottom is basically eliminated, keeping that entire road at the bottom as a single edge. The optimal route through this village is pretty apparent as you can determine a route that loops through each road segment without repeating any just by looking at it. I guess similar to the castle village, including all edges in the solution will allow a more optimal solution.
Since graph theory allows for weighting of edges to determine an optimal solution, I will weight all of the edges. Weighting allows you to assign a cost to each road segment, which will help determine which road should be repeated (if necessary). Since the problem statement is to incur the least distance, weighting each edge by distance is the best choice. The most complete solution would include determining the exact distance of each road segment by inspecting each from a previous recording in Strava, for example. However, there is significant effort for this. So, to once again simplify, I will rate the distance for each route on a scale of one 1-5 by simply visually looking at how long each road segment looks on the map.
With all of these simplifications, the crude hand drawing of the graph I come up with is:
Letters A-I indicate intersections
Circled Numbers indicate the estimated edge weight
Additional numbers along-side abbreviated letters (Example 4 Se, Sp) indicate spawning/starting points. The abbreviations are the Zwift programmed routes.
Note: One adjustment made after this drawing was to include the starting point as a vertex itself. Thus, there was an additional "J" vertex in the graph not pictured and the road/edge containing this point was divided roughly in half for weighting.
Running the program
Back to inputs into the provided program. The required inputs for this program are sets of edges as defined by the two vertices the edge connects to. Vertices are defined as numeric instead of alpha, so A->B is (1, 2)
A third value for each edge allows for the defined weight. There is also a fourth value that could define if the edge was directional (think one way street), but this does not apply here, you can currently travel all of Yumezi's road segments in either direction.
My entire set of edges looked like this:
yumezi_1 = [
(1, 2, 1), (2, 3, 1), (2, 4, 1), (4, 5, 2), (4, 5, 5), (5, 6, 1),
(3, 6, 2), (6, 7, 2), (6, 8, 2), (7, 9, 5), (7, 8, 3), (8, 9, 1),
(9, 10, 4), (10, 3, 2), (10, 1, 1)
]
With this as the input, we run the program as described and get the following output:
Loading graph: yumezi_1
<15> edges
Converting to Eularian path...
Doubling dead_ends
Building possible odd node pairs
(28 pairs)
Finding pair solutions
(56 solutions)
Building path sets
Finding cheapest route
Adding new edges
Conversion complete
Added 5 edges
Total cost is 40
Attempting to solve Eularian Circuit...
Solved in <1> attempts
Solution: (<20> edges)
[1, 10, 9, 8, 6, 5, 4, 5, 6, 7, 9, 8, 7, 6, 3, 10, 3, 2, 4, 2, 1]
Note that the "Solution" would provide the route transversal by defining the order of vertices hit during navigation. Cost would also allow us to compare solutions with different inputs.
Alternative Solutions
I mention cost comparison since as noted we have multiple spawn points. Thus, another graph for a different spawn point is drawn. Note that only the vertex enumeration changes since we insert the starting point as a vertex in a different location.
Similar is done for the 3rd spawning point (not pictured) and those are converted to edge input sets and run through the program. In the end, all solutions came to a cost of 40, so I arbitrarily choose to go with the first solution.
Cleaning up and preparing to test the route
Navigating off of the crude graph drawing seems problematic, so I will draw something a little cleaner that defines all of the steps a little clearer. Numbers next to the arrows indicate what step of the route I'm on
I also need a rough plan for how I will navigate the Castle Village to ensure I don't miss any sections:
Off to ride:
On to Zwift with my map in hand. After roughly 1 hours 10 minutes of riding and 4 total U turns, all the road segments were covered.
Part of the fun was not knowing what the total distance would come to using an arbitrary weight scale. Could have been 16 miles, could have been 30 miles, who knows? So, I sweated in many ways as the distance gradually ticked up.
I discovered at the end that it's tough to remember exactly where I started, so I stopped the activity a little late. After analyzing the activity in Strava, I discovered that I took me 21.15 mi / 34km to cover all of the roads.
Attempt 1: https://www.strava.com/activities/5352793821
Takeaways & Improvements
One real benefit of this exploration is I got a real good feel for the Yumezi map and think I can comfortably navigate to any portion of it without needing to reference the map at all. I had completed the badge hunt for the new routes prior to this exploration but missed a feel for how everything connected while doing that.
Obviously, the solution is not optimal. It has been demonstrated that ~31-32km is possible adhering roughly to the arbitrary rules.
The following improvements can be made:
- Use actual distance as weights for edges instead of a 1-5 weight scale.
- Use complete map by defining all the roads and intersections in the villages.
- I *think* the program discovers a cycle for the route (ending exactly at the starting point), which is not a requirement here as long as all the road segments are covered. Look into whether this is a setting or update that can be made for the provided code.
Finally, you may ask "why use math here? I can just sit down and trace out a route after a number of tries that is really good." This is really good point for this map, but performing the math around the solution has a number of benefits:
- With the improvements made, an optimal solution can be discovered. You won't really need to question "can I have done better?" if the math is optimal.
- Solving with math and especially with code that takes arbitrary inputs allow for solutions for far more complex maps. Imagine sitting down and trying to trace a route of a real-world city (NYC, Paris, etc..) by hand and how long that would take to feel confident you have the best solution.
- The edge weighting is actually really powerful. What if the requirement was time based (at a given effort) instead of distance based? What if it was to minimize the amount of climbing or time on unpaved surfaces? These variables could be used instead of distance to weight the edges making for flexible problem solving.
I'm not sure if I’ll redo the math or retry a different route, but I am curious what the optimal solution might be. Either way a good adventure into problem solving!
Updated
I went through and measured the distances (in miles) in Strava between all intersections and spawn points. Also, de-simplified the graph such that the castle and village shows all intersections and enumerates those as vertices. I think the application used still only solves complete cycles instead of paths, but the listing of edge ordering at the bottom indicates my latest attempt.
Additional Notes on Running the Program
Steps:
- Clone repository locally:
git clone https://github.com/supermitch/Chinese-Postman.git
- In a text editor, add additional data to data/data.py
For example, I added the following after my updated map (note the third element in each set is still cost, but is approximate miles for each segment in this array. This array is just appended to the end of the existing file.
yumezi_1 = [
(1, 2, 0.5),
(2, 3, 0.5),
(3, 5, 2.2),
(3, 5, 0.5),
(2, 4, 0.5),
(4, 6, 0.8),
(6, 19, 0.1),
(6, 1, 0.65),
(5, 7, 0.3),
(4, 10, 0.4),
(7, 8, 0.4),
(7, 9, 0.1),
(9, 10, 0.1),
(10, 11, 1.0),
(9, 8, 0.4),
(8, 12, 0.6),
(11, 12, 0.1),
(11, 15, 1.2),
(12, 13, 0.4),
(13, 14, 0.3),
(14, 15, 1.0),
(15, 16, 0.3),
(14, 16, 2.5),
(16, 17, 0.5),
(17, 18, 0.7),
(18, 19, 0.4),
(18, 19, 0.4),
(18, 19, 0.3)
]
- Verify the local requirements noted in the repo:
"This program will probably run in Python 2.7 and Python 3.4-3.7. (Tested recently w/ Python 3.7.2)"
- Run the program, specifying the name of the data array to use
python main.py yumezi_1
This is the resulting output:
Loading graph: yumezi_1
<28> edges
Converting to Eularian path...
Doubling dead_ends
Building possible odd node pairs
(91 pairs)
Finding pair solutions
(182 solutions)
Building path sets
Finding cheapest route
Adding new edges
Conversion complete
Added 9 edges
Total cost is 20.55
Attempting to solve Eularian Circuit...
Solved in <1> attempts
Solution: (<37> edges)
[1, 6, 4, 6, 19, 18, 19, 18, 17, 16, 15, 14, 16, 15, 11, 12, 11, 10, 9, 8, 12, 13, 14, 13, 12, 8, 7, 5, 3, 2, 4, 10, 9, 7, 5, 3, 2, 1]
Note that each run of this program can reproduce different results, look at the total cost value and number of edges in the solutionfrom each run, but they should be the same throughout
Additional adjustments:
The program currently starts the path creation from Node 1, we can specify a different starting point by changing line 50 in main.py:
change line from: route, attempts = eularian.eularian_path(graph, start=1)
to: route, attempts = eularian.eularian_path(graph, start=14)
Alternatively, we can force a random starting point:
route, attempts = eularian.eularian_path(graph)