Techniques for route planning optimization

A computing device, comprising:

• a processor;
• and
• a memory storing computer-readable instructions that, upon execution by the processor, configure the computing device to:
• obtain a navigation graph comprising a first set of nodes and a first set of edges;
• generate an abstract navigation graph from the navigation graph, the abstract navigation graph comprising the first set of nodes, the first set of edges, and a set of maneuver edges, a maneuver edge of the set of maneuver edges representing a traversal time for performing a maneuver between a pair of edges of the first set of edges;
• calculate first time values corresponding to the first set of edges and second time values corresponding to the set of maneuver edges based at least in part on positional data corresponding to historical route traversals by a plurality of computing devices, wherein calculating the first time values and the second time values causes the computing device to:
• calculate a first transit-time value based at least in part on a first subset of the positional data corresponding to first traversals from a first node to a second node utilizing a first edge of the first set of edges, the first node being connected to the second node within the abstract navigation graph via the first edge and a first maneuver edge;
• calculate a second transit-time value based at least in part on a second subset of the positional data corresponding to second traversals from the first node to a third node along the first edge, the first node being connected to the third node within the abstract navigation graph via the first edge and a second maneuver edge;
• assign a minimum transit-time value for the first edge based at least in part on identifying the minimum transit-time value from the first transit-time value and the second transit-time value;
• and
• assign, to the first maneuver edge, a difference value indicating a difference between the first transit-time value and the second transit-time value;
• generate an updated abstract navigation graph comprising the first time values and the second time values;
• and
• calculate one or more navigation routes utilizing the updated abstract navigation graph.

A computer-readable storage medium having stored thereon computer-executable instructions that, when executed by a processor, cause the processor to perform operations comprising:

• obtaining a navigation graph comprising a first set of nodes and a first set of edges;
• generating an abstract navigation graph from the navigation graph, the abstract navigation graph comprising the first set of nodes, the first set of edges, and a set of maneuver edges, a maneuver edge of the set of maneuver edges representing a traversal time for performing a maneuver between a pair of edges of the first set of edges;
• calculating first time values corresponding to the first set of edges, a first time value being calculated based at least in part on a first subset of positional data corresponding to first traversals from a first node to a second node utilizing a first edge of the first set of edges, the first node being connected to the second node within the abstract navigation graph via the first edge and a first maneuver edge;
• calculating second time values corresponding to the set of maneuver edges, a second time value being calculated based at least in part on a second subset of the positional data corresponding to second traversals from the first node to a third node utilizing the first edge, the first node being connected to the third node within the abstract navigation graph via the first edge and a second maneuver edge;
• assigning a minimum time value for the first edge based at least in part on identifying the minimum time value from the first time value and the second time value;
• assigning, to the first maneuver edge, a difference value indicating a difference between the first time value and the second time value;
• generating an updated abstract graph comprising the first time values and the second time values;
• and
• calculating one or more navigation routes utilizing the updated abstract graph.