Rules validation for travel planning system

• US 6,377,932 B1
• Filed: 07/02/1998
• Issued: 04/23/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): Hafiz, Tariq R.
• Assistant Examiner(s): ALLEN, AKIBA KANELLE
• Application Number:
  US09/109,486
• Time in Patent Office: 1,391 Days
• Field of Search: 705/5, 705/6, 705/1
• US Class Current: 705/5
• 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

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 method of validating fares in a travel planning system comprises:

retrieving a fare rule for a fare;

applying the retrieved fare rule to an itinerary to determine an answer as to whether the fare can be used with the itinerary; and

storing the answer provided from applying the rule and determining for a subsequent application of the rule to a fare whether there is a stored answer as to whether the fare can be used with the itinerary that corresponds to a previous application of the rule to be applied to a fare component and, if there is a stored answer, return the stored answer.

2. The method of claim 1 wherein if the rule does not have a corresponding stored answer, further comprising:

retrieving the rule; and

applying the rule to the itinerary and storing the answer resulting from applying the rule.

3. The method of claim 1 wherein the itinerary includes a sequence of flight segments spanned by a single fare.

4. The method of claim 1 wherein the itinerary is a faring atom that corresponds to a sequence of flight segments spanned by a single fare.

5. A method for retrieving rules over multiple travel dates comprises:

retrieving rules from a rules database that divides rules according to sets of records having travel dates;

finding a first record from the sets of records that is matched to a current fare;

storing an answer of applying the matched record and storing a latest travel date for which the answer remains valid and;

determining for subsequent travel dates whether the subsequent travel date falls within a bound defined by the stored date.

6. The method of claim 5 wherein if the subsequent date does fall within the bound of the stored date;

using the stored result corresponding to the stored travel date to validate the fare.

7. The method of claim 5 wherein if the travel date does not fall within the bound of the stored travel date, comprising:

retrieving rules for the subsequent travel date.

8. The method of claim 5 wherein retrieving rules comprises:

retrieving rules from the rules database;

finding a first rule matched to the current fare; and

storing the resulting answer of applying the rule.

9. A method of validating faring atoms for an airline travel planning system comprises:

retrieving a faring atom and determining whether a previous answer of applying a current rule is stored in the faring atom; and

if the previous answer is stored, returning the previous stored answer for the current rule.

10. The method of claim 9 wherein if an answer for a rule is not stored, applying the rule.

11. The method of claim 10 wherein applying the rule further comprises:

storing the answer of applying the rule in the faring atom.

12. The method of claim 10 further comprising:

evaluating whether application of the rule returns a pass or defer result and, if it returns a pass or defer result, constructing a fare component from the faring atom.

13. The method of claim 12 wherein if the application returns a defer answer further comprising:

storing the deferred rule in the fare component.

14. The method of claim 11 further comprising:

evaluating whether application of the rule returns a pass or defer answer and, if it returns a pass or defer answer, constructing a faring component from the faring atom.

15. The method of claim 14 wherein if the application returns a defer answer further comprising:

storing the deferred rule in the fare component.

16. A computer program product residing on a computer readable medium for validating faring atoms, for inclusion in a pricing solution of a travel planning system, comprises instructions for causing a computer to:

retrieve rules from a rules database that divides rules according to hierarchical sets of records;

search each hierarchical set of records for a first record from the hierarchical sets of records that matches a current faring atom;

store matched records and a latest date for which a result of applying the matched record remains valid;

determine for a subsequent travel date of the faring atom whether the subsequent travel date of the faring atom falls within a bound defined by the stored travel date; and

if the subsequent travel date does fall within the bound of the stored date,

use a rule corresponding to the stored travel date to validate the faring atom.

17. The product of claim 16 wherein if the date does not fall within the bounds of the stored date, the instructions retrieve rules for the subsequent date.

18. The product of claim 17 wherein instructions that cause the computer to retrieve rules comprises instructions for causing the computer to:

retrieve rules from the rules database and

find a first rule matched to the current fare and store the rule.

19. A computer program product residing on a computer readable medium for validating fares for inclusion in a pricing solution of a travel planning system, comprises instructions for causing a computer to:

retrieve a fare rule for a fare;

apply the rule to an itinerary to provide an answer as to whether the fare can be used with the itinerary; and

store the answer resulting from the applied rule and determine for a subsequent application of the rule whether there is a answer that corresponds to a previous application of the rule to be applied to a fare component; and

, if there is a stored answer;

return the stored answer.

20. The product of claim 19 wherein if the rule does not have a corresponding stored answer, the instructions cause the computer to

apply the rule to the fare.

21. The product of claim 19 wherein the fare is represented as a faring atom that corresponds to a sequence of flight segments spanned by a single fare.

22. The method of claim 20 wherein the fare is a faring atom that corresponds to a sequence of flight segments spanned by a single fare.

23. A computer program product residing on a computer readable medium for validating faring atoms, for inclusion in a pricing solution for an airline travel planning system, comprises instructions for causing a computer to:

retrieve a faring atom and determining whether a current rule has an answer that is stored in the retrieved faring atom; and

if the current rule has a result that is stored in the retrieved faring atom,

return the answer stored for the rule;

if the current rule has a result that is not stored in the faring atom,

apply the rule to the fare.

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

cache the answer provided by the application of the rule in the faring atom.

25. The product of claim 24 further comprising instructions that evaluate the rule and, if it returns a pass or defer answer, construct a faring component from the faring atom.

26. The product of claim 25 wherein if the application returns a defer answer further comprising instructions that cause the computer to:

store the deferred record in the fare component.

27. A travel planning system, comprises:

a computer; and

a computer readable medium including;

a computer program product residing on the computer readable medium for validating faring atoms, for inclusion in a pricing solution provided by the travel reservation system, comprises instructions for causing to;

retrieve rules from a rules database that divides rules according to hierarchical sets of records;

search the hierarchical sets of records for a first record from the hierarchical sets of records that matches a current faring atom;

store matched records and a latest travel date for which a result of applying the matched record remains valid;

determine for a subsequent travel date of the faring atom whether the subsequent travel date of the faring atom falls within a bound defined by the stored travel date; and

if the subsequent travel date does fall within the bound of the stored travel date,

use a stored answer corresponding to the stored travel date to validate the faring atom.

28. The system of claim 27 wherein if the computer program product determines that the date does not fall within the bounds of the stored date, the instructions retrieve rules for the subsequent date.

29. The system of claim 27 wherein the instructions of the computer program product to cause the computer to retrieve rules further comprises instructions for causing the computer to:

retrieve rules from the rules database; and

find a first rule matched to the current fare and store the answer obtained from applying the rule.