System and method for real time optimization of driving directions

• US 9,212,920 B1
• Filed: 01/13/2010
• Issued: 12/15/2015
• Est. Priority Date: 01/13/2010
• Status: Expired due to Fees

• Current Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Original Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Inventors: Mannepalli, Rao Y., Uzdzinski, Joseph E.
• Primary Examiner(s): Mawari, Redhwan K
• Assistant Examiner(s): Torchinsky, Edward
• Application Number:
  US12/686,838
• Time in Patent Office: 2,162 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• 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/3691 Retrieval, searching and output of information related to real-time traffic, weather, or environmental conditions arrangements for giving variable traffic instructions G08G1/09
• CPC Class Codes: G08G 1/09685 where the complete route is computed only once and not updated
• CPC Class Codes: G08G 1/096866 where the complete route is shown to the driver
• CPC Class Codes: G08G 1/0969 having a display in the form of a map

Abstract

A system and method for generating driving directions is disclosed. The system and method comprise generating a series of instructions to guide a driver along a route that includes a sequence of roads and intersections. The system uses real time or near real time information culled from one or more databases to calculate and display a time-efficient route based on current weather conditions, traffic conditions, road closures, construction, and the like. The system can also incorporate one or more driver preferences in calculating the displayed route. The system also can provide a summary of the rationales used in calculating the displayed route so the user can understand the basis for a particular route'"'"'s presentation. A method is also disclosed for using the system.

Claims

1. A method for providing driving directions for a trip, comprising:

obtaining a start point for a trip;

obtaining an end point for the trip;

obtaining a start time and a start date for the trip;

obtaining traffic volume information and updating a database with the traffic volume information;

obtaining delay information representing potential causes of delay;

correlating the delay information with preselected statistical limits to determine whether the delay information should be used to update the database;

responsive to a positive determination, updating the database with the delay information;

constructing a graph of a plurality of potential routes linking the start point to the end point, wherein the graph comprises a plurality of nodes and a plurality of links connecting the nodes;

assigning a weight to each of said plurality of links based on the stored traffic volume information and the potential causes of delay;

applying a shortest path algorithm to obtain a proposed route of shortest duration from said plurality of potential routes, wherein the proposed route includes selected segments and wherein at least one of the selected segments includes a note relating to a predicted delay identified on an unselected alternative segment to the at least one selected segment, based on one or both of the stored traffic volume information and the stored potential causes of delay;

reviewing the selected segments of the proposed route and generating a text explanation for each of the selected segments that includes the note relating to the predicted delay identified on the unselected alternative segment to the selected segment;

displaying to the user on the display a map of the proposed route; and

displaying to the user, on the display of the map of the proposed route, for each of the selected segments having the note, the text explanation relating to the note, thereby providing the user a rationale for not selecting the unselected alternative segment instead of the selected segment.

2. The method of claim 1, wherein the step of obtaining the delay information representing potential causes of delay further comprises obtaining construction delay information.

3. The method of claim 1, where the step of obtaining the delay information representing potential causes of delay comprises using Chauvenet'"'"'s criterion to eliminate statistically significant data samples.

4. The method of claim 1, where the step of obtaining the delay information representing potential causes of delay comprises using Peirce'"'"'s criterion to eliminate statistically significant data samples.

5. The method of claim 1, wherein the step of assigning a weight to each of said plurality of links comprises assigning a weight dependent upon a time of day.

6. The method of claim 5, wherein a first link of said plurality of links is assigned a first weight associated with the start time of the trip, and a second link of said plurality of links is assigned a second weight associated with a time of the trip that is later than said start time.

7. The method of claim 6, wherein said second weight is associated with a date of the trip that is later than said start date.

8. The method of claim 1, wherein the display is a display on a device outside of the vehicle, and further comprising:

displaying to the user on the display an election of whether to display reasoning corresponding to the proposed route; and

wherein displaying to the user the text explanation relating to the note is responsive to receiving an affirmative election to display the reasoning corresponding to the proposed route.

9. The method of claim 1, wherein correlating the delay information with the preselected statistical limits to determine whether the delay information should be used to update the database comprises:

determining whether the potential causes of delay corresponding to the delay information are within the preselected statistical limits;

responsive to a determination that the potential causes of delay corresponding to the delay information are within the preselected statistical limits, updating the database with the delay information including updating driving times corresponding to the delay information;

responsive to a determination that the potential causes of delay corresponding to the delay information are not within the preselected statistical limits;

performing a root cause analysis; and

updating the database with the delay information based on the root cause analysis.

10. A system for providing driving directions for a trip, comprising a processing unit connected to and in communication with a database and a display, and a machine-readable storage medium encoded with a computer program code such that, when the computer program code is executed by a processor, the processor performs a method comprising:

obtaining a start point for a trip;

obtaining an end point for the trip;

obtaining a start time and a start date for the trip;

obtaining traffic volume information and updating a database with the traffic volume information;

obtaining delay information representing potential causes of delay;

correlating the delay information with preselected statistical limits to determine whether the delay information should be used to update the database;

responsive to a positive determination, updating the database with the delay information;

constructing a graph of a plurality of potential routes linking the start point to the end point, wherein the graph comprises a plurality of nodes and a plurality of links connecting the nodes;

assigning a weight to each of said plurality of links based on the stored traffic volume information and the potential causes of delay;

applying a shortest path algorithm to obtain a proposed route of shortest duration from said plurality of potential routes, wherein the proposed route includes selected segments and wherein at least one of the selected segments includes a note relating to a predicted delay identified, on an unselected alternative segment to the at least one selected segment, based on one or both of the stored traffic volume information and the stored potential causes of delay;

reviewing the selected segments of the proposed route and generating a text explanation for each of the selected segments that includes the note relating to the predicted delay identified on the unselected alternative segment to the selected segment;

displaying to the user on the display a map of the proposed route; and

displaying to the user, on the display of the map of the proposed route, for each of the selected segments having the note, the text explanation relating to the note, thereby providing the user a rationale for not selecting the unselected alternative segment instead of the selected segment.

11. The system of claim 10, wherein the step of obtaining the delay information representing potential causes of delay further comprises obtaining and storing construction delay information.

12. The system of claim 10, where the step of obtaining the delay information representing potential causes of delay comprises using Chauvenet'"'"'s criterion to eliminate statistically significant data samples.

13. The system of claim 10, where the step of obtaining the delay information representing potential causes of delay comprises using Peirce'"'"'s criterion to eliminate statistically significant data samples.

14. The system of claim 10, wherein the step of assigning a weight to each of said plurality of links comprises assigning a weight dependent upon a time of day.

15. The system of claim 14, wherein a first link of said plurality of links is assigned a first weight associated with the start time of the trip, and a second link of said plurality of links is assigned a second weight associated with a time of the trip that is later than said start time.

16. The system of claim 15, wherein said second weight is associated with a date of the trip that is later than said start date.

17. The system of claim 10, wherein the display is a display on a device outside of the vehicle, wherein the machine-readable storage medium encoded with the computer program code further includes computer program code which, when executed by a processor, causes the processor to perform the steps of:

displaying to the user on the display an election of whether to display reasoning corresponding to the proposed route; and

wherein displaying to the user the text explanation relating to the note is responsive to receiving an affirmative election to display the reasoning corresponding to the proposed route.

18. The system of claim 10, wherein correlating the delay information with the preselected statistical limits to determine whether the delay information should be used to update the database comprises:

determining whether the potential causes of delay corresponding to the delay information are within the preselected statistical limits;

responsive to a determination that the potential causes of delay corresponding to the delay information are within the preselected statistical limits, updating the database with the delay information including updating driving times corresponding to the delay information;

responsive to a determination that the potential causes of delay corresponding to the delay information are not within the preselected statistical limits;

performing a root cause analysis; and

updating the database with the delay information based on the root cause analysis.