Generating a diverse set of travel options

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

• 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): Porter; Rachel L.
• Application Number:
  US09/431,365
• Time in Patent Office: 3,046 Days
• Field of Search: 705/5, 705/6
• US Class Current: 705/5
• CPC Class Codes: G06F 16/34 Browsing; Visualisation therefor
• CPC Class Codes: G06Q 10/02 Reservations, e.g. for tickets, services or events
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

An airline travel planning system is described. The system includes a server computer executing a server process including a search process to search for set of pricing solutions in accordance with at least one destination and at least one origin. The search process represents the set of pricing solutions in the form of a directed acyclic graph. The system also includes a client computer executing a client process on the set of pricing solutions. The client process has a manipulation process that manipulates the set of pricing solutions in response to user preferences. Several processes are described including a process responsive to user preferences and to set of pricing solutions that provides pricing solutions sorted by said user preference, a process that sorts set of pricing solutions to produce a subset of said set of pricing solutions in accordance with user specified preferences, and a process that prunes from the directed acyclic graph nodes that are no longer contained within the subset of set of pricing solutions.

Claims

1. A travel planning system comprising:

a requirements generator module to generate a set of diverse travel requirements, by establishing a plurality of travel requirements templates, and for each travel requirement template, defining a plurality of travel requirements corresponding to different values of the travel requirements with values for a particular travel requirements template based on a candidate set of travel options; and

a selection module to output a set of diverse travel options, the number of travel options in the set of diverse travel options being fewer in number than the number of travel options in the candidate set of travel options and for each diverse travel requirements in the set of diverse travel requirements, selecting from the candidate set of travel options one or more travel options that satisfy that travel requirements with the candidate set of travel options represented using a data structure that compactly stores the candidate set of travel options.

2. The travel planning system of claim 1 wherein the data structure comprises a graph data structure.

3. The travel planning system of claim 1 further comprising a display to display the diverse set of travel options.

4. The travel planning system of claim 1 further comprising:

a travel option generator module to generate a first ordered set of travel options using a first preference function and a second ordered set of travel options using a second preference function, and

wherein the selection module outputs a set of diverse travel options by selecting a first and second number of travel options from each of the first and second ordered set of travel options, respectively.

5. The travel planning system of claim 1 wherein at least one of the diverse travel requirements within the plurality is not a user entered travel requirement.

6. The travel planning system of claim 1 wherein the plurality of diverse travel requirements comprise at least one of travel on a particular carrier, non-stop travel, outbound travel departing in a predefined time period, return travel departing in a predefined time period, non-stop travel on a predefined airline, or travel with an outbound departure on a first predefined date and a return arrival on a second predefined date.

7. The travel planning system of claim 6 wherein the predefined time period comprises morning, afternoon, evening or a predefined date.

8. The travel planning system of claim 1 wherein the compact data structure comprises a directed acyclic graph.

9. The travel planning system of claim 1 wherein the compact data structure comprises a grammar.

10. A method for generating a diverse set of travel options, the method comprising:

determining a candidate set of travel options, the candidate set of travel options being based on user input and represented a data structure that compactly stores the candidate set or travel options;

defining a set of diversity requirements, with defining comprising;

establishing a plurality of travel requirement templates, and for each travel requirement template, defining a plurality of travel requirements, each of the plurality of travel requirements corresponding to a different value of the respective travel requirements with values for a particular travel requirement template based on the candidate set of travel options, and

for each travel requirement in the set of diversity requirements, selecting from the candidate set of travel options a travel option that satisfies that travel requirement;

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

displaying the diverse set of travel options to a user.

11. The method of claim 10 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.

12. The method of claim 11 wherein values for the travel requirement template of particular carriers include a first particular airline and a second, different particular airline.

13. The method of claim 10, wherein the structure that compactly stores comprises a graph data structure.

14. The method of claim 10 wherein the structure that compactly stores comprises a directed acyclic graph.

15. The method of claim 10 wherein the structure that compactly stores comprises a grammar.

16. The method of claim 10 wherein selecting comprises:

generating a first ordered set of travel options using a first preference function and a second ordered set of travel options using a second preference function to operate on the structure that compactly stores the travel options, and combining the selected travel options further comprises

combining a first and second number of travel options from each of the first and second ordered set of travel options, respectively to generate the diverse travel options.

17. The method of claim 10 wherein the least one of the diverse travel requirements within the plurality is not a user entered travel requirement.

18. The method of claim 10 wherein the plurality of diverse travel requirements comprise at least one of travel on a particular carrier, non-stop travel, outbound travel departing in a predefined time period, return travel departing in a predefined time-period, non-stop travel on a predefined airline, or travel with an outbound departure on a first predefined date and a return arrival on a second predefined date.

19. 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 and represented using a data structure that compactly stores the candidate set of travel options;

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

establish a plurality of travel requirement templates, and for each travel requirement template,

define a plurality of travel requirements, each of the plurality of travel requirements corresponding to a different value of the respective travel requirements with values for a particular travel requirement template based on the candidate set of travel options, 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 requirements;

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.

20. The article of claim 19 wherein the plurality of travel requirement templates include templates for 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.

21. The article of claim 20 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.

22. The article of claim 20 wherein the predefined time periods comprise morning, afternoon, evening or a predefined date.

23. The article of claim 19 wherein the structure that compactly stores comprises a graph data structure.

24. The article of claim 19 wherein the structure that compactly stores comprises a directed acyclic graph.

25. The article of claim 19 wherein the structure that compactly stores comprises a grammar.

26. The article of claim 19 wherein instructions to select further comprise instructions to:

generate a first ordered of travel using a first preference function and a second ordered set of travel options using a second preference function to operate on the structure that compactly stores the travel options, and combining the selected travel options further comprises

combine a first and second number of travel options from each of the first and second ordered set of travel options, respectively to generate the diverse travel options.

27. The article of claim 19 wherein at least one of the diverse travel requirements within the plurality is not a user entered travel requirement.

28. The article of claim 19 wherein the plurality of diverse travel requirements comprise at least one of travel on a particular carrier, non-stop travel, outbound travel departing in a predefined time period, return travel departing in a predefined time period, non-stop travel on a predefined airline, or travel with an outbound departure on a first predefined date and a return arrival on a second predefined date.

29. The article of claim 19 wherein the predefined time period comprises morning, afternoon, evening or a predefined date.