APPARATUS AND METHODS OF DETERMINING PATHS THROUGH AN ELECTRONIC MAP

• US 20160245663A1
• Filed: 10/30/2014
• Published: 08/25/2016
• Est. Priority Date: 10/31/2013
• Status: Active Grant

• Current Assignee: TomTom International BV (TomTom NV)
• Original Assignee: TomTom Navigation B.V (TomTom NV)
• Inventors: Schultz, Jeroen Razoux, van der Vlist, Bram Jan Jacobus, van Dok, Cornelis Klaas, Gawrilow, Ewgenij
• Granted Patent: US 10,168,171 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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/3476 using point of interest [POI] information, e.g. a route passing visible POIs
• CPC Class Codes: G01C 21/3484 Personalized, e.g. from learned user behaviour or user-defined profiles
• CPC Class Codes: G01C 21/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 Class Codes: G01C 21/3605 Destination input or retrieval
• CPC Class Codes: G01C 21/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 Class Codes: G01C 21/3676 Overview of the route on the road map

Abstract

A plurality of routes through a navigable network represented by an electronic map are stored by a navigation device. Each route is defined as a plurality of point locations to be travelled between in a predefined order. The device receives a selection of one of the plurality of stored routes from a user, and determines a minimum cost path along segments of the electronic map between the plurality of point locations of the selected route. The minimum cost path traverses the plurality of point locations in an order based on the predefined order associated with the selected route. The device then outputs a set of navigation instructions to the user for guiding the user along the route.

Claims

1. A method of generating a minimum cost path through a navigable network, the navigable network being represented by an electronic map comprising a plurality of segments representing navigable segments of the navigable network, the method comprising:

receiving a selection of one of a plurality of stored routes, each of the stored routes being defined as a plurality of point locations to be travelled between in a predefined order; and

determining a minimum cost path along segments of the electronic map between the plurality of point locations of the selected route, the minimum cost path traversing the plurality of point locations in an order based on the predefined order associated with the selected route.

2. The method of claim 1, wherein the plurality of point locations include a starting location and a destination location, and one or more intermediate locations.

3. The method of claim 1, wherein one or more, and optionally all, of the stored routes are defined by a user.

4. The method of claim 1, wherein a user may change the order of the point locations defining a stored route and/or modify the point locations defining a stored route.

5. The method of claim 1, wherein each of the routes is stored in association with an identifier that allows a user to select their desired route, and wherein the user uses the identifier to select the desired route from the plurality of stored routes.

6. The method of claim 1, comprising determining a current location of the device, and wherein the determining a minimum cost path comprises determining a minimum cost path from the current location of the device to the first point location of the selected route and then on to the last point location of the selected route.

7. The method of claim 1, wherein a user, after a stored route has been selected, indicates that a reverse route is to be determined, the method comprising determining the minimum cost path so as to traverse the plurality of point locations in the inverse of the predefined order associated with the selected route.

8. The method of claim 1, wherein the minimum cost path is determined taking into account traffic events on the network.

9. The method of claim 1, further comprising providing navigation instructions to a user to guide the user along the determined minimum cost path.

10. The method of claim 1, wherein the stored route is further defined by data indicative of a polyline, the polyline representing a route between said point locations, wherein the method further comprises using the polyline data in determining the minimum cost path along segments of the electronic map between the plurality of point locations.

11. The method of claim 10, wherein the determining a minimum cost path comprises favoring segments of the electronic map for inclusion in the determined path that are in greater proximity to the polyline as represented on the electronic map.

14. 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 perform the method of claim 1.

12. A device for generating a minimum cost path through a navigable network, the navigable network being represented by an electronic map comprising a plurality of segments representing navigable segments of the navigable network, the device comprising:

a memory storing a plurality of routes, each of the stored routes being defined as a plurality of point locations to be travelled between in a predefined order; and

one or more processors arranged to;

receive a selection of one of the plurality of stored routes; and

determine a minimum cost path along segments of the electronic map between the plurality of point locations of the selected route, the minimum cost path traversing the plurality of point locations in an order based on the predefined order associated with the selected route.

13. (canceled)