Factored representation of a set of priceable units

• US 6,381,578 B1
• Filed: 07/02/1998
• Issued: 04/30/2002
• 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): Cosimano, Edward R.
• Application Number:
  US09/109,876
• Time in Patent Office: 1,398 Days
• Field of Search: 701/201, 701/202, 705/5, 705/6, 705/400, 707/10, 707/102, 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 computer storage medium storing a data structure of groups of fare components that are mutually dependent with respect to pricing, the groups of fare components used in a travel planning system with a travel planning software program to provide pricing solutions, the data structure comprising:

a priceable unit cores data structure; and

a priceable unit labels data structure corresponding to a group of priceable unit cores and sets of faring atoms that represent sets of priceable units.

2. The computer storage medium of claim 1 wherein the priceable unit cores data structure comprises:

a fares field for storing a list of fares.

3. The computer storage medium of claim 1 wherein the priceable unit labels data structure comprises

a field corresponding to priceable unit cores for storing a set of priceable unit cores;

and

faring atom sets for storing a list of sets of faring atoms per slice of a journey.

4. The computer storage medium of claim 1 wherein the priceable-unit-labels and priceable-unit-cores share entries to minimize the number of priceable-unit-cores and priceable-unit-labels.

5. The computer storage medium of claim 1 wherein the priceable-unit-labels and priceable-unit-cores data structure are factored representations of these components.

6. The computer storage medium of claim 1 wherein each priceable-unit-core contains a set of fares and other information associated with the fares including discounts, surcharges and penalties.

7. The computer storage medium of claim 1 wherein the priceable-unit-label data structure compactly represents connections between faring-atoms and priceable-unit-cores.

8. A method of providing a priceable units data structure comprises:

enumerating a collection of faring markets;

enumerating collections of sets of faring components by selecting sets of fare components for each faring market;

enumerating collections of faring components by operating on sets of fare components to evaluate deferred record-2'"'"'s on collections of fare components;

representing the enumerated collections of faring components in the priceable units data structure that is represented by priceable unit labels data structure and priceable unit cores data structure.

9. The method of claim 8 wherein enumerating collections of faring markets further comprises:

selecting a process to enumerate said collections of faring markets in accordance with the type of priceable units that are constructed.

10. The method of claim 9 wherein said type of priceable units are a one-way priceable unit, a round trip priceable unit, an open jaw priceable unit, or a circle trip priceable unit.

11. The method of claim 9 wherein enumerating of collections of sets of faring components by applying deferred record-2'"'"'s further comprises:

applying deferred record-2'"'"'s to the collection of fare components.

12. A method of constructing priceable units comprising:

selecting one fare-component from each of a collection of sets of fare components; and

evaluating the selected fare components for any deferred fare rules.

13. The method of claim 12 wherein selecting comprises:

enumerating complete collections of fare-components; and

evaluating comprises;

applying deferred record-2s to the enumerated fare-components.

14. The method of claim 13 wherein:

enumerating a collection of sets of fare-components and applying deferred rules is accomplished by a GET-OR-AND-OR function that labels the collection of sets of fare components, evaluates any deferred rule conditions, and returns a representation of a set of valid priceable-units in OR-AND-OR form.

15. The method of claim 14 wherein priceable-unit-cores and priceable-unit-labels are constructed by applying the get-OR-AND-OR procedure to fare components by iterating over an inner AND-OR form of the fare components to construct priceable-unit-cores if no identical priceable-unit-core already exists and priceable-unit-labels if no identical priceable-unit-label already exists.

16. The method of claim 15 wherein priceable-unit-labels are constructed by:

mapping fare-components to faring-atoms.

17. A method of factoring faring components into a priceable unit representation comprises:

determining a procedure to use depending on the number of fare components involved with the priceable units; and

applying an auxiliary function determined in accordance with the number of fare components to the collection of fare-components to determine potential priceable units by evaluating any deferred record-2s and constructing a priceable unit for any fare component that returns a result or pass.

18. The method of claim 17 wherein factoring priceable-units of size three components or greater comprises:

determining a subset of possible priceable-units that have no deferred record-2s;

building priceable-units from the subset of priceable units; and

constructing a factored representation from the subset of priceable units.

19. The method of claim 18 wherein the set of faring-markets and a fare-component set, have times corresponding to flights, and determining a subset further comprises:

setting time-bounds based on the faring-markets by determining time bound ranges for valid faring atoms; and

reapplying deferred record-2s to faring-atoms to determine which of the faring markets have valid faring atoms; and

discarding any faring atoms that fail or are deferred and retaining faring atoms for all deferred record-2s that evaluate to pass.

20. The method of claim 17 further comprising:

applying a second auxiliary function that partitions fare-components-by-surcharges into subsets that have the same secondary characteristics including surcharges, discounts, and penalties.

21. The method of claim 20 wherein factoring priceable-units of size one comprises:

passing a single fare-component set;

applying deferred record-2s to produce a final set of valid fare-components;

partitioning the final set into sets with the same surcharges, penalties, and discounts.

22. The method of claim 21 wherein factoring priceable-units of size two components comprises:

enumerating priceable units by selecting one fare component from each set of components; and

testing the select fare components against corresponding deferred record-2s; and

adding valid priceable unit to an OR-AND-OR representation of priceable units.