Method for Generating A Diverse Set of Travel Options

• US 20080154630A1
• Filed: 03/04/2008
• Published: 06/26/2008
• Est. Priority Date: 11/01/1999
• Status: Abandoned Application

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: ITA Software, Inc. (Alphabet Inc.)
• Inventors: DeMarcken, Carl G.
• Application Number:
  US12/041,775
• Publication Number:
  US 20080154630A1
• Time in Patent Office: Days
• US Class Current: 705/1
• CPC Class Codes: G06Q 10/02 Reservations, e.g. for tickets, services or events

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 computer-implemented method for providing a set of travel options comprises:

reducing a larger set of travel options that comprise flights and fares usable with the flights to a smaller set of diverse travel options that satisfy diverse travel requirements.

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

generating travel options for the smaller set of diverse travel options that are consistent for each of the 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 for the smaller set of diverse travel options that are consistent with the 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 for the smaller set of diverse travel options that are consistent with the 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 or 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 requirement combinations include airlines and number of stops, arrival and departure airports.

10. A method for reducing a larger set of travel options to a smaller set of diverse travel options comprises:

generating one or more travel options that are best for each of a set of travel preference functions, with the travel preference functions, being functions that order, according to a criterion defined by the preference function, the travel options; and

selecting travel options that comprise flights and fares usable with the flights to provide a set of diverse travel options that satisfy diverse travel requirements and are selected according to the ordering provided by the travel preference functions.

11. The method of claim 10 wherein the travel preference functions include functions that optimize cost or functions that optimize convenience.

12. The method of claim 10 wherein the travel preference functions include both functions that optimize cost and functions that optimize convenience and functions that optimize combinations of cost and convenience.

13. A method generating a diverse list of N travel options Rts from a larger list of travel options Ts, 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 with the list of options being optimized travel options for a set of travel requirements R in accordance with the ordering function F.

14. The method of claim 13 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.

15. The method of claim 14 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).

16. The method of claim 15 further comprising:

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

17. The method of claim 16 further comprising:

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

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

checking if the remaining list of requirements Rs is empty.

19. The method of claim 18 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.

20. The method of claim 15 further comprising:

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

removing R2 from Rs.

21. A travel planning system, comprising:

a processor; and

a computer readable medium that stores a computer program product comprising instructions that causes the system to;

determine a set of travel options, of flights and fares usable with the flights, that is smaller than a larger set of travel options that the system has computed, by reducing the larger set of travel options to a smaller set of diverse travel options that satisfy diverse travel requirements.

22. The travel planning system of claim 21 wherein instructions to determine 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;

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.

23. The travel planning system of claim 23 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.

24. The travel planning system of claim 24 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).