Apparatus and method for route searching

• US 9,857,187 B2
• Filed: 07/01/2013
• Issued: 01/02/2018
• Est. Priority Date: 06/29/2012
• Status: Active Grant

• Current Assignee: TomTom Navigation B.V (TomTom NV)
• Original Assignee: TomTom Navigation B.V (TomTom NV)
• Inventors: Profous, Andreas, Fischer, Johannes Robert, Menge, Andreas
• Primary Examiner(s): Jos, Basil T.
• Application Number:
  US14/411,552
• Publication Number:
  US 20150149078A1
• Time in Patent Office: 1,646 Days
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G01C 21/3469 Fuel consumption; Energy use; Emission aspects
• CPC Class Codes: G01C 21/3476 using point of interest [POI] information, e.g. a route passing visible POIs
• CPC Class Codes: G01C 21/3679 Retrieval, searching and output of POI information, e.g. hotels, restaurants, shops, filling stations, parking facilities G01C21/3611 takes precedence

Abstract

Embodiments of the present invention provide a one-to-many route searching method comprising searching map data to select links to form a plurality of routes from a departure node according to a cost function, and determining an extent of each route according to an objective function, wherein the searching of the map data is performed to a search boundary based upon a cost of an unreachable node.

Claims

1. A computer implemented method of performing a one-to-many route search on digital map data, said digital map data comprising a plurality of links connected by nodes representing navigable paths of a network, the method comprising:

searching the map data using a one-to-many route planning algorithm to explore links from a departure node so as to determine a reachable area for the departure node, said searching comprising;

determining a first cost for each explored link using a cost function associated with the route planning algorithm; and

determining a second cost for each explored link using an objective function, such that each node reached by the route planning algorithm has a first accumulated cost and a second accumulated cost, wherein the first accumulated cost is the minimum accumulation of first costs for links forming a route from the departure node to the node, wherein the second accumulated cost is the accumulation of second costs for the links forming the route from the departure node to the node, and wherein the reachable area is based on a predetermined second accumulated cost value, such that a node is identified as unreachable when the second accumulated cost for the node exceeds the predetermined second accumulated cost value,

wherein the searching of the map data is limited to a search boundary, wherein the first accumulated cost value defining the search boundary is based upon the first accumulated cost of the first unreachable node identified by the searching of the map data,

the method further comprising;

causing a representation of the determined reachable area to be displayed on a display device.

2. The method of claim 1, wherein the first accumulated cost value defining the search boundary is determined by applying a predetermined factor to the first accumulated cost of the first unreachable node, such that the search boundary extends beyond the first unreachable node.

3. The method of claim 1, wherein the first accumulated cost value defining the search boundary is based upon the first accumulated cost of a plurality of unreachable nodes.

4. The method of claim 3, wherein the first accumulated cost value defining the search boundary is based upon the first plurality of unreachable nodes identified by the searching of the map data.

5. The method of claim 4, wherein the first accumulated cost value defining the search boundary is based upon the average first accumulated cost of the first plurality of unreachable nodes identified by the searching of the map data.

6. The method of claim 1, wherein the first cost for each explored link determined using the cost function associated with the route planning algorithm is based upon one or more of:

length;

travelling time; and

travelling speed of the link.

7. The method of claim 1, where the cost function of the route planning algorithm is selected to determine one of:

shortest routes;

fastest routes; and

most fuel or energy efficient routes, from the departure node.

8. The method of claim 1, wherein the second cost for each explored link determined using the objective function is one of:

energy cost;

travelling time; and

travelling distance, such that the predetermined second accumulated cost value corresponds, respectively, to one of;

a current fuel load of a vehicle;

a maximum travel time; and

a maximum travel distance.

9. The method of claim 1, wherein each link in the map data has an associated importance level, and said searching comprises determining the importance level of a link to be explored from a node and exploring the link only when the importance level is equal to or greater than a predetermined importance level, unless at least one of:

(i) the link is in one or more regions defined around the departure node and/or a node associated with a point of interest (POI); and

(ii) the node was reached from a link having an importance level less than the predetermined importance level.

10. The method of claim 9, wherein the importance level associated with each link is a functional road classification (FRC).

11. The method of claim 9, wherein said displaying comprises:

selecting, for each of a plurality of sub-regions of a region around the departure node, a maximal reachable node, wherein the maximal reachable node is the furthest reachable node in the sub-region from the departure node; and

determining a shape of the reachable area to be displayed by connecting the selected maximal reachable nodes.

12. The method of claim 1, wherein the plurality of links of the map data represent road segments of a road network, and wherein the departure node represents a current location of a vehicle on the road network.

13. A non-transitory computer readable medium comprising instructions that, when executed by one or more processors of a computing device, cause the computing device to perform the method according to claim 1.

14. A computing device, comprising one or more processors and a memory storing digital map data, said digital map data comprising a plurality of links connected by nodes representing navigable paths of a network, the one or more processors being arranged to perform a one-to-many route search on the digital map data by:

searching the map data using a one-to-many route planning algorithm to explore links from a departure node so as to determine a reachable area for the departure node, said searching comprising;

determining a first cost for each explored link using a cost function associated with the route planning algorithm; and

determining a second cost for each explored link using an objective function, such that each node reached by the route planning algorithm has a first accumulated cost and a second accumulated cost, wherein the first accumulated cost is the minimum accumulation of first costs for links forming a route from the departure node to the node, wherein the second accumulated cost is the accumulation of second costs for the links forming the route from the departure node to the node, and wherein the reachable area is based on a predetermined second accumulated cost value, such that a node is identified as unreachable when the second accumulated cost for the node exceeds the predetermined second accumulated cost value, wherein the searching of the map data is limited to a search boundary, wherein the first accumulated cost value defining the search boundary is based upon the first accumulated cost of the first unreachable node identified by the searching of the map data; and

causing a representation of the determined reachable area to be displayed on a display device.

15. A computer implemented method of performing a one-to-many route search on digital map data, said digital map data comprising a plurality of links connected by nodes representing navigable paths of a network, the method comprising:

searching the map data using a one-to-many route planning algorithm to explore links from a departure node representative of a current location of a user so as to determine a reachable area for the departure node, said searching comprising;

determining a first cost for each explored link using a cost function associated with the route planning algorithm; and

determining a second cost for each explored link using an objective function, such that each node reached by the route planning algorithm has a first accumulated cost and a second accumulated cost, wherein the first accumulated cost is the minimum accumulation of first costs for links forming a route from the departure node to the node, wherein the second accumulated cost is the accumulation of second costs for the links forming the route from the departure node to the node, and wherein the reachable area is based on a predetermined second accumulated cost value, such that a node is identified as unreachable when the second accumulated cost for the node exceeds the predetermined second accumulated cost value,

the method further comprising;

obtaining the locations of points of interest (POI) in a region around the departure node, each POI being associated with the nearest node of the map data;

checking, for nodes associated with a POI reached by the route planning algorithm, the reachability of the POI from the departure node, so as to identify at least one POI as reachable;

obtaining availability information for the at least one reachable POI;

using the obtained availability information for a current time or an expected arrival time at each of the at least one reachable POI, so as to identify at least one reachable POI as available;

determining a route from the departure node to an available POI using the map data; and

generating instructions to guide the user along the determined route.

16. The method of claim 15, further comprising using a booking system associated with an available POI to book the POI at the expected arrival time.

17. A non-transitory computer readable medium comprising instructions that, when executed by one or more processors of a computing device, cause the computing device to perform the method according to claim 15.