Patent Document ID: 10024673
Application ID: 15164390
Patent Status: 1

Claim One:
1. A computer-implemented method for identifying a path of a trip, the method comprising: receiving a plurality of geographic points that describe a trip of a vehicle from a starting location to a destination location, each of the plurality of received geographic points associated with a timestamp, wherein the plurality of received geographic points are global positioning satellite (GPS) points received from a location tracking device located in the vehicle; identifying a set of candidate geographic points for each of the plurality of received geographic points, each candidate geographic point in the set representing a candidate location on a road network that is associated with the received geographic point; determining a graph that includes the sets of candidate geographic points for the plurality of received geographic points, each candidate geographic point arranged in the graph according to the timestamp of the received geographic point that is associated with the candidate geographic point; identifying a plurality of sub-graphs from the graph; iteratively applying an A* algorithm to a subset of the plurality of sub-graphs that evaluates only a portion of all possible edges that connect together the candidate geographic points in the graph without evaluating all of the possible edges, wherein the evaluation comprises initially setting a zero cost for edges of the plurality of sub-graphs; and identifying a shortest path of travel of the vehicle in the trip based on the iterative application of the A* algorithm to the subset of the plurality of sub-graphs, the shortest path of travel including a single candidate geographic point from each set of candidate geographical points.