Measuring quality in optimal navigation routes by navigation systems

• US 9,513,132 B2
• Filed: 08/21/2014
• Issued: 12/06/2016
• Est. Priority Date: 08/21/2014
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: HERE Global B.V. (Nokia Corporation)
• Inventors: Fowe, James Adeyemi
• Primary Examiner(s): Shaawat, Mussa A
• Application Number:
  US14/465,531
• Publication Number:
  US 20160054135A1
• Time in Patent Office: 838 Days
• US Class Current: 1/1
• CPC Class Codes: G01C 21/30 Map- or contour-matching
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes

Abstract

Systems, methods, and apparatuses are provided for measuring quality in optimal navigation routes. A plurality of nodes having latitude and longitude coordinates is received for analysis. The nodes may be map matched with a road network and a traveled route of the navigation device may be determined. Alternative routes may be calculated between the origin and destination of the traveled route at a time after the traveled route is completed. Comparisons may be made between the traveled route and the alternative routes. The comparison data may be used to develop an improved traffic database or the data may be reported to a navigation device or navigation service provider.

Claims

1. A method comprising:

receiving, using a processor, a plurality of nodes from a navigation device, each node comprising latitude and longitude coordinates and a time stamp;

map matching the plurality of nodes with a road network;

determining, using the map matched nodes, a traveled route of the navigation device between an origin and destination;

calculating an alternative route between the origin and destination at a time after the traveled route is completed;

comparing the alternative route with the traveled route to provide comparison data, wherein the comparing comprises determining;

a difference in total travel time between the alternative route and the traveled route, a difference in total travel distance between the alternative route and the traveled route, or a combination thereof; and

reporting the comparison data to the navigation device or a navigation service provider.

2. The method of claim 1, wherein the receiving comprises pushing the plurality of nodes to a map developer through a hypertext transfer protocol interface.

3. The method of claim 1, wherein the traveled route is determined using an A* algorithm.

4. The method of claim 1, wherein the alternative route is calculated using current real-time traffic data, historical traffic data, forecasted traffic data, posted speed limit data, or combinations thereof.

5. The method of claim 1, wherein the alternative route is calculated using a decreased order of time search algorithm.

6. The method of claim 1, further comprising ascertaining an overall score for the alternative route based on the comparison data.

7. The method of claim 1, further comprising updating a map database of potential travel paths using the comparison data.

8. A method comprising:

receiving, using a processor, a plurality of nodes from a navigation device, each node comprising latitude and longitude coordinates and a time stamp;

map matching the plurality of nodes with a road network;

determining, using the map matched nodes, a traveled route of the navigation device between an origin and destination;

calculating a faster alternative route between the origin and destination, at a time after the traveled route is completed, using current real-time traffic data, historical traffic data, forecasted traffic data, posted speed limit data, or combinations thereof;

comparing the faster alternative route with the traveled route to provide comparison data including a difference in total travel time between the faster alternative route and the traveled route; and

reporting the comparison data to the navigation device or a navigation service provider.

9. An apparatus comprising:

at least one processor; and

at least one non-transitory memory including computer program code for one or more programs;

the at least one non-transitory memory and the computer program code configured to, with the at least one processor, cause the apparatus to at least perform;

receive plurality of nodes from a navigation device, each node comprising latitude and longitude coordinates and a time stamp;

map match the plurality of nodes with a road network;

determine, using the map matched nodes, a traveled route of the navigation device between an origin and destination;

calculate an alternative route between the origin and destination at a time after the traveled route is completed;

compare the alternative route with the traveled route to provide comparison data, wherein the comparing comprises determining;

a difference in total travel time between the alternative route and the traveled route, a difference in total travel distance between the alternative route and the traveled route, or a combination thereof; and

report the comparison data to the navigation device or a navigation service provider.

10. The apparatus of claim 9, wherein the plurality of nodes is received by pushing the plurality of nodes through a hypertext transfer protocol interface.

11. The apparatus of claim 9, wherein the traveled route is determined using an A* algorithm.

12. The apparatus of claim 9, wherein the alternative route is calculated using current real-time traffic data, historical traffic data, forecasted traffic data, posted speed limit data, or combinations thereof.

13. The apparatus of claim 9, wherein the alternative route is calculated using a decreased order of time search algorithm.

14. The apparatus of claim 9, wherein the at least one non-transitory memory and the computer program code are configured to cause the apparatus to further perform:

ascertain an overall score for the alternative route based on the comparison data.

15. The apparatus of claim 9, wherein the at least one non-transitory memory and the computer program code are configured to cause the apparatus to further perform:

update a map database of potential travel paths using the comparison data.