Navigation devices and methods carried out thereon

Patent metadata

Field	Value
Publication number	US-2016178386-A1
Application number	US-201514949985-A
Country	US
Kind code	A1
Filing date	Nov 24, 2015
Priority date	Jul 9, 2009
Publication date	Jun 23, 2016
Grant date	—

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

1 - 26 . (canceled)

27 . 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 including 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; determine from the cost profile whether at a second travel time within the time window the cost of the route is less than the cost for the first travel time and, when the cost is less, providing an indication informing the user of 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.

28 . The method of claim 27 , 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.

29 . The method of claim 27 , 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.

30 . The method of claim 27 , 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.

31 . The method of claim 27 , 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.

32 . The method of claim 27 , 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.

33 . 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 including 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; determining from the cost profile whether at a second travel time within the time window the cost of the route is less than the cost for the first travel time and, when the cost is less, providing an indication informing the user of the second travel time; receiving 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 causing a display to display an image of the route determined from the cost profile at the second travel time.

34 . The non-transitory computer readable medium of claim 33 , wherein the method further comprises causing 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.

35 . The non-transitory computer readable medium of claim 33 , 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.

36 . The non-transitory computer readable medium of claim 33 , 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 t

Assignees

• Tomtom Navigation Bv

Inventors

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

Classifications

• 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

• G01C21/3664

  Details of the user input interface, e.g. buttons, knobs or sliders, including those provided on a touch screen; remote controllers; input using gestures · CPC title

• G01C21/3446 Primary

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

• H03M7/70

  Type of the data to be coded, other than image and sound · CPC title