METHODS AND SYSTEMS FOR GENERATING ROUTES USING ELECTRONIC MAP DATA

• US 20170276502A1
• Filed: 09/26/2016
• Published: 09/28/2017
• Est. Priority Date: 03/28/2016
• Status: Active Grant

• Current Assignee: TomTom Navigation B.V (TomTom NV)
• Original Assignee: TomTom International BV (TomTom NV), TomTom Navigation B.V (TomTom NV)
• Inventors: Fischer, Johannes Robert, Dzyuba, Tetyana, Knig, Felix Godafoss, Goverts, Sijtse Thomas
• Granted Patent: US 10,429,202 B2
• Time in Patent Office: Days
• CPC Class Codes: G01C 21/343 Calculating itineraries, i.e. routes leading from a starting point to a series of categorical destinations using a global route restraint, round trips, touristic trips travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047
• 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/3614 through interaction with a road map, e.g. selecting a POI icon on a road map

Abstract

A method and system for generating a route through a navigable network in a geographic area is disclosed, the navigable network being represented by an electronic map comprising a plurality of segments each having a traversal direction associated therewith. An area is defined around a location represented by the electronic map, and at least some of the outgoing segments from the area are determined. A first optimum cost route from an origin is determined to each of the determined outgoing segments, and these routes are ranked according to their cost. At least one of the first optimum cost routes is selected based on the ranking, and a second optimum cost route is determined from the outgoing segment from the area of the selected route to a destination. The generated route from the origin to the destination comprises the selected first optimum cost route and the second optimum cost route.

Claims

1. A method of generating a route through a navigable network in a geographic area, the navigable network being represented by an electronic map comprising a plurality of segments representing navigable elements of the navigable network, the plurality of segments being connected by nodes, and each segment having a traversal direction associated therewith, the method comprising using at least one processor to:

receive location data identifying a location represented by the electronic map;

define an area represented by the electronic map based on the received location data;

determine at least some of the outgoing segments from the defined area;

determine, for each of the determined outgoing segments from the defined area, a first optimum cost route from an origin to the respective outgoing segment using a route planning algorithm, each first optimum cost route having an associated cost;

select at least one of the first optimum cost routes based on the associated cost;

determine a second optimum cost route to a destination from the outgoing segment from the area of the at least one selected first optimum cost route; and

output for provision to a user at least one of;

data indicative of the generated route; and

a set of navigation instructions for guiding the user along at least a portion of the generated route, wherein the generated route from the origin to the destination comprises the selected first optimum cost route and the second optimum cost route.

2. The method of claim 1, further comprising ranking, using the at least one processor, the determined first optimum cost routes according to their cost, and wherein said selecting of the at least one of the first optimum cost routes is based on the ranking.

3. The method of claim 1, wherein the location data is received from the user.

4. The method of claim 1, wherein the location identified by the location data is a point location, and the area is defined as a circle centred on the point location.

5. The method of claim 1, wherein said defining of the area comprises defining an initial area based on the received location data, determining whether the initial area includes at least a predetermined number of outgoing segments from the area, and, where the area is found not to include at least the predetermined number of outgoing segments, increasing the size of the initial area until the area is found to include at least the predetermined number of outgoing segments from the area.

6. The method of claim 5, wherein the predetermined number of outgoing segments from the area is two outgoing segments.

7. The method of claim 1, wherein the origin is a point location and is one of:

(i) a current location of a user; and

(ii) a node associated with an outgoing segment from a second defined area.

8. The method of claim 1, wherein said selecting at least one of the first optimum cost routes comprises selecting a set of first optimum cost routes, said set including the first optimum cost route with the lowest associated cost and a predetermined number of first optimum cost routes with the next lowest associated costs.

9. The method of claim 1, wherein the destination is a point location and is one of:

(i) a location selected by a user; and

(ii) a node associated with an outgoing segment from a second defined area.

10. The method of claim 1, wherein the received location data identifies a plurality of locations indicative of waypoints to be included in the route, and an area is defined for each of said plurality of locations, and the method further comprises receiving data indicative of an order in which the locations along the route are to be traversed.

11. The method of claim 1, wherein each first optimum cost route comprises at least one segment, and the second optimum cost route is determined using a route planning algorithm that prevents any segment of at least one of the first optimum cost routes from forming part of the second optimum cost route.

20. A non-transitory computer readable medium comprising instructions which, when executed by at least one processor of a computing device, cause the computing device to operate according to the method of claim 1.

12. A computing device for generating a route through a navigable network in a geographic area, the navigable network being represented by an electronic map comprising a plurality of segments representing navigable elements of the navigable network, the plurality of segments being connected by nodes, and each segment having a traversal direction associated therewith, the computing device comprising at least one processor and a memory, wherein the at least one processor is arranged to:

receive location data identifying a location represented by the electronic map;

define an area represented by the electronic map based on the received location data;

determine at least some of the outgoing segments from the defined area;

determine, for each of the determined outgoing segments from the defined area, a first optimum cost route from an origin to the respective outgoing segment using a route planning algorithm, each first optimum cost route having an associated cost;

select at least one of the first optimum cost routes based on the associated cost;

determine a second optimum cost route to a destination from the outgoing segment from the area of the at least one selected first optimum cost route; and

output for provision to a user at least one of;

data indicative of the generated route; and

a set of navigation instructions for guiding the user along at least a portion of the generated route, wherein the generated route from the origin to the destination comprises the selected first optimum cost route and the second optimum cost route.

13. The computing device of claim 12, wherein the at least one processor is further arranged to rank the determined first optimum cost routes according to their cost, and wherein said selecting of the at least one of the first optimum cost routes is based on the ranking.

14. The computing device of claim 12, wherein the location data is received from the user.

15. The computing device of claim 12, wherein the location identified by the location data is a point location, and the area is defined as a circle centred on the point location.

16. The computing device of claim 12, wherein said defining of the area comprises defining an initial area based on the received location data, determining whether the initial area includes at least a predetermined number of outgoing segments from the area, and, where the area is found not to include at least the predetermined number of outgoing segments, increasing the size of the initial area until the area is found to include at least the predetermined number of outgoing segments from the area.

17. The computing device of claim 12, wherein said selecting at least one of the first optimum cost routes comprises selecting a set of first optimum cost routes, said set including the first optimum cost route with the lowest associated cost and a predetermined number of first optimum cost routes with the next lowest associated costs.

18. The computing device of claim 12, wherein the received location data identifies a plurality of locations indicative of waypoints to be included in the route, and an area is defined for each of said plurality of locations, and the at least one processor is arranged to receive data indicative of an order in which the locations along the route are to be traversed.

19. The computing device of claim 12, wherein each first optimum cost route comprises at least one segment, and the second optimum cost route is determined using a route planning algorithm that prevents any segment of at least one of the first optimum cost routes from forming part of the second optimum cost route.