Navigation devices and methods carried out thereon

Patent metadata

Field	Value
Publication number	US-10132640-B2
Application number	US-201514949985-A
Country	US
Kind code	B2
Filing date	Nov 24, 2015
Priority date	Jul 9, 2009
Publication date	Nov 20, 2018
Grant date	Nov 20, 2018

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.

First claim

The invention claimed is:

1. A method of determining routes from an origin to a destination using map data divided into a plurality of regions, the map data comprising: a plurality of navigable segments representing portions of navigable paths of the map data, each navigable segment having an associated time varying function, the time varying function comprising a value for each of a plurality of different time periods; and minimum cost data for the navigable segments within each region of the map data identifying, for each of the other regions, whether a navigable segment is part of a minimum cost path to the other region at any time period, the method comprising using at least one processing apparatus to:
receive an origin and a destination on the map data;
receive from a user via a user interface a request for a route between the origin and the destination at a first travel time;
determine a time window based on the first travel time, the time window being a span of time that includes corresponding specified amounts of time before and after the first travel time, wherein the time window includes the first travel time;
determine a cost profile for minimum cost routes from the origin to the destination using a route planning algorithm and multiple values of each time varying function of the navigable segments being explored, the cost profile representing the cost of the minimum cost route between the origin and the destination at different travel times within the time window, and wherein determining the cost profile comprises 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, exploring from the set only the one or more navigable segments that are identified as being part of a minimum cost path, wherein the minimum cost data comprises a plurality of bit vectors, each bit vector associated with a different navigable segment and each bit in each bit vector associated with a different destination region, wherein each bit represents whether or not a corresponding navigable segment is part of a minimum cost path to the destination region;
determine a cost of the route for a second travel time from the cost profile, the second travel time being a travel time within the time window;
compare the cost of the route for the second travel time to the cost of the route for the first travel time to determine whether the cost of the route at the second travel time is lower than the cost of the route at the first travel time and, when the cost of the route at the second travel time is lower, providing an indication informing the user of the lower cost at the second travel time;
receive from the user via the user interface a request to change the travel time for the route between the origin and the destination to the second travel time; and
cause a display to display an image of the route determined from the cost profile at the second travel time.

2. The method of claim 1 , wherein the at least one processing apparatus is further arranged to cause the display to display an image of the route determined from the cost profile at the first travel time, and to update the display with the image of the route determined from the cost profile at the second travel time, wherein the updating of the display, in response to the change in the travel time, occurs in real time.

3. The method of claim 1 , wherein determination of the route comprises identifying from the minimum cost data minimum cost paths between a pair of regions independently of time and carrying out a cost analysis for the identified minimum cost paths for one or more relevant times derived from the travel time to determine the minimum cost path at the travel time.

4. The method of claim 1 , wherein the minimum cost data identifies for each minimum cost path a reference time at which the path is the minimum cost path and determining a route comprises selecting a minimum cost path from the minimum cost data having a reference time corresponding to one or more relevant times derived from the travel time.

5. The method of claim 1 , wherein the time varying function associated with each navigable segment of the map data comprises speed profile data identifying the expected speed on navigable segments of the paths at different times.

6. The method of claim 1 , wherein the at least one processing apparatus is further arranged to cause the display of a slider representing the travel time and to update the display with the image of the route determined from the cost profile at the second travel time in response to user interaction with the slider.

7. A non-transitory computer readable medium comprising computer readable instructions which, when executed by one or more processors, cause the one or more processors to perform a method of determining routes from an origin to a destination using map data divided into a plurality of regions, the map data comprising: a plurality of navigable segments representing portions of navigable paths of the map data, each navigable segment having an associated time varying function, the time varying function comprising a value for each of a plurality of different time periods; and minimum cost data for the navigable segments within each region of the map data identifying, for each of the other regions, whether a navigable segment is part of a minimum cost path to the other region at any time period, the method comprising:
receiving an origin and a destination on the map data;
receiving from a user via a user interface a request for a route between the origin and the destination at a first travel time;
determining a time window based on the first travel time, the time window being a span of time that includes corresponding specified amounts of time before and after the first travel time, wherein the time window includes the first travel time;
determining a cost profile for minimum cost routes from the origin to the destination using a route planning algorithm and multiple values of each time varying function of the navigable segments being explored, the cost profile representing the cost of the minimum cost route between the origin and the destination at different travel times within the time window, and wherein determining the cost profile comprises 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, exploring from the set only the one or more navigable segments that are identified as being part of a minimum cost path, wherein the minimum cost data comprises a plurality of bit vectors, each bit vector associated with a different navigable segment and each bit in each bit vector associated with a different destination region, wherein each bit represents whether or not a corresponding navigable segment is part of a minimum cost path to the destination region;
determining a cost of the route for a second travel time from the cost profile, the second travel time being a travel time within the time window;
comparing the cost of the route for the second travel time to the cost of the route for the first travel time to determine whether the cost of the route at the second travel time is lower than the cost of the route at the first travel time and, when the cost of the route at the second travel time is lower, providing an indication informing the user of the lower cost at th

Assignees

• Tomtom Navigation Bv

Inventors

• Schilling Heiko
• Tertoolen Simone Francine
• Gawrilow Ewgenij
• Hilger Moritz
• Profous Andreas
• Werber Jürgen

Classifications

• G01C21/3492

  employing speed data or traffic data, e.g. real-time or historical (traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968) · CPC title

• G01C21/367

  Details, e.g. road map scale, orientation, zooming, illumination, level of detail, scrolling of road map or positioning of current position marker · CPC title

• G01C21/3453 Primary

  Special cost functions, i.e. other than distance or default speed limit of road segments · CPC title

• G08G1/096866

  where the complete route is shown to the driver · CPC title

• G01C21/3446 Primary

  Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes · CPC title