Booth Id:
MATH011
Category:
Mathematics
Year:
2020
Finalist Names:
Garth, Edward (School: Redeemer Baptist School)
Abstract:
Determining the quickest network route from point A to point B is a common introductory Graph Theory or Combinatorics activity and algorithms such as Dijkstra’s algorithm are effective tools in optimising edge-weightings for each possible route. When applied to road networks, nodes usually represent cities while edges often represent distances or travel costs between cities.
When attempting to develop an algorithm that is better than current available GPS mapping programs, I quickly found that nodal variants associated with intersection dynamics, exponentially increase the complexity of any proposed algorithm. UPS, for example, took 5 years to develop their ORION route-optimization system, improving safety by minimizing left-hand turns.
Over a four-month period during peak travelling hours, 2891 dynamic intersection timings were recorded, from 134 intersection types to determine the average time and standard deviation for each intersection maneuver – used to weight each node. Road types, speed limits and distances between intersections were used to calculate edge-weightings. Converting each node and edge-weighting to a common unit of time, made it feasible to transform doubly-weighted graphs into directed edge-weighted graphs, suitable for performing manual algorithms to compare alternative routes.
Eight routes were randomly selected and my preferred manually calculated route was physically trialed against the Google Maps route. My route proved more reliable (100%), faster (88%) and safer (100%). Of greater global significance for all drivers is that the fastest, safest and most reliable route from A to B is always in a clockwise direction in left-hand-drive countries and anti-clockwise in right-hand drive countries.