Patent ID: 9219500
Filing Date: 2015-12-22
Classification: G01C,G08G,H03M

Abstract:
1. A method of determining and using cost profiles of routes using map data divided into a plurality of regions, the method comprising using at least one processing apparatus to: search, by the at least one processing apparatus, for one or more routes from an origin to a destination, the search comprising determining whether one or more navigable segments of a set of navigable segments connected to a node are identified by pre-processed minimum cost data as part of a minimum cost path for regions comprising the origin and destination at one or more of a plurality of time periods and, if one or more of the navigable segments of the set are identified as being part of a minimum cost path during at least one of the plurality of time periods, exploring from the set only the one or more navigable segments that are identified as being part of a minimum cost path during at least one of the plurality of time periods, wherein the set of navigable segments comprises segments of navigable paths of the map data, each navigable segment having an associated time varying cost function; determine, by the at least one processing apparatus, a cost profile of the one or more routes over time from the time varying cost functions of the navigable segments that are explored, the cost profile representing the cost of an optimum route between the origin and the destination at different travel times, wherein determining a cost profile of the one or more routes over time comprises combining a first cost profile associated with a first minimum cost path and a second cost profile associated with a second minimum cost path when the first and second minimum cost paths intersect at a node to determine at least one combined cost profile, and further propagating the at least one combined cost profile from the node; and display, by the at least one processing apparatus, the optimum route for a particular travel time based on the determined cost profile or a representation of the determined cost profile on a display.