The Problem¶
When we first wanted to find the shortest route throughout PSP we looked into combinatorial optimization in graph theory, quickly finding the Chinese Postman Problem, an algorithm to find the shortest closed path or circuit to that visits every edge of a graph at least once.
Note the distinction from the Travelling Salesman Problem, that aims to visit every node at least once. Using this algorithm would provide the shortest path across all trail junctions, rather than the shortest path across all trails.
The Math¶
Suppose we have a weighted graph of the park $G = (V, E)$
Where $V = nodes/intersections$ & $E = edges/trail$
With each edge/trail having a length $w(e)$
Our goal is then: $min(total\,route\,length)$ where every edge $e \in E$ is covered at least once
Note that PSP is not a Euler circuit, i.e you can't start somewhere, travel every edge once, and return to where you started, if this was the case the optimal path would be a simple traversal circling all trails with a length equal to the sum of lengths $\sum w(e)$
Thus our total length looks more like: $\sum w(e) + minimum\,repeated\, distance$
A graph always has an even number of odd-degree nodes (a node with 1,3,5,etc connections), this set of odd-degree nodes is defined as: $O = \{v_{1},v_{2},...,v_{2k} \}$
Said odd nodes must be paired with duplicate paths to Eluerize a graph. The combination of two odd notes with a duplicate path creates a parity flip, a node only visited 3 times would be visited a 4th time by the duplicated path. Given that we don't need to finish where we started we also can leave 2 odd nodes (Eulers path rather than Eulers circuit, 'open' CPP).
This becomes: $min_{M,s,t}\sum_{(i,j) \in M} d(v_{i}, v_{j})$ where $M$ is a matching of nodes except s & t, and $d(v_{i}, v_{j})$ is the shortest distnace between odd nodes $v_{i}$ and $v_{j}$
Thus the algorithm to solving the Chinese Postman Length is:
$Optimal\,Length = \sum_{e \in E} w(e) + min_{M,s,t} \sum_{i,j \in M}d(v_{i}, v_{j})$
or Optimal Length = sum of all lengths + shortest way to pair odd nodes except entry and exit
A Simple Example¶
Suppose a graph has 4 odd nodes: $A,B,C,D$ with path distances:
$A-B = 3, \, A-C=5, \, A-D=4, \, B-C=6, \, B-D=2, \, C-D=7$
Given that we can leave 2 nodes unmatched we only need to pair 2 of the 4 nodes, the shortest pairing is B-D. Thus the shortest path is: 27 (original length) + 2 (shortest duplicate length)
The Code¶
The following code takes this logic and creates an optimal path across the parks trail system. It takes in a list of edges, i.e distances between nodes (junctions/entrances) and returns an ordered list that traverses the nodes in the shortest possible way.
For example: graph = {(A,B): 3, (A,C):5, (A,D):4, ...}
The list of nodes and edge connections is hand calculated given the city of Vancouvers park map, with edge lengths calculated using plotaroute.com (in KM)
In [37]:
import sys
print(sys.executable)
print(sys.version)
/usr/local/bin/python3 3.13.0 (v3.13.0:60403a5409f, Oct 7 2024, 00:37:40) [Clang 15.0.0 (clang-1500.3.9.4)]
In [72]:
import ast
import math
import heapq
import networkx as nx
# returns the distance and shortest path between two nodes given graph
def dijkstra(graph, start_node, end_node):
# Stores shortest known distance from start to each node
distances = {node: math.inf for node in graph}
distances[start_node] = 0
# Stores previous node so we can rebuild the path later
previous = {node: None for node in graph}
# Current distance and current node
queue = [(0, start_node)]
# Priority queue
while queue:
current_distance, current_node = heapq.heappop(queue)
# if already found better way, skip
if current_distance > distances[current_node]:
continue
# stop once destination is reached
if current_node == end_node:
break
# check each neighbor
for neighbor, distance in graph[current_node]:
new_distance = current_distance + distance
if new_distance < distances[neighbor]:
distances[neighbor] = new_distance
previous[neighbor] = current_node
heapq.heappush(queue, (new_distance, neighbor))
# rebuild shortest path
path = []
current_node = end_node
# follow "previous" back to start_node
while current_node is not None:
path.append(current_node)
current_node = previous[current_node]
path.reverse()
# return and exceptions
if distances[end_node] == math.inf:
return math.inf, []
return distances[end_node], path
# returns a eulers path
def hierholzer(graph, start, end):
graph = {
node: connections.copy()
for node, connections in graph.items()
}
stack = [start]
path = []
while stack:
curr = stack[-1]
if graph[curr]:
next_node, distance = graph[curr].pop()
# remove reverse edge
for i, (neighbor, d) in enumerate(graph[next_node]):
if neighbor == curr and d == distance:
graph[next_node].pop(i)
break
stack.append(next_node)
else:
path.append(stack.pop())
path.reverse()
return path
def pathCheck(path, graph):
total = 0
for i in range(len(path)-1):
a = path[i]
b = path[i+1]
distance = next(d for neighbor, d in graph[a] if neighbor == b)
total += distance
return total
# Read edge list
with open("psp_adj_list.txt", "r") as file:
edges = ast.literal_eval(file.read())
# Build graph as an adjacency list
graph = {}
for (a, b), distance in edges.items():
graph.setdefault(a, []).append((b, distance))
graph.setdefault(b, []).append((a, distance))
# Find all odd degree nodes (110/145)
odd_nodes = []
for node, connections in graph.items():
if len(connections) % 2 == 1:
odd_nodes.append(node)
# Choose our entry and exit nodes
entry_node = 200
exit_node = 301
odd_nodes.remove(entry_node)
odd_nodes.remove(exit_node)
# Compute shortest paths between every pair of odd degree nodes
shortest_paths = {}
for node in odd_nodes:
for other_node in odd_nodes:
if node != other_node:
pair = tuple(sorted((node, other_node)))
if pair not in shortest_paths:
distance, path = dijkstra(graph, node, other_node)
shortest_paths[pair] = {
"distance":distance,
"path":path
}
# Gave up on pairing using recurssion due to 109! computations, doing this instead, returns optimal pairings, paths, and distances
odd_matching_graph = nx.Graph()
for (u, v), info in shortest_paths.items():
odd_matching_graph.add_edge(u, v, weight=info["distance"])
best_matching = nx.algorithms.matching.min_weight_matching( # optimal matches
odd_matching_graph,
weight="weight"
)
paths_to_duplicate = [] # paths for each match
for u, v in best_matching:
pair = tuple(sorted((u, v)))
paths_to_duplicate.append(shortest_paths[pair]["path"])
matching_length = 0 # length of matches
for (u, v) in best_matching:
pair = tuple(sorted((u,v)))
matching_length += shortest_paths[pair]["distance"]
# sum of distances in park then adding matching_length
park_length = 0
for node in graph:
for neighbor, distance in graph[node]:
park_length += distance
park_length = park_length/2
# Total Distance of the traverse
total_length = matching_length + park_length
print(total_length)
# now we have two graphs, the original and complete 'graph' and the duplicated 'odd_matching_graph'
augmented_graph = {
node: connections.copy()
for node, connections in graph.items()
}
# take all the duplicate paths from odd_matching_graph and add them augmented_graph
for (u, v) in best_matching:
pair = tuple(sorted((u, v)))
path = shortest_paths[pair]["path"]
for i in range(len(path) - 1):
a = path[i]
b = path[i + 1]
# find the distance between a and b in original graph
distance = next(d for neighbor, d in graph[a] if neighbor == b)
# add duplicated edge in both directions
augmented_graph[a].append((b, distance))
augmented_graph[b].append((a, distance))
print(augmented_graph)
# Hierholzer's algorithm on augmented graph
path = hierholzer(augmented_graph, entry_node, exit_node)
print(path)
print(pathCheck(path, graph))
54.267999999999965
{100: [(101, 0.146), (125, 0.026), (202, 0.92), (125, 0.026)], 101: [(100, 0.146), (102, 0.782), (122, 0.029), (122, 0.029)], 125: [(100, 0.026), (100, 0.026)], 102: [(101, 0.782), (103, 0.136), (116, 0.748), (116, 0.748)], 122: [(101, 0.029), (101, 0.029)], 103: [(102, 0.136), (123, 0.099), (104, 0.126), (123, 0.099)], 116: [(102, 0.748), (114, 0.248), (117, 0.072), (102, 0.748)], 123: [(103, 0.099), (103, 0.099)], 104: [(103, 0.126), (105, 0.333), (111, 0.088), (111, 0.088)], 105: [(104, 0.333), (106, 0.087), (107, 0.103), (107, 0.103)], 111: [(104, 0.088), (110, 0.094), (113, 0.204), (104, 0.088)], 106: [(105, 0.087), (108, 0.144), (124, 0.091), (124, 0.091)], 107: [(105, 0.103), (108, 0.074), (109, 0.047), (105, 0.103)], 108: [(106, 0.144), (107, 0.074), (109, 0.099), (119, 0.68)], 124: [(106, 0.091), (106, 0.091)], 109: [(107, 0.047), (108, 0.099), (110, 0.193), (110, 0.193)], 119: [(108, 0.68), (118, 0.307), (120, 0.065), (120, 0.065)], 110: [(109, 0.193), (111, 0.094), (112, 0.123), (109, 0.193)], 112: [(110, 0.123), (113, 0.045), (115, 0.285), (113, 0.045)], 113: [(111, 0.204), (112, 0.045), (114, 0.29), (112, 0.045)], 115: [(112, 0.285), (114, 0.091), (118, 0.247), (114, 0.091)], 114: [(113, 0.29), (115, 0.091), (116, 0.248), (115, 0.091)], 118: [(115, 0.247), (117, 0.058), (119, 0.307), (209, 0.356)], 117: [(116, 0.072), (118, 0.058)], 120: [(119, 0.065), (121, 0.198), (210, 0.419), (121, 0.198), (210, 0.419), (119, 0.065)], 121: [(120, 0.198), (120, 0.198)], 202: [(100, 0.92), (201, 0.082), (205, 0.301), (201, 0.082)], 209: [(118, 0.356), (208, 0.641), (210, 0.071), (210, 0.071)], 210: [(120, 0.419), (209, 0.071), (211, 0.138), (120, 0.419), (209, 0.071), (211, 0.138)], 200: [(201, 0.077)], 201: [(200, 0.077), (202, 0.082), (204, 0.282), (202, 0.082)], 204: [(201, 0.282), (203, 0.053), (205, 0.127), (206, 0.229), (203, 0.053), (205, 0.127)], 205: [(202, 0.301), (204, 0.127), (207, 0.179), (208, 0.177), (204, 0.127), (208, 0.177)], 203: [(204, 0.053), (204, 0.053)], 206: [(204, 0.229), (207, 0.044), (212, 0.219), (212, 0.219)], 207: [(205, 0.179), (206, 0.044), (208, 0.046), (213, 0.293)], 208: [(205, 0.177), (207, 0.046), (209, 0.641), (205, 0.177)], 212: [(206, 0.219), (206, 0.219)], 213: [(207, 0.293), (214, 0.018), (301, 0.501), (214, 0.018)], 211: [(210, 0.138), (210, 0.138)], 214: [(213, 0.018), (213, 0.018)], 301: [(213, 0.501), (302, 0.231), (303, 0.373)], 302: [(301, 0.231), (303, 0.292), (310, 0.12), (310, 0.12)], 303: [(301, 0.373), (302, 0.292), (304, 0.563), (309, 0.165)], 310: [(302, 0.12), (309, 0.396), (311, 0.172), (412, 0.513), (302, 0.12), (412, 0.513)], 304: [(303, 0.563), (305, 0.218), (307, 0.155), (308, 0.226)], 309: [(303, 0.165), (308, 0.404), (310, 0.396), (433, 0.503)], 305: [(304, 0.218), (319, 0.088), (306, 0.074), (319, 0.088)], 307: [(304, 0.155), (306, 0.121), (317, 0.141), (317, 0.141)], 308: [(304, 0.226), (309, 0.404), (433, 0.245), (433, 0.245)], 319: [(305, 0.088), (305, 0.088)], 306: [(305, 0.074), (318, 0.039), (307, 0.121), (318, 0.039)], 318: [(306, 0.039), (306, 0.039)], 317: [(307, 0.141), (307, 0.141)], 311: [(310, 0.172), (312, 0.071), (313, 0.086), (313, 0.086)], 312: [(311, 0.071), (313, 0.042), (314, 0.02), (401, 0.604)], 313: [(311, 0.086), (312, 0.042), (314, 0.043), (315, 0.059), (311, 0.086), (315, 0.059)], 314: [(313, 0.043), (312, 0.02), (316, 0.036), (316, 0.036)], 315: [(313, 0.059), (313, 0.059)], 316: [(314, 0.036), (314, 0.036)], 433: [(308, 0.245), (309, 0.503), (431, 0.28), (308, 0.245)], 412: [(310, 0.513), (410, 0.736), (413, 0.554), (310, 0.513)], 401: [(312, 0.604), (400, 0.077), (403, 0.16), (400, 0.077)], 400: [(401, 0.077), (401, 0.077)], 403: [(401, 0.16), (402, 0.07), (409, 0.273), (402, 0.07)], 402: [(403, 0.07), (403, 0.07)], 409: [(403, 0.273), (406, 0.067), (410, 0.032), (410, 0.032)], 404: [(405, 0.013), (405, 0.013)], 405: [(404, 0.013), (406, 0.039), (407, 0.114), (404, 0.013), (406, 0.039), (407, 0.114)], 406: [(405, 0.039), (408, 0.225), (409, 0.067), (405, 0.039)], 407: [(405, 0.114), (405, 0.114)], 408: [(406, 0.225), (486, 0.062), (411, 0.185), (486, 0.062)], 486: [(408, 0.062), (408, 0.062)], 411: [(408, 0.185), (410, 0.317), (415, 0.14), (416, 0.113), (410, 0.317), (416, 0.113)], 410: [(409, 0.032), (411, 0.317), (412, 0.736), (414, 0.325), (409, 0.032), (411, 0.317)], 414: [(410, 0.325), (413, 0.137), (415, 0.244), (428, 0.316)], 415: [(411, 0.14), (414, 0.244), (417, 0.064), (420, 0.229)], 416: [(411, 0.113), (417, 0.145), (418, 0.33), (487, 0.19), (411, 0.113), (487, 0.19)], 413: [(412, 0.554), (414, 0.137), (429, 0.114), (429, 0.114)], 429: [(413, 0.114), (428, 0.212), (430, 0.195), (413, 0.114)], 428: [(414, 0.316), (422, 0.387), (427, 0.487), (429, 0.212)], 417: [(415, 0.064), (416, 0.145), (419, 0.275), (420, 0.221)], 420: [(415, 0.229), (417, 0.221), (421, 0.223), (421, 0.223)], 418: [(416, 0.33), (419, 0.279), (439, 0.133), (440, 0.549), (419, 0.279), (439, 0.133)], 487: [(416, 0.19), (416, 0.19)], 419: [(417, 0.275), (418, 0.279), (421, 0.473), (418, 0.279)], 439: [(418, 0.133), (418, 0.133)], 440: [(418, 0.549), (442, 1.771)], 421: [(419, 0.473), (420, 0.223), (422, 0.044), (420, 0.223)], 422: [(421, 0.044), (423, 0.194), (428, 0.387), (423, 0.194)], 423: [(422, 0.194), (424, 0.177), (443, 1.647), (422, 0.194)], 424: [(423, 0.177), (425, 0.164), (427, 0.387), (425, 0.164)], 443: [(423, 1.647), (442, 0.073), (444, 0.258), (448, 0.799)], 425: [(424, 0.164), (426, 0.283), (450, 0.728), (424, 0.164)], 427: [(424, 0.387), (426, 0.648), (428, 0.487), (434, 0.11)], 426: [(425, 0.283), (427, 0.648), (436, 0.819), (455, 0.167)], 450: [(425, 0.728), (448, 0.36), (451, 0.476), (448, 0.36)], 436: [(426, 0.819), (435, 0.29), (437, 0.313), (438, 0.314)], 455: [(426, 0.167), (451, 0.047), (453, 0.06), (453, 0.06)], 434: [(427, 0.11), (435, 0.065)], 430: [(429, 0.195), (431, 0.202)], 431: [(430, 0.202), (432, 0.104), (433, 0.28), (432, 0.104)], 432: [(431, 0.104), (435, 0.349), (483, 0.398), (431, 0.104), (435, 0.349), (483, 0.398)], 435: [(432, 0.349), (434, 0.065), (436, 0.29), (432, 0.349)], 483: [(432, 0.398), (432, 0.398)], 437: [(436, 0.313), (438, 0.21), (484, 0.192), (488, 0.07), (484, 0.192), (488, 0.07)], 438: [(436, 0.314), (437, 0.21), (454, 0.89), (485, 0.426)], 484: [(437, 0.192), (437, 0.192)], 488: [(437, 0.07), (437, 0.07)], 454: [(438, 0.89), (460, 0.21)], 485: [(438, 0.426), (456, 0.374)], 442: [(440, 1.771), (443, 0.073), (444, 0.166), (444, 0.166)], 444: [(442, 0.166), (443, 0.258), (445, 0.321), (442, 0.166)], 448: [(443, 0.799), (446, 0.075), (450, 0.36), (450, 0.36)], 445: [(444, 0.321), (446, 0.863)], 446: [(445, 0.863), (447, 0.128), (448, 0.075), (449, 0.417), (447, 0.128), (449, 0.417)], 447: [(446, 0.128), (446, 0.128)], 449: [(446, 0.417), (446, 0.417)], 451: [(450, 0.476), (452, 0.034), (455, 0.047), (452, 0.034)], 452: [(451, 0.034), (451, 0.034)], 453: [(455, 0.06), (455, 0.06)], 460: [(454, 0.21), (461, 0.014), (462, 0.009), (462, 0.009)], 456: [(457, 0.019), (458, 0.014), (485, 0.374), (458, 0.014)], 457: [(456, 0.019), (458, 0.014), (459, 0.126), (459, 0.126)], 458: [(456, 0.014), (457, 0.014), (467, 0.133), (456, 0.014)], 459: [(457, 0.126), (457, 0.126)], 467: [(458, 0.133), (468, 0.031), (469, 0.065), (469, 0.065)], 461: [(460, 0.014), (462, 0.011), (465, 0.043), (469, 0.481)], 462: [(460, 0.009), (461, 0.011), (465, 0.041), (460, 0.009)], 465: [(461, 0.043), (462, 0.041), (466, 0.047), (466, 0.047)], 469: [(461, 0.481), (467, 0.065), (468, 0.045), (467, 0.065)], 466: [(465, 0.047), (465, 0.047)], 468: [(467, 0.031), (469, 0.045), (470, 0.133), (470, 0.133)], 470: [(468, 0.133), (471, 0.041), (473, 0.165), (468, 0.133)], 471: [(470, 0.041), (472, 0.103), (473, 0.068), (472, 0.103)], 473: [(470, 0.165), (471, 0.068), (474, 0.028), (475, 0.06), (474, 0.028), (475, 0.06)], 472: [(471, 0.103), (471, 0.103)], 474: [(473, 0.028), (473, 0.028)], 475: [(473, 0.06), (476, 0.017), (479, 0.193), (473, 0.06), (479, 0.193), (476, 0.017)], 476: [(475, 0.017), (477, 0.018), (478, 0.015), (477, 0.018), (478, 0.015), (475, 0.017)], 479: [(475, 0.193), (480, 0.02), (481, 0.254), (480, 0.02), (481, 0.254), (475, 0.193)], 477: [(476, 0.018), (476, 0.018)], 478: [(476, 0.015), (476, 0.015)], 480: [(479, 0.02), (479, 0.02)], 481: [(479, 0.254), (479, 0.254)]}
[200, 201, 202, 201, 204, 205, 208, 205, 204, 203, 204, 206, 212, 206, 207, 208, 209, 210, 211, 210, 209, 118, 119, 120, 210, 120, 121, 120, 119, 108, 109, 110, 109, 107, 105, 107, 108, 106, 124, 106, 105, 104, 111, 104, 103, 123, 103, 102, 116, 117, 118, 115, 114, 115, 112, 113, 112, 110, 111, 113, 114, 116, 102, 101, 122, 101, 100, 125, 100, 202, 205, 207, 213, 214, 213, 301, 303, 309, 433, 308, 433, 431, 432, 483, 432, 435, 432, 431, 430, 429, 413, 429, 428, 427, 434, 435, 436, 438, 485, 456, 458, 456, 457, 459, 457, 458, 467, 469, 467, 468, 470, 473, 475, 476, 478, 476, 477, 476, 475, 479, 481, 479, 480, 479, 475, 473, 474, 473, 471, 472, 471, 470, 468, 469, 461, 465, 466, 465, 462, 460, 462, 461, 460, 454, 438, 437, 488, 437, 484, 437, 436, 426, 455, 453, 455, 451, 452, 451, 450, 448, 450, 425, 424, 425, 426, 427, 424, 423, 422, 423, 443, 448, 446, 449, 446, 447, 446, 445, 444, 442, 444, 443, 442, 440, 418, 439, 418, 419, 418, 416, 487, 416, 411, 416, 417, 420, 421, 420, 415, 417, 419, 421, 422, 428, 414, 415, 411, 410, 411, 408, 486, 408, 406, 405, 407, 405, 404, 405, 406, 409, 410, 409, 403, 402, 403, 401, 400, 401, 312, 314, 316, 314, 313, 315, 313, 311, 313, 312, 311, 310, 412, 413, 414, 410, 412, 310, 302, 310, 309, 308, 304, 307, 317, 307, 306, 318, 306, 305, 319, 305, 304, 303, 302, 301]
54.26799999999998