Navigation devices and methods carried out thereon
First Claim
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.
7 Assignments
0 Petitions
Accused Products
Abstract
This invention concerns a method of determining a route using map data comprising a plurality of navigable paths, the map data divided into a plurality of regions. The method comprises using at least one processing apparatus to: receive an origin and a destination on the map data and a travel time, determine a route from the origin to the destination using the map data and minimum cost data that identifies minimum cost paths between regions of the map data. The minimum cost data identifies more than one minimum cost path between a pair of the regions if different minimum cost paths exist between the pair of regions at different times and determining a route comprises identifying from the minimum cost paths for the pair of regions comprising the origin and destination, the minimum cost path having a lowest cost at the travel time.
41 Citations
19 Claims
-
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. - View Dependent Claims (2, 4, 5, 6, 7, 8, 9, 10, 11, 18)
-
-
3. A computer device comprising memory having stored therein map data divided into a plurality of regions, the map data comprising:
-
a plurality of navigable segments representing segments of navigable paths of the map data, each navigable segment having an associated time varying cost function; and pre-processed minimum cost data for the navigable segments identifying whether a navigable segment is part of a minimum cost path between regions of the map data at one or more of a plurality of time periods, and a processing apparatus arranged to; search 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 the minimum cost data as part of a minimum cost path for regions comprising the origin and destination 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; determine 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 propagate the at least one combined cost profile from the node; and display 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.
-
-
12. A navigation device comprising:
-
at least one processing apparatus; a memory; and a display, wherein the memory stores map data comprising a plurality of navigable segments representing segments of navigable paths of the map data, each navigable segment having an associated time varying cost function and minimum cost data for the navigable segments identifying whether a navigable segment is part of a minimum cost path between regions of the map data at one or more of a plurality of time periods; and wherein the at least one processing apparatus is operative to;
search 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 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 a 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 a plurality of time periods; anddetermine 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 propagate the at least one combined cost profile from the node; and display the optimum route for a particular travel time based on the determined cost profile or a representation of the determined cost profile on the display. - View Dependent Claims (13, 14, 15, 16, 17, 19)
-
Specification