Robustness and notifications in travel planning system

• US 7,085,726 B1
• Filed: 11/01/2000
• Issued: 08/01/2006
• Est. Priority Date: 11/01/2000
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: ITA Software, Inc. (Alphabet Inc.)
• Inventors: Galperin, Gregory R., DeMarcken, Carl G.
• Primary Examiner(s): Nguyen, Dean T.
• Application Number:
  US09/704,268
• Time in Patent Office: 2,099 Days
• Field of Search: 705/1, 705/5, 705/6, 705/7, 705/8, 705/10
• US Class Current: 705/5
• CPC Class Codes: G06Q 10/02 Reservations, e.g. for tickets, services or events
• CPC Class Codes: G06Q 10/025 Coordination of plural reservations, e.g. plural trip segments, transportation combined with accommodation
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06Q 50/14 Travel agencies

Abstract

A method includes determining a travel itinerary that includes a first segment that is scheduled to arrive at a location at an arrival time and a second segment that is scheduled to depart from the location at a departure time. The method also includes deriving a probability distribution of delays in the arrival time based on an arrival statistical model of the first segment, retrieving a minimum connection time required by a traveler traveling in the first segment to connect to the second segment, and computing a likelihood that the traveler will fail to connect to the second segment based on the probability distribution of delays in the arrival time. Annotations are derived from the computed likelihood and added to the travel itinerary.

Claims

1. A method executed in a computer system, the method comprising:

determining a travel itinerary that includes a first segment that is scheduled to arrive at a first location at a first arrival time and a second segment that is scheduled to depart from the first location at a first departure time;

computing a likelihood that a traveler will fail to connect to the second segment based on a probability distribution of delays in the first arrival time;

deriving second segment annotations from the computed likelihood;

adding the second segment annotations to the travel itinerary; and

rendering the travel itinerary and the segment annotations on an output device.

2. The method of claim 1 wherein computing the likelihood that the traveler will fail to connect to the second segment is further based on the probability distribution of delays in the first departure time.

3. The method of claim 2 further comprising:

determining the probability distribution of delays in the departure time based on a departure statistical model of the second segment.

4. The method of claim 3 further comprising:

building the departure statistical model of the second segment based on past delays in departure times associated with the second segment.

5. The method of claim 2 further comprising:

retrieving a minimum connection time required by a traveler traveling in the first segment to connect to the second segment; and

computing a likelihood that the traveler will fail to connect to the second segment based on the minimum connection time.

6. The method of claim 5 wherein the likelihood that the traveler will fail to connect to the second segment is given by:

7. The method of claim 1 further comprising:

deriving the probability distribution of delays in the first arrival time based on an arrival statistical model of the first segment.

8. The method of claim 1 further comprising:

determining whether the likelihood that the traveler will fail to connect to the second segment is greater than a threshold value;

if the likelihood is greater than the threshold value, determining an alternate segment that the traveler may connect to if the traveler fails to connect to the second segment;

adding the alternate segment to the itinerary; and

rendering the alternate segment on an output device.

9. The method of claim 8 further comprising:

computing the likelihood that the traveler will fail to connect to the alternate segment;

deriving alternate segment annotations from the computed likelihood that the traveler will fail to connect to the alternate segment; and

adding the alternate segment annotations to the travel itinerary.

10. The method of claim 9 further comprising:

computing the combined likelihood that the traveler will fail to connect to both the second segment and the first segment;

deriving combined annotations from the combined likelihood; and

adding the combined annotations to the travel itinerary.

11. The method of claim 7 further comprising:

building the arrival statistical model of the first segment based on past delays in arrival times associated with the first segment.

12. The method of claim 1 further comprising:

retrieving a minimum connection time required by a traveler traveling in the first segment to connect to the second segment; and

computing the likelihood that the traveler will fail to connect to the second segment based on the minimum connection time.

13. The method of claim 12 wherein computing the likelihood that the traveler will fail to connect to the second segment includes:

calculating the difference between the first departure time and the sum of the first arrival time and the minimum connection time; and

determining the probability that the delay in the first arrival time is greater than the calculated difference.

14. The method of claim 12 wherein the likelihood that the traveler will fail to connect to the second segment is given by:

15. The method of claim 1 wherein the second segment is scheduled to arrive at a second location at a second arrival time and the travel itinerary further includes a third segment that is scheduled to depart from the second location at a second departure time;

the method further comprising;

computing a likelihood that the traveler will fail to connect to the third segment based on a probability distribution of the delays in the second arrival time;

computing a composite likelihood that the traveler will not fail to connect to either the second segment or the third segment based on the computed likelihood that the traveler will fail to connect to either the second or the third segments;

deriving composite annotations based on the composite likelihood; and

adding the composite annotations to the itinerary.

16. An article comprising a machine-readable medium which stores machine-executable instructions operable to cause a machine to:

determine a travel itinerary that includes a first segment that is scheduled to arrive at a first location at a first arrival time and a second segment that is scheduled to depart from the first location at a first departure time;

compute a likelihood that a traveler will fail to connect to the second segment based on a probability distribution of delays in the first arrival time;

derive second segment annotations from the computed likelihood; and

add the second segment annotations to the travel itinerary.

17. The article of claim 16 wherein computing the likelihood that the traveler will fail to connect to the second segment is further based on the probability distribution of delays in the first departure time.

18. The article of claim 16 wherein the instructions further cause the machine to:

derive the probability distribution of delays in the first arrival time based on an arrival statistical model of the first segment.

19. The article of claim 18 wherein the instructions further cause the machine to:

build a arrival statistical model of the first segment based on past delays in arrival times associated with the first segment.

20. The article of claim 17 wherein the instructions further cause the machine to:

determine the probability distribution of delays in the departure time based on a departure statistical model of the second segment.

21. The article of claim 20 wherein the instructions further cause the machine to:

build a departure statistical model of the second segment based on past delays in departure times associated with the second segment.

22. The article of claim 17 wherein the instructions further cause the machine to:

retrieve a minimum connection time required by a traveler traveling in the first segment to connect to the second segment;

wherein computing a likelihood that the traveler will fail to connect to the second segment based on the minimum connection time.

23. The article of claim 22 wherein instructions to calculate the likelihood that the traveler will fail to connect to the second segment are given by:

24. The article of claim 16 wherein the instructions further cause the machine to:

determine whether the likelihood that the traveler will fail to connect to the second segment is greater than a threshold value; and

if the likelihood is greater than the threshold value,

determine an alternate segment that the traveler may connect to if the traveler fails to connect to the second segment; and

add the alternate segment to the itinerary.

25. The article of claim 24 wherein the instructions further cause the machine to:

compute the likelihood that the traveler will fail to connect to the alternate segment; and

derive alternate segment annotations from the computed likelihood that the traveler will fail to connect to the alternate segment; and

add the alternate segment annotations to the travel itinerary.

26. The article of claim 25 wherein the instructions further cause the machine to:

compute the combined likelihood that the traveler will fail to connect to both the second segment and the first segment; and

derive combined annotations from the combined likelihood; and

add the combined annotations to the travel itinerary.

27. The article of claim 16 wherein the instructions further cause the machine to:

retrieve a minimum connection time required by a traveler traveling in the first segment to connect to the second segment; and

compute a likelihood that the traveler will fail to connect to the second segment based on the minimum connection time.

28. The article of claim 27 wherein instructions to compute the likelihood that the traveler will fail to connect to the second segment further includes instructions to:

calculate the difference between the first departure time and the sum of the first arrival time and the minimum connection time; and

determine the probability that the delay in the first arrival time is greater than the calculated difference.

29. The article of claim 27 wherein instructions to calculate the likelihood that the traveler will fail to connect to the second segment are given by:

30. The article of claim 16 wherein the second segment is scheduled to arrive at a second location at a second arrival time and the travel itinerary further includes third segment that is scheduled to depart from the second location at a second departure time, wherein the instructions further cause the machine to:

compute a likelihood that the traveler will fail to connect to the third segment based on a probability distribution of the delays in the second arrival time;

compute a composite likelihood that the traveler will not fail to connect to either the second segment or the third segment based on the computed likelihood that the traveler will fail to connect to either the second or the third segments;

derive composite annotations based on the composite likelihood; and

add the composite annotations to the itinerary.