Method, system, and computer-readable medium for generating a diverse set of travel options

• US 7,340,403 B1
• Filed: 11/01/1999
• Issued: 03/04/2008
• Est. Priority Date: 11/01/1999
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: ITA Software, Inc. (Alphabet Inc.)
• Inventors: DeMarcken, Carl G.
• Primary Examiner(s): Smith; Jeffrey A.
• Assistant Examiner(s): RINES, ROBERT D
• Application Number:
  US09/431,699
• Time in Patent Office: 3,046 Days
• Field of Search: 705/5, 705/6, 707/2
• 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: Y10S 707/99932 Access augmentation or optimizing

Abstract

A method for generating a diverse list of N travel options Rts from a larger list of travel options Ts, is described. The method includes generating a prioritized ordered list of requirements Rs and sorting the list of travel options Ts by an ordering function F to produce a best-first ordered list Ts2 with the list of options being optimized travel options for a set of travel requirements R in accordance with the ordering function F.

Claims

1. A method for providing a set of diverse travel options, the method comprising:

reducing a larger set of travel options to a smaller set of diverse travel options in accordance with diverse travel requirements that represent conditions for a travel option to be considered for inclusion in the set of diverse travel options that includes at least first and second travel options that satisfy first and second travel requirements, with the first and second travel requirements representing different values in a category of travel requirements, and the travel options including a flight and fare combination; and

wherein reducing a larger set of travel options to a smaller set of diverse travel options further comprises;

evaluating for the travel requirements a set of travel preference functions used to order the larger set of travel options.

2. The method of claim 1 wherein reducing a larger set of travel options to a smaller set of diverse travel options comprises:

generating one or more travel options consistent for each of the diversity of travel requirements.

3. The method of claim 1 wherein reducing a larger set of travel options to a smaller set of diverse travel options comprises:

generating one or more desired travel options consistent with diversity of travel requirements.

4. The method of claim 1 wherein reducing a larger set of travel options to a smaller set of diverse travel options further comprises:

generating one or more of the best travel options consistent with a diversity of travel requirements where the travel requirements are dependent on the original set of travel options.

5. The method of claim 1 wherein the set of travel requirements includes requirements for different airlines.

6. The method of claim 1 wherein the set of travel requirements includes requirements for travel times of day, travel dates, numbers of stops, arrival pr departure airports, and cabin class.

7. The method of claim 1 wherein the set of travel requirements includes requirements that are combinations of other requirements.

8. The method of claim 7 wherein the set of travel requirement combinations include outbound and return travel dates or times of day.

9. The method of claim 7 wherein the set of travel requirements combinations include airlines and number of stops, arrival and departure airports.

10. The method of claim 7 wherein the set of travel requirements combinations include airlines and number of stops, arrival and departure airports.

11. The method of claim 1 wherein the method reduces a larger set of travel options to a smaller set of diverse travel options in accordance with travel requirements in the ordered list of travel requirements.

12. The method of claim 1 wherein the travel requirements represent conditions for a travel option to be considered for inclusion in the diverse list of travel options Rts.

13. The method of claim 1 wherein the set of travel requirements includes requirements for different airlines.

14. The method of claim 1 wherein the set of travel requirements includes requirements for travel times of day, travel dates, numbers of stops, arrival pr departure airports, and cabin class.

15. The method of claim 1 wherein the set of travel requirements includes requirements that are combinations of other requirements.

16. The method of claim 15 wherein the set of travel requirement combinations include outbound and return travel dates or times of day.

17. A computer implemented method for generating a diverse list of travel options Rts from a larger list of travel options Ts, the method comprises:

generating a prioritized ordered list of requirements Rs;

sorting the list of travel options Ts by an ordering function F to produce a best-first ordered list Ts2;

selecting a travel requirement R1 from the list of requirements Rs;

identifying a travel option T1 in the ordered list Ts2 that satisfies the travel requirement R1 that represents a value in a category of travel requirements;

adding the travel option T1 to the diverse list of travel options Rts;

selecting a second travel requirement R2 from the list of requirements Rs;

identifying a travel option T2 in the ordered list Ts2 that satisfies travel requirement R2 that represents a different value in the category of the first travel requirement R1; and

adding the travel option T2 to the diverse list of travel options Rts.

18. The method of claim 17 further comprising:

initializing the list of result travel options Rts to be empty; and

if the remaining list of requirements Rs is empty, returning an ordered list of diverse travel options Rts.

19. The method of claim 18 further comprising:

initializing the list of result travel options Rts to be empty; and

if the remaining list of requirements Rs is not empty,

selecting a first travel requirement R from the ordered list of requirements (Rs); and

removing a requirement R from the requirement list (Rs).

20. The method of claim 19 further comprising:

determining for each travel requirement R2 and Rs, whether the requirement R2 includes a requirement R, and T satisfies R2, and if T satisfies R2;

removing R2 from Rs.

21. The method of claim 19 further comprising:

finding a first option T in a best-first ordered list (Ts2) that satisfies travel requirements R.

22. The method of claim 21 further comprising:

determining whether any option in the Ts2 satisfies the travel requirement.

23. The method of claim 22 wherein if no option in Ts2 satisfies R, the method further comprises:

checking if the remaining list of requirements Rs is empty.

24. The method of claim 23 wherein if the diversity process determines if a travel option T is not already in the result list Rts,

adding the travel option T to end of the result travel option list Rts;

and

determining if the size of the travel option list Rts is equal to or greater than N the process in order to return the ordered list of diverse travel options.

25. A travel planning system comprising:

a computer system;

including;

a computer readable medium storing a computer program product comprising instructions to cause the computer system to;

output a set of travel options, smaller than a complete set of travel options that the computer has computed, by instructions to;

prune the complete set of travel options to a smaller set with a diversity-based pruning process, the diversity-based pruning process produces at least one travel option in the smaller set that satisfies a first travel requirement and at least one other travel option in the smaller set that satisfies a second travel requirement, with the first and second travel requirements representing different values in a category of travel requirements with the values for the travel requirement based on the set of travel options.

26. The travel planning system of claim 25 wherein the diversity-based pruning process comprises instructions to cause the system to:

generate a diverse list of N travel options Rts from a larger list of travel options Ts,

generate a prioritized ordered list of requirements Rs; and

sort the list of travel options Ts by an ordering function F to produce a best-first ordered list Ts2 with the list of options being optimized travel options for a set of travel requirements R in accordance with the ordering function F.

27. The travel planning system of claim 26 further comprising instructions to cause the system to:

initialize the list of result travel options Rts to be empty; and

if the remaining list of requirements Rs is empty,

return an ordered list of diverse travel options Rts.

28. The travel planning system of claim 27 further comprising instructions to cause the system to:

initialize the list of result travel options Rts to be empty; and

if the remaining list of requirements Rs is not empty, select a first travel requirement R from the ordered list of requirements (Rs); and

remove a requirement R from the requirement list (Rs).

29. A computer program product residing on a computer readable medium for generating a diverse list of travel options Rts from a larger list of travel options Ts, the computer program product comprises instructions for causing a computer to:

generate a prioritized ordered list of requirements Rs;

sort the list of travel options Ts by an ordering function F to produce a best-first ordered list Ts2;

select a travel requirement R1 from the list of requirements Rs;

identify a travel option T1 in the ordered list Ts2 that satisfies the travel requirement R1 that represents a value in a category of travel requirements;

add the travel option T1 to the diverse list of travel options Rts;

select a second travel requirement R2 from the list of requirements Rs;

identify a travel option T2 in the ordered list Ts2 that satisfies travel requirement R2 that represents a different value in the category of the first travel requirement R1; and

add the travel option T2 to the diverse list of travel options Rts.

30. The computer program product of claim 29 further comprising instructions to:

initialize the list of result travel options Rts to be empty; and

if the remaining list of requirements Rs is empty, returning an ordered list of diverse travel options Rts.

31. The computer program product of claim 29 further comprising instructions to:

initialize the list of result travel options Rts to be empty; and

if the remaining list of requirements Rs is not empty, select a first travel requirement R from the ordered list of requirements (Rs); and

removing a requirement R from the requirement list (Rs).

32. The computer program product of claim 31 further comprising instructions to:

find a first option T in a best-first ordered list (Ts2) that satisfies travel requirements R.

33. The computer program product of claim 31 further comprising instructions to:

determine whether any option in the Ts2 list satisfies the travel requirement.

34. The computer program product of claim 33 wherein if no option in Ts2 satisfies R, the instructions further comprise instructions to:

check if the remaining list of requirements Rs is empty.

35. The computer program product of claim 33 wherein if the instructions determine that a travel option T is not already in the result list Rts, add the travel option T to end of the result travel option list Rts;

and determine if the size of the travel option list Rts is equal to or greater than N the process in order to return the ordered list of diverse travel options.

36. The computer program product of claim 33 further comprising instructions to:

determine for each travel requirement R2 and Rs, whether the requirement R2 includes a requirement R, and T satisfies R2, and if T satisfies R2;

remove R2 from Rs.

37. An article of manufacture having computer-readable program portions embodied therein for generating a diverse set of travel options, the article comprising instructions for causing a processor to:

generate a first ordered set of travel options using a first preference function;

select travel options from the first set, the selected travel options corresponding to a plurality of diverse travel requirements;

generate a second ordered set of travel options using a second preference function, the second preference function being different from the first preference function;

select travel options from the second set, the selected travel options corresponding to a plurality of diverse travel requirements; and

combine the selected travel options to generate the diverse set of travel options.

38. The article of claim 37 further comprising instructions for causing a processor to generate a plurality of travel requirements,

wherein the computer-readable program portion for selecting a predefined number of best travel options from the first set further comprises for each travel requirement, selecting one or more travel options from the first set that satisfy that travel requirement, and

wherein the computer-readable program portion for selecting a predefined number of best travel options from the second set further comprises for each travel requirement, selecting one or more travel options from the second set that satisfy that travel requirement.

39. The article of claim 37 wherein values for a particular travel requirement are based on the candidate set of travel options.

40. The article of claim 37 wherein the plurality of travel requirement include particular carriers, number of stops, outbound travel departing in a predefined time period, return travel departing in a predefined time period, or travel with an outbound departure on a first predefined date and a return arrival on a second predefined date.

41. The article of claim 37 wherein values for the travel requirement of particular carriers with corresponding travel requirements include a first particular airline and a second, different particular airline.

42. An article of manufacture having computer-readable program portions embodied therein for generating a diverse set of travel options, the article comprising instructions for causing a processor to:

determine a candidate set of travel options, the candidate set of travel options being based on user input;

define a set of diversity requirements with instructions to define comprising instructions to;

establish a plurality of travel requirement templates, for each travel requirement template, define a plurality of travel requirements, each of the travel requirements corresponding to a different value of the respective travel requirement template to produce the set of diversity requirements, and for each travel requirement in the set of diversity requirements,

select from the candidate set of travel options a travel option that satisfies that travel requirement with values for a particular travel requirement template based on the candidate set of travel options;

combine the selected travel options for the travel requirements to generate the diverse set of travel options; and

display the diverse set of travel options to a user.

43. The article of claim 42 wherein values for a particular travel requirement template are based on the candidate set of travel options.

44. The article of claim 42 wherein the plurality of travel requirement templates include particular carriers, number of stops, outbound travel departing in a predefined time period, return travel departing in a predefined time period, or travel with an outbound departure on a first predefined date and a return arrival on a second predefined date.

45. The article of claim 44 wherein values for the travel requirement template of particular carriers with corresponding travel requirements include a first particular airline and a second, different particular airline.