Travel planning system

• US 6,295,521 B1
• Filed: 07/02/1998
• Issued: 09/25/2001
• Est. Priority Date: 07/02/1998
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: ITA Software, Inc. (Alphabet Inc.)
• Inventors: Wertheimer, Jeremy, DeMarcken, Carl G.
• Primary Examiner(s): Cosimano, Edward R.
• Application Number:
  US09/109,327
• Time in Patent Office: 1,181 Days
• Field of Search: 701/201, 701/202, 705/5, 705/6, 705/400, 707/10, 707/104, 709/217, 709/218, 709/219
• US Class Current: 705/6
• 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/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202
• CPC Class Codes: G06Q 30/0283 Price estimation or determination

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 server process that determines travel planning information in response to a travel request query;

a client process, to send the travel request query and that receives the travel planning information, said client process comprising;

a manipulation process that operates on the travel planning information, to extract, in response to a subsequent user command, travel options from the travel planning information sent from the server process.

2. The system of claim 1 wherein the server process and the client process execute on the same computer.

3. The system of claim 1 wherein said manipulation process of said client process operates on the travel planning information in accordance with at least one user command, and further comprises

a process that produces a set of travel planning information by fare in accordance with the at least one user command.

4. The system of claim 3 wherein said process client further comprises:

a process that sorts said travel planning information by lowest price based on the user input command.

5. The system of claim 1 wherein said manipulation process further comprises:

a process that finds for the set of pricing solutions a pricing solution that optimizes a value function.

6. The system of claim 5 wherein said process that finds a pricing solution, finds for a travel option a best travel option involving an itinerary.

7. The system of claim 1 wherein the manipulation process further comprises:

an enumerating process that uses the set of pricing solutions to produce a subset of the set of pricing solutions in accordance with a user specified preference.

8. The system of claim 7 wherein said enumeration process further comprises:

a process that prunes from the set of pricing solutions, a set of pricing solutions that do not correspond to a user preference.

9. The system of claim 1 further comprising:

a server computer for executing said server process; and

a client computer for executing said client process.

10. The system of claim 9 further comprising a network and wherein said server computer and client computer are interconnected by the network.

11. An airline travel planning system, comprising:

a scheduler that produces a set of itineraries in response to a user specified query;

a faring system that provides fares for the sets of itineraries, and represents the sets of itineraries and fares as a set of logically manipulatable nodes in a data structure where such nodes are shared across itineraries;

an enumeration process that processes the data structure to extract flight-fare components from nodes in the data structure.

12. The system of claim 11 wherein said enumeration process further comprises:

a process that sorts the set of pricing solutions by price in accordance with at least one user preference.

13. The system of claim 11 wherein said process further comprises:

a process that sorts said set of pricing solutions by lowest price.

14. The system of claim 11 wherein the enumeration process further comprises:

a node invalidation process that invalidates nodes in the data structure to produce a subset of valid fares linked to sets of itineraries in accordance with a user specified preference.

15. The system of claim 11 wherein said enumeration process further comprises:

a process that finds for the set of pricing solutions a pricing solution that optimizes a value function.

16. The system of claim 15 wherein said process finds for a travel option a best travel option involving an itinerary.

17. A travel planning system comprising:

a server process that in response to at least one travel destination and at least one travel origin determines a set of pricing solutions, said set of pricing solutions represented by a structure that contains a first plurality of logically combinable entries that represent a second, larger number of pricing solutions;

a client process that receives said pricing solution structure, said client process further comprising;

an enumeration process that extracts pricing solutions from the structure.

18. The system of claim 17 wherein client process comprises:

a query process that causes the enumeration process to extract pricing solutions from the pricing solution structure.

19. The system of claim 17 wherein said pricing solution structure has a number of logical entries which when logically combined can provide a plurality of pricing solutions, with the number of set of pricing solutions being larger than the number of logical entries in the pricing solution structure.

20. The system of claim 17 wherein said client process further comprises:

a process that produces a sorted set of set of pricing solutions by fare in accordance with at least one user preference.

21. The system of claim 17 wherein said client process further comprises:

a process that finds for the set of pricing solutions a pricing solution that optimizes a value function.

22. The system of claim 17 wherein the client process further comprises:

a process that enumerates the set of pricing solutions in accordance with a user preference.

23. The system of claim 17 wherein said process further comprises:

a process that produces a sorted set of said set of pricing solutions by lowest price.

24. The system of claim 23 wherein said process finds for a travel option a best travel option involving an itinerary.

25. The system of claim 24 wherein said enumeration process further comprises:

a process that invalidates logical entries in the pricing solution structure.

26. A travel planning system comprising:

a server process that in response to at least one travel destination and at least one travel origin determines and represents a set of pricing solutions by a directed acyclic graph data structure;

a client process that receives said directed acyclic graph, said client process further comprising;

a process that uses the directed acyclic graph representation to enumerate in response to user preferences a set of pricing solutions.

27. The system of claim 26 wherein said client process further comprises:

a process that produces a sorted set of pricing solutions by price in accordance with at least one user preference.

28. The system of claim 27 wherein said process that produced the sorted set further comprises:

a process that produces the sorted set of said pricing solutions by lowest price.

29. The system of claim 26 wherein said client process further comprises:

an extraction process that extracts set of pricing solutions from the pricing solution structure.

30. The system of claim 29 wherein said client process further comprises:

an invalidate process that invalidates nodes in the directed acyclic graph which are involved only in set of pricing solutions that are outside of a subset of set of pricing solutions.

31. The system of claim 29 wherein said client process further comprises:

a process that finds for the set of pricing solutions a pricing solution that optimizes a value function.

32. The system of claim 31 wherein said process that finds a pricing solution, finds for a travel option a best travel option involving an itinerary.

33. An airline travel planning system comprising:

a server computer;

a server process executed on said server computer, said server process comprising a search process to search for set of pricing solutions in accordance with at least one destination and at least one origin, said search process representing said set of pricing solutions in the form of a directed acyclic graph;

a client computer;

a client computer process responsive to the set of pricing solutions represented in the form of the directed acyclic graph;

said client process further comprising;

a manipulation process that manipulates the set of pricing solutions in the form of the directed acyclic graph representation in response to user preferences, said manipulation process comprising;

a process, responsive to user preferences and to set of pricing solutions represented in the directed acyclic graph, to find a set of pricing solutions in accordance with said user preference;

a process that finds the set of pricing solutions and to produce a subset of said set of pricing solutions in accordance with user specified preferences; and

a sorting process that prunes from the directed acyclic graph nodes that are no longer contained within the subset of set of pricing solutions.