Pricing graph representation for sets of pricing solutions for travel planning system

• US 6,609,098 B1
• Filed: 07/02/1998
• Issued: 08/19/2003
• 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: DeMarcken, Carl G.
• Primary Examiner(s): BANANKHAH, MAJID A
• Application Number:
  US09/109,328
• Time in Patent Office: 1,874 Days
• Field of Search: 709/100, 709/217, 709/218, 709/219, 705/6, 705/1, 705/5, 705/400, 707/10, 707/102, 701/201, 701/202
• 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 computer program product residing on a computer readable medium for determining a set of fares for a set of itineraries comprising instructions for causing a computer to:

retrieve itinerary sets for at least one slice of a journey;

parse retrieved itinerary sets into faring atoms that correspond to one or more travel unit segments spanned by a single fare, wherein faring atoms are shared across itineraries;

apply rules to the faring atoms to produce fare components;

construct from the fare components a set of fares that are valid for and associated with the itinerary sets.

2. The computer program of claim 1 wherein the instructions for causing the computer to construct a set of fares further comprises instructions for causing the computer to

construct priceable units from the fare components; and

link itineraries and priceable units into pricing solutions.

3. The computer program of claim 2 wherein the pricing solutions correspond to the set of valid fares and information linking the set of valid fares to segments of the journey.

4. The computer program product of claim 2 wherein the instructions for causing the computer to link itineraries and priceable units, links the itineraries and priceable units through a data structure that represents the set of pricing solutions.

5. The computer program product as recited in conjunction with claim 4 wherein the instructions that cause the computer to apply rules further comprises instructions for causing the computer to

defer applying a rule to a faring atom if the rule references information outside of the faring atom;

and

apply deferred rules when all fare components for evaluating the rule have been delivered to the fare.

6. The computer program product of claim 1 wherein parsing of itineraries into faring atoms further comprises instructions for causing the computer to:

group faring atoms by faring markets; and

partition itineraries into divisions of faring atoms.

7. The computer program product of claim 1 wherein the instructions for causing the computer to partition itineraries further comprises instructions for causing the computer to:

split sequences of legs of itineraries into individual faring atoms if the legs are on a same airline.

8. The computer program product of claim 1 wherein the pricing solutions are represented in a compact form.

9. The computer program product of claim 8 wherein the compact form is a graph type data structure.

10. A method for determining a set of fares for a set of itineraries comprises:

retrieving itinerary sets for at least one slice of a journey;

parsing retrieved itinerary sets into faring atoms that correspond to one or more travel unit segments spanned by a single fare;

applying rules to the faring atoms to produce fare components; and

constructing from the fare components a set of fares that are valid for and associated with the itinerary sets.

11. The method of claim 10 wherein determining a set of fares for a set of itineraries further comprises:

constructing priceable units from the fare components; and

linking itineraries and priceable units into a representation of a set of pricing solutions.

12. The method of claim 11 wherein the pricing solutions correspond to the set of valid fares and information linking the set of valid fares to segments of the itinerary.

13. The method of claim 11 wherein linking itineraries and priceable units links the itineraries and priceable units through a data structure that represents the pricing solutions.

14. The method of claim 13 wherein applying rules further comprises:

deferring applying a rule to a faring atom if the faring atom represents a fare outside of the faring components involving the faring atom; and

applying deferred rules to the faring atom once the faring components correspond to the fare.

15. The method of claim 10 wherein parsing of itineraries into faring atoms further comprises:

grouping faring atoms by faring markets; and

partitioning itineraries in divisions of faring atoms by slices of a journey.

16. The method of claim 10 wherein the instructions for causing the computer to partition itineraries further comprises:

splitting sequences of legs of itineraries into individual faring atoms if the legs are flights on a same airline.

17. A method for determining pricing solutions comprises:

retrieving itinerary sets for all slices of a journey;

decomposing said itinerary sets into faring atoms;

applying rules to said faring atoms to produce valid faring atoms that are grouped into faring components;

constructing priceable unit data structures from the faring components; and

linking itineraries and priceable units into a data structure that represents pricing solutions.

18. The method of claim 17 wherein the data structure that represents the pricing solutions is a graph type data structure.

19. The method of claim 18 wherein applying rules further comprises:

deferring application of rules to faring atoms if the faring atoms represent a fare outside of the faring components involving the faring atoms; and

applying deferred rules to the faring atoms once information from the fare is within the faring components.

20. The method of claim 19 wherein parsing of itineraries into faring atoms further comprises:

grouping faring atoms by faring markets; and

partitioning itineraries into divisions of faring atoms.

21. The method of claim 20 wherein partitioning itineraries further comprises:

splitting sequences of legs of itineraries into individual faring atoms if the legs are flights on a same airline.

22. A computer system for determining pricing solutions comprises:

a computer; and

a computer readable medium storing a computer program that causes the computer to;

retrieve itinerary sets for all slices of a journey;

decompose said itinerary sets into faring atoms;

apply rules to the faring atoms to produce valid faring atoms that are grouped into faring components;

construct priceable unit data structures from the faring components; and

link itineraries and priceable units into a data structure that represents pricing solutions.

23. The system of claim 22 wherein the data structure that represents the pricing solutions is a graph type data structure.

24. The system of claim 23 wherein the instructions that cause the computer to apply rules further comprise instructions that cause the computer to:

defer application of rules to faring atoms if the faring atoms represent a fare outside of the faring components involving the faring atoms; and

apply deferred rules to the faring atoms once information from the fare is within the faring components.

25. The system of claim 22 wherein instructions that cause the computer to parse the itineraries into faring atoms further comprises instructions that cause the computer to:

group faring atoms by faring markets; and

partition itineraries into divisions of faring atoms.

26. The method of claim 22 wherein partitioning itineraries further comprises:

splitting sequences of legs of itineraries into individual faring atoms if the legs are flights on a same airline.