Rules validation for travel planning system

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

What is claimed is:

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.

Description

BACKGROUND

This invention relates to computerized travel planning systems.

Travel planning systems are used to produce itineraries and prices by selecting suitable travel units from databases containing geographic, scheduling and pricing information. In the airline industry, fundamental travel units include "flights" (sequences of regularly scheduled takeoffs and landings assigned a common identifier) and "fares" (prices published by airlines for travel between two points). The term "itinerary" is often used to refer to a sequence of flights on particular dates, and the term "pricing solution" is often used to refer to a combination of fares and itineraries that satisfies a travel request.

The databases usually contain schedule information provided by airlines, typically in the so-called Standard Schedules Information Manual (SSIM) format, and usually fares published by airlines and resellers, typically provided through the intermediary Airline Tariff Publishing Company.RTM. (ATPCO). The database may also contain "availability" information that determines whether space is available on flights, or this may be obtained through communication links to external sources such as airlines.

Presently, so-called computer reservation system (CRSs) operate to produce fare and schedule information. There are four generally known computer reservation systems that operate in the United States, Sabre.RTM., Galileo.RTM., Amadeus.RTM. and WorldSpan.RTM.. The typical CRS contains a periodically updated central database that is accessed by subscribers such as travel agents through computer terminals. The subscribers use the computer reservation system to determine what airline flights are operating in a given market, what fares are offered and whether seats are available on flights to make bookings and issue tickets to clients.

The computer reservation systems typically conduct searches using the information contained in the database to produce itineraries that satisfy a received request. The search results are sorted and returned to the requester s computer for display. Typically, the number of possible itineraries and pricing solutions that are returned by a CRS is a small portion of the total set that may satisfy a passengers request.

SUMMARY

According to an aspect of the invention, a method of validating fares in a travel planning system includes retrieving a fare rule for a fare, applying the rule to an itinerary to determine if the fare can be used with the itinerary; and storing results of applying the rule.

According to an additional aspect of the invention, a method for retrieving rules over multiple travel dates includes retrieving rules from a rules database that divides rules according to sets of records having travel dates and finding a first record from the sets of records that is matched to a current fare. The method also includes storing a result of applying the matched record and storing a latest travel date for which the result remains valid and determining for subsequent travel dates whether the subsequent travel date falls within a bound defined by the stored date.

According to a further aspect of the invention, a method of validating faring atoms for an airline travel planning system includes retrieving a faring atom and determining whether a previous result of applying a current rule is stored and if the previous result is stored, returning the previous result stored for the current rule.

According to a still further aspect of the invention, 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, includes 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 and store matched records and a latest date for which a result of applying the matched record remains valid. The program also includes instructions to cause the computer to 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 and use a rule corresponding to the stored travel date to validate the faring atom.

According to a still further aspect of the invention, a travel planning system, includes a computer and a computer readable medium. The computer readable includes a computer program product residing on the computer readable medium for validating faring atoms, for inclusion in a pricing solution provided by the travel planning system and includes instructions for causing to retrieve rules from a rules database that divides rules according to hierarchical sets of records, search the hierarchical set of records for a first record from the hierarchical set 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 and determine for a subsequent travel date of the faring atom whether the subsequent date falls within a bound defined by the stored travel date; and if the subsequent date does fall within the bound of the stored date, use a stored result corresponding to the stored travel date to validate the faring atom.

BRIEF DESCRIPTION OF THE DRAWINGS

The foregoing features and other aspects of the invention will be described in further detail by the accompanying drawings, in which:

FIG. 1 is a block diagram of a client server travel planning system.

FIG. 2 is a flow chart showing a server process used in the system of FIG. 1.

FIG. 3 is a flow chart showing a client process used in the system of FIG. 1.

FIGS. 3A-3B are diagrammatic representations of pricing graphs.

FIGS. 4A-4B are flow charts showing a faring process used in the server process of FIG. 2.

FIG. 5 is a flow chart showing a process to decompose an itinerary into faring atoms used in the process of FIG. 4A.

FIG. 6 is a flow chart showing a process for partitioning itineraries used in the process of FIG. 5.

FIG. 7 is a flow chart showing a process for applying rules to faring atoms used in the faring process of FIG. 4A.

FIGS. 8A-8C are flow charts showing a process for retrieving fare rules.

FIG. 9 is a flow chart showing a process for applying fare rules.

FIG. 10 is a flow chart showing a process for determining priceable units used in the faring process of FIGS. 4A-4B.

FIG. 10A is a flow chart showing a process for enumerating collections of sets of faring components used in the process of FIG. 10.

FIG. 11 is a flow chart showing a process for enumerating collections of faring components used in the process of FIG. 10.

FIG. 12 is a flow chart showing a process for representing priceable units in a compact representation.

FIGS. 13-15 are flow charts showing processes for determining priceable units.

FIG. 16 is a flow chart showing a process for producing slice label sets.

FIG. 17 is a flow chart showing the process for constructing a pricing graph.

FIG. 18 is a block diagram showing the relationship between the pricing graph and a graphical user interface for the travel planning system of FIG. 1.

FIG. 19 is a flow chart showing various enumeration functions.

FIG. 20; is a diagram of a window depicting a user interface.

FIG. 21 is a diagram of a window used in an initial query;

FIG. 22 is a diagram of a window depicting an exemplary solution of a one-way travel request.

FIG. 23 is a diagram of a window depicting an itinerary and associated fares corresponding to one of the solutions depicted in FIG. 21.

FIG. 24 is a diagram of a window depicting an exemplary solution of round trip travel request.

FIG. 25 is a diagram of a window depicting an outbound itinerary and a possible return itinerary and associated fares corresponding to one of the solutions depicted in FIG. 24.

FIG. 26 shows the window generally depicted in conjunction with FIG. 24 modified based upon a user selected criteria.

FIG. 27 shows a window depicting a histogram

DETAILED DESCRIPTION

Referring now to FIG. 1, a travel planning system 10 is shown. The travel planning system can be used with various forms of travel such as airline, bus and railroad and is particularly adapted for air travel. It includes a server computer 12 having a computer memory or storage media 14 storing a server process 15. The server process includes a scheduler process 16 and a faring process 18. The scheduler process 16 is any suitable scheduler process that will produce from a travel request sets of flights that can satisfy the request. The faring process 18 is a process that determines a set of valid fares and links the set of valid fares to the sets of flights to form a pricing solution. The server process 15 can be configured to produce other travel-related information as a result of a user query. For example, the server process 12 can produce routes or airline suggestions, optimal travel times and suggestions for alternative requests.

The travel planning system 10 also includes a plurality of databases 20a, 20b which store industry-standard information pertaining to travel (e.g., airline, bus, railroad, etc. ). For example, database 20a can store the Airline Tariff Publishing Company database of published airline fares and their associated rules, routings and other provisions, the so-called ATPCO database. Database 20b can be an inventory of current availability of airline information for a particular carrier and so forth. The databases 20a-20b are typically stored locally and updated periodically by accessing remote resources 21a, 21b that maintain the respective databases.

The system 10 also includes a plurality of clients 30a-30c (generally, 30) implemented by terminals or preferably personal computers. The clients 30a-30c are coupled to the server 12 via a network 22 which is also used to couple the remote resources (21a-21c) that supply the databases 20a-20b to the server 12. The network 22 can be any local or wide area network or an arrangement such as the Internet.

The clients 30a-30c are preferably smart clients. That is, using client 30c as an illustrative example, client 30c includes a client computer system 32 including a computer memory or storage media 34 that stores a client process 36 and a set of pricing solutions 38. The set of pricing solutions 38 in one embodiment is provided from the server process 15 and comprises a set of fares that are valid for a journey, and associated information linking the fares to the flight segments of the journey.

The set of pricing solutions 38 is obtained from the server 12 in response to a user request sent from the client 30c to the server 12. The server 12 executes the server process 15 using the scheduling process 16 and the faring process 18 to produce a set of pricing solutions for a particular journey. If requested by the client, for example client 30c, the server 12 will deliver the set of pricing solutions 38 to the requesting client 30c. Under control of the client process 36, the requesting client 30c can store and/or logically manipulate the set of pricing solutions 38 to extract or display a subset of the set of pricing solutions as a display representation 41 on the monitor 40.

SERVER PROCESS

Referring now to FIG. 2, the server process 18 is preferably executed on the server computer 12 but could be executed on the client computer 32. The server process 18 is responsive to a user input query 48. The user input query 48 would typically include minimal information needed to determine a set of pricing solutions. This information typically requires at a minimum, an origin and a destination for travel. In addition, the information could also include times, dates and so forth.

This query 48 is fed to the scheduler process 16 that produces a large number of itineraries, that is, sequences of flight segments between the origin and destination for each slice of a journey. Examples of scheduler systems that may be used include the OAG Flight Desk.RTM. (Official Airlines Guide, a division of Reed Travel Group) or schedule components of computer reservation systems (CRS's) such as Sabre.RTM., Apollo.RTM., Amadeus.RTM. and WorldSpan.RTM.. It is preferable in order to obtain the largest number of possible itineraries to use a scheduler with dynamic connection generation. Such a scheduler is described in co-pending patent application entitled SCHEDULER SYSTEM FOR TRAVEL PLANNING SYSTEM, Ser. No. 09/109,622, filed on Jul. 2, 1998 by Carl G. deMarcken et al. and assigned to the assignee of the invention and incorporated herein by reference.

The scheduler process 16 provides the itineraries to a faring process 18. The faring process 18 provides a set of pricing solutions 38 by finding valid fares corresponding to the itineraries produced by the scheduler process 16. The faring process 18 validates the fares for inclusion in the set of pricing solutions 38.

The set of pricing solutions 38 is used by an availability system 58 that interrogates an airline inventory database 20b to determine whether there are seats available on particular flights for particular pricing solutions. The availability system 58 uses the airline inventory database 20b as a filter to remove from the set of pricing solutions 38 those pricing solutions for which there are not available seats. The availability system 58 is shown after the faring process 18. However, it could be included at nearly any point in the server process 18. In addition, it is shown being fed by the pricing solution when it may only receive flight information from the scheduler process 16 depending on the airline.

The client system 30c receives the results from the server process 18. These results are the set of pricing solutions 38 and/or pricing solutions based upon availability. The client process 36 executed in the client 30c uses this information or a subset of it to access a booking system 62 to provide a booking and reservation for a user selected, enumerated pricing solution, as will be described below.

CLIENT PROCESS

Referring now to FIG. 3, the client process 36 receives a listing of possible itineraries from the scheduler process 16 as well as the set of fares from the faring process 18 or the availability system 58. The set of pricing solutions 38, if obtained from the faring process 18, will include a large number of pricing solutions for which there is not any available inventory. Therefore, the components would need to be first checked out with an airline prior to booking. The set of pricing solutions 38 if obtained after the availability system 58 should contain pricing solutions which have a high degree of availability for booking on an airline.

In one embodiment, the set of pricing solutions 38 is provided in a compact representation 38'. A preferred, compact representation 38' of the set of pricing solutions 38 is as a data structure comprising a plurality of nodes including itineraries and fares and that can be logically manipulated using value functions to enumerate a set of pricing solutions. One preferred example is a graph data structure type particularly a directed acyclic graph (DAG) that contains nodes that can be logically manipulated or combined 74 to extract 75 a plurality of pricing solutions for display 72.

The client process 36 receives the flight information from scheduler process 16 and the pricing solution from the faring process 18 or the availability system 56 and enumerates pricing solutions from the directed acyclic graph (DAG) representation. The enumerated 70 set of pricing solutions is rendered or displayed 72 in a graphical user interface 41 on the client monitor 40 (FIG. 1) in a manner as will be described below.

In response to user input 76, the client 40 can manipulate 74 travel options and can query the local copy of the DAG to produce and display a subset of pricing solutions enumerated from the DAG that satisfy the query 76. The manipulation process used to control the display and change the travel options will be described below.

A directed acyclic graph (DAG) is used to represent the compact set of pricing solutions 38' since, in general, the number of nodes needed to represent a typical pricing solution will be substantially less than the actual number of pricing solutions represented by the DAG. This significantly increases the efficiency of transfer of a set of pricing solutions 38 from the server process 18 to the client process 36. The DAG representation also minimizes the storage requirements for the set of pricing solutions 38. The DAG representation permits the use of powerful search, sorting and manipulation processes to produce various subsets of set of pricing solutions in an efficient manner. As used herein, a directed acyclic graph (DAG) is a set of nodes connected by directed arcs, that have no loops of arcs in the same direction. If a node A is connected to a node B via an arc A.fwdarw.B, then A is called a parent of B, and B is called a child of A. Each node may have zero, one or many parents and zero, one or many children. As used herein, a pricing solution that is represented by a graph will be referred to as a pricing graph.

PRICING-GRAPH

A pricing graph that is produced by the faring process 18 and that represents a pricing solution includes three types of nodes. The first type of node is an exclusive node, i.e., "OR" node. An OR node N with children A, B and C represents an exclusive choice between A, B and C. In other words, a pricing-solution involving node N contains either the fares and itineraries represented by A, or by B, or by C.

The second type of node is a collection node, i.e., an "AND" node. An AND node N with children A, B and C represents the sum of A, B and C. In other words, a pricing solution involving N contains all the fares and itineraries found within A, B and C.

The third type of node is a terminal node. Terminal nodes are used to hold pricing objects. Pricing objects include fares, itineraries, surcharges, routes, prices, booking codes, taxes, rules/restrictions and other information of the user or information that might be part of a travel option. Collectively, "AND" and "OR" nodes are non-terminal nodes.

An example of the pricing-graph for a hypothetical round-trip journey is presented below in TABLE 1. For each node, its type and children are listed. If a node is a terminal, the fare or itinerary is provided. Many nodes in the pricing graph have more than one parent.

    TABLE 1
    Node  Type  Children          Object
      0   OR    Nodes 1, 2, 3
      1   AND   Nodes 10, 14,
                17, 17
      2   AND   Nodes 4, 5
      3   AND   Nodes 13, 15,
                19, 19
      4   OR    Nodes 8, 9
      5   OR    Nodes 6, 7
      6   AND   Nodes 14, 16
      7   AND   Nodes 15, 18
      8   AND   Nodes 13, 16
      9   AND   Nodes 13, 18
     10   OR    Nodes 11, 12
     11   Itin.                   Slice 1: BOS.fwdarw.LAX UA023
     12   Itin.                   Slice 1: BOS.fwdarw.DFW UA100,
                                  DFW.fwdarw.LAX UA103
     13   Itin.                   Slice 1: BOS.fwdarw.SAN NW222
     14   Itin.                   Slice 2: LAX.fwdarw.BOS UA515
     15   Itin.                   Slice 2: SAN.fwdarw.BOS NW223
     16   Fare                    UA BOS-LAX One-way "Y"
     17   Fare                    UA BOS-LAX Round-trip "QE7NR"
     18   Fare                    NW BOS-SAN One-way "F"
     19   Fare                    NW BOS-SAN Round-trip "H7NR"

    TABLE 2
    Solution
    Number  Itineraries              Fares
       1    Slice 1: BOS.fwdarw.LAX UA023 UA BOS-LAX RT "QE7NR"
            Slice 2: LAX.fwdarw.BOS UA515 UA BOS-LAX RT "QE7NR"
       2    Slice 1: BOS.fwdarw.LAX UA023 UA BOS-LAX OW "Y"
            Slice 2: LAX.fwdarw.BOS UA515 UA BOS-LAX OW "Y"
       3    Slice 1: BOS.fwdarw.LAX UA023 UA BOS-LAX OW "Y"
            Slice 2: SAN.fwdarw.BOS NW223 NW BOS-SAN OW "F"
       4    Slice 1: BOS.fwdarw.DFW UA100, UA BOS-LAX RT "QE7NR"
            DFW_LAX UA103
            Slice 2: LAX.fwdarw.BOS UA515 UA BOS-LAX RT "QE7NR"
       5    Slice 1: BOS.fwdarw.DFW UA100, UA BOS-LAX OW "Y"
            DFW_LAX UA103
            Slice 2: LAX.fwdarw.BOS UA515 UA BOS-LAX OW "Y"
       6    Slice 1: BOS.fwdarw.DFW UA100, UA BOS-LAX OW "Y"
            DFW_LAX UA103
            Slice 2: SAN.fwdarw.BOS NW223 NW BOS-SAN OW "F"
       7    Slice 1: BOS.fwdarw.SAN NW222 NW BOS-SAN OW "F"
            Slice 2: LAX.fwdarw.BOS UA515 UA BOS-LAX OW "Y"
       8    Slice 1: BOS.fwdarw.SAN NW222 NW BOS-SAN RT "H7NR"
            Slice 2: SAN.fwdarw.BOS NW223 NW BOS-SAN RT "H7NR"
       9    Slice 1: BOS.fwdarw.SAN NW222 NW BOS-SAN OW "F"
            Slice 2: SAN.fwdarw.BOS NW223 NW BOS-SAN OW "F"

    TABLE 3
    Node  Type  Children        Object
      0   AND   Nodes 1, 6, 11
      1   OR    Nodes 2, 3, 4
      2   AND   Nodes 5, 40
      3   AND   Nodes 41, 41
      4   AND   Nodes 42, 42
      5   OR    Nodes 39, 40
      6   OR    Nodes 7, 8, 9
      7   AND   Nodes 20, 10
      8   AND   Nodes 21, 10
      9   AND   Nodes 22, 10
     10   OR    Nodes 23, 24,
                25, 26
     11   OR    Nodes 12, 13, 14,
                16, 17, 18
     12   AND   Nodes 27, 15
     13   AND   Nodes 28, 15
     14   AND   Nodes 29, 15
     15   AND   Nodes 30, 31, 32
     16   AND   Nodes 33, 19
     17   AND   Nodes 34, 19
     18   AND   Nodes 35, 19
     19   OR    Nodes 36, 37, 38
     20   Itin.                 Slice 1: LAX.fwdarw.DFW NW100,
                                DFW.fwdarw.BOS AA223
     21   Itin.                 Slice 1: LAX.fwdarw.DFW NW137,
                                DFW.fwdarw.BOS AA223
     22   Itin.                 Slice 1: LAX.fwdarw.DFW NW137,
                                DFW.fwdarw.BOS AA414
     23   Fare                  DFW, LAX NW "Y" OW
     24   Fare                  DFW, LAX NW "F" OW
     25   Fare                  DFW, LAX NW "C" OW
     26   Fare                  DFW, LAX NW "QA7" OW
     27   Itin.                 Slice 2: BOS.fwdarw.DFW AA67,
                                DFW.fwdarw.LAX CO716
     28   Itin.                 Slice 2: BOS.fwdarw.DFW AA67,
                                DFW.fwdarw.LAX CO717
     29   Itin.                 Slice 2: BOS.fwdarw.DFW AA67,
                                DFW.fwdarw.LAX CO719
     30   Fare                  DFW, LAX CO "F" OW
     31   Fare                  DFW, LAX CO "C" OW
     32   Fare                  DFW, LAX CO "Y" OW
     33   Itin.                 Slice 2: BOS.fwdarw.DFW AA852,
                                DFW.fwdarw.LAX DL186
     34   Itin.                 Slice 2: BOS.fwdarw.DFW AA852,
                                DFW.fwdarw.LAX DL180
     35   Itin.                 Slice 2: BOS.fwdarw.DFW AA852,
                                DFW.fwdarw.LAX DL343
     36   Fare                  DFW, LAX DL "F" OW
     37   Fare                  DFW, LAX DL "C" OW
     38   Fare                  DFW, LAX DL "Y" OW
     39   Fare                  DFW, BOS AA "QE7NR" RT
     40   Fare                  DFW, BOS AA "QE7IP" RT
     41   Fare                  DFW, BOS AA "QE14NR" RT
     42   Fare                  DFW, BOS AA "QE21NR" RT

             TABLE 4
        Faring-Atom Number     Legs and Departure Times
                1              DFW.fwdarw.BOS UA005 12NOV 12:30
                2              BOS.fwdarw.YYZ UA010 12NOV 18:00
                3              DFW.fwdarw.BOS UA005 12NOV 12:30
                               BOS.fwdarw.YYZ UA010 12NOV 18:00
                4              YYZ.fwdarw.YVR AC121 13NOV 01:00

    TABLE 5
    Faring-Atom fields   Use
    legs-and-departure-times A list of legs and their departure times and
                         dates.
    faring-market        The faring-market that this faring-atom is in.
    cached-results       A storage space used to eliminate redundant
                         computation in the rule-checking process. As
                         rule record-2s are applied to faring-atoms, the
                         results are stored in this field. If the same
                         record-2 is applied again, the answer is
                         retrieved rather than recomputed.
    priceable-unit-labels A list of the priceable-unit-labels that the
                         faring-atom enters into.

    TABLE 6
    Fare-Component fields Use
    fare               The fare-component's fare.
    faring-atom        The fare-component's faring-atom.
    deferred-record-2s A list of non-category-10 record-2s that have
                       not been fully evaluated.
    combinability-record-2 If the fare's rules include a category-10
                       ("Fare Combinability" record-2, it is stored
                       here.
    surcharges         A list of surcharges, penalties, discounts and
                       other pieces of information produced during
                       the rule-checking process.

    TABLE 7
    Priceable-Unit-Core
    fields             Use
    fares              A list of fares.
    slice-numbers      A list of the slices the fares originate from.
    surcharges         A list of surcharges, penalties, discounts and
                       other pieces of information produced during the
                       rule-checking process.

    TABLE 8
    Priceable-Unit-Label
    fields             Use
    priceable-unit-cores A set of priceable-unit cores.
    slice-numbers      A list of the slices the fares and faring-atoms
                       originate from.
    faring-atom-sets   A list of sets of faring-atoms, one per slice.

                             TABLE 9
                             Use
    Slice-Label-Set fields
    multi-slice-PU-labels    A set of multi-slice PU-labels.
    itinerary-label-holders  A set of itinerary-label-holders.
    Itinerary-Label-Holder fields
    itinerary                An itinerary.
    division-label-holders   A set of division-label-holders.
    Division-Label-Holder fields
    division                 An itinerary division.
    single-slice-PU-label-sets A set of sets of single-slice PU-labels.

                             TABLE 10
                             Use
        Open-Label-Set fields
        open-PU-labels       A set of open multi-slice FU-labels.
        backward-links       A set of backward-links.
        Backward-Link fields
        slice-label-set      A slice-label-set.
        open-label-set       An open-label-set.

    TABLE 11
    price-itinerary-sets(itinerary-sets, fare-database, rule-database,
     routing-database, environmental-information)
        //
        // itinerary-sets is a set of sets of itineraries, one per slice.
        // environmental-information contains information about the passenger,
     the current date, the location
        // where tickets will be purchased, and other non-itinerary-based
     information that is necessary for applying
        // fare rules.
        //
        Let faring-market-sets = {}
        // Construct itinerary-divisions, faring-markets and faring-atoms.
        Let slice-number = 1
        For itinerary-set in itinerary-sets
          //
          // create-divisions constructs the itinerary-divisions,
     faring-markets and faring-atoms for
          // all the itineraries within a slice. It returns a set of
     faring-markets.
          faring-market-sets += create-divisions(itineraries, slice-number,
     fare-database)
          slice-number += 1
        // Apply fare rules, constructing fare-components in each
     faring-market.
        For faring-market-set in faring-market-sets
          //
          // apply-fare-rules constructs fare-components for each faring-market
     within a slice.
          // This process contains pseudo-code for apply-fare-rules.
          apply-fare-rules(faring-market-set, fare-database, rule-database,
                routing-database, environmental-information)
        // Create priceable-units.
        // for create-priceable-units
        create-priceable-units(faring-market-sets)
        // Link itineraries between slices. This procedure returns either nil,
     if there are no pricing-solutions, or
        // a "root" open-label-set. This process is described in
     link-itineraries
        Let root-object = link-itineraries(itinerary-sets)
        If (root-object = nil)
          return(nil)
        // Create the pricing-graph from the data-structures that have been
     built in the preceding steps.
        // This process includes psedo-code for create-pricing-graph.
        Let root-node = create-pricing-graph(root-object)
        // Return the pricing graph.
        return(root-node)

    TABLE 12
    create-divisions(itineraries, slice-number, fare-database)
        Let faring-atoms = {}
        Let faring-markets = {}
        Subroutine get-faring-market(origin-airport, destination-airport,
     airline)
          Let origin-city = city(origin-airport)
          Let destination-city = city(destination-airport)
          Let previous-faring-market = find(<origin-city, destination-city,
     airline>, faring-markets)
          If (previous-faring-market)
            return(previous-faring-market)
          Else
            If (fares-exist(origin-city, destination-city, airline))
              Let faring-market = new-faring-market()
              faring-market.slice-number = slice-number
              faring-market.origin-city = origin-city
              faring-market.destination-city = destination-city
              faring-market.airline = airline
              faring-market.faring-atoms = {}
              faring-markets += faring-market
              return(faring-market)
            Else
              return(nil)
        Subroutine get-faring-atom(legs-and-departure-times, origin-airport,
     destination-airport, airline)
          Let previous-faring-atom = find(legs-and-departure-times,
     faring-atoms)
          If (previous-faring-atom)
            return(previous-faring-atom)
          Else
            Let faring-market = get-faring-market(origin-airport,
     destination-airport, airline)
            If (faring-market <> nil)
              Let faring-atom = new-faring-atom()
              faring-atom.faring-market = faring-market
              faring-atom.legs-and-departure-times = legs-and-departure-times
              faring-atom.priceable-unit-labels = {}
              faring-atom.cached-results = {}
              faring-market.faring-atoms += new-faring-atom
              faring-atoms += faring-atom
              return(faring-atom)
            Else
              return(nil)
        Subroutine get-online-divisions(legs-and-departure-times,
     origin-airport, destination-airport, airline)
          Let online-divisions = {}
          Let number-of-legs = length(legs-and-departure-times)
          Let single-faring-atom = get-faring-atom(legs-and-departure-times,
     origin-airport, destination-airport, airline)
          If (single-faring-atom <> nil)
            online-divisions += list(single-faring-atom)
          For i from 1 to number-of-legs - 1
            Let legs-and-departure-times1 = legs-and-departure-times[1 . . . i]
            Let legs-and-departure-times2 = legs-and-departure-times[i+1 . . .
     number-of-legs]
            Let destination-airport1 = destination-airport(faring-atom-legs1)
            Let origin-airport2 = origin-airport(faring-atom-legs2)
            If (is-not-same-flight-segment(legs-and-departure-times1,
     legs-and-departure-times2))
              Let faring-atom1 = get-faring-atom(legs-and-departure-times1,
     origin-airport,
                               destination-airport1, airline)
              Let faring-atom2 = get-faring-atom(legs-and-departure-times2,
     origin-airport2,
                               destination-airport, airline)
              If (faring-atom1 <> nil and faring-atom2 <> nil)
                online-divisions += list(faring-atom1, faring-atom2)
          return(online-divisions)
        For each itinerary in itineraries
          Let divisions = { {} }
          Let legs-and-departure-times = itinerary.legs-and-departure-times

          TABLE 13
          Slice 1 NW CHI_MSP         Slice 2 NW MSP_CHI
          faring-atoms               faring-atoms
          ORD_MSP NW220              MSP_ORD NW301
          12APR97 13:00              15APR97 19:00
          ORD_MSP NW220              MSP_ORD NW577
          13APR97 13:00              16APR97 12:00
          ORD_MSP NW220              MSP_ORD NW301
          14APR97 13:00              16APR97 19:00

            TABLE 14
            Category-3 field                   Example
            Earliest Permitted Travel Date     nil
            Latest Permitted Travel Date       19OCT97
            Fare-Component Based               false
            Geographic Specification           nil
            Earliest Record-3 Valid Date       15MAY88
            Latest Record-3 Valid Date         nil
            Available                          true

    TABLE 15
    apply-record-3-FC-category-3(record-3, faring-atom, passenger-information,
     current-date)
        If (record-3.available = false)
          return(unavailable)
        Let date = departure-date(faring-atom)
        If ((record-3.earliest-record-3-valid-date <> nil and
     record-3.earliest-record-3-valid-date > date) or
            (record-3.latest-record-3-valid-date <> nil and
     record-3.latest-record-3-valid-date < date))
          return(no-match))
        If (record-3.fare-component-based = true)
          Let travel-date = date
          If (record-3.geographic-specification <> nil)
            travel-date =
     apply-geographic-specification(record-3.geographic-specification,
     faring-atom)
          If ((record-3.earliest-permitted-travel-date <> nil and
     record-3.earliest-permitted-travel-date > travel-date) or
              (record-3.latest-permitted-travel-date <> nil and
     record-3.latest-permited-travel-date < travel-date))
            return(fail)
          Else
            return(pass)
        Else If (record-3.geographic-specification <> nil)
          return(defer)
        Else
          Let earliest-travel-date =
     earliest-priceable-unit-departure-date(faring-atom)
          Let latest-travel-date =
     latest-priceable-unit-departure-date(faring-atom)
          Let result = pass
          If (record-3.earliest-permitted-travel-date <> nil)
            If (record-3.earliest-permitted-travel-date >
     latest-travel-date)
              result = fail
            Else If (record-3.earliest-permitted-travel-date <=
     earliest-travel-date)
              result = defer
          If (record-3.latest-permitted-travel-date <> nil)
            If (record-3.latest-permitted-travel-date <
     earliest-travel-date)
              result = fail
            Else If (result <> fail and
     record-3.latest-permitted-travel-date >= latest-travel-date)
              result = defer
          return(result)

    TABLE 16
    apply-record-3-PU-category-3(record-3, fares, faring-atoms,
     prime-faring-atom, passenger-information, current-date)
        If (record-3.available = false)
          return(unavailable)
        Let date = departure-date(prime-faring-atom)
        If ((record-3.earliest-record-3-valid-date <> nil and
     record-3.earliest-record-3-valid-date > date) or
            (record-3.latest-record-3-valid-date <> nil and
     record-3.latest-record-3-valid-date < date))
          return(no-match))
        Let travel-date = date
        If (record-3.fare-component-based = true)
          If (record-3.geographic.specification <> nil)
            travel-date =
     apply-geographic-specification(record-3.geographic-specification,
     prime-faring-atom)
        Else
          travel-date = departure-date(faring-atoms)
          If (record-3.geographic-specification <> nil)
            travel-date =
     apply-geographic-specification(record-3.geographic-specification,
     faring-atoms)
        If ((record-3.earliest-permitted-travel-date <> nil and
     record-3.earliest-permitted-travel-date > travel-date) or
          (record-3.latest-permitted-travel-date <> nil and
     record-3.latest-permited-travel-date < travel-date))
          return(fail)
        Else
          return(pass)

    TABLE 17
    create-priceable-units(faring-market-sets)
        Let number-of-slices = length(faring-market-sets)
        Let priceable-unit-labels = {}
        For slice-number1 from 1 to number-of-slices
        For faring-market1 in faring-market-sets[slice-number1]
          Let airline = faring-market1.airline
          // Create one-way priceable-units.
          priceable-unit-labels = create-PUs-in-markets1(faring-market1,
     priceable-unit-labels, one-way)
          For slice-number2 from slice-number1 + 1 to number-of-slices
          For faring-market2 in
     faring-markets-on-carrier(faring-market-sets[slice-number2], airline)
            // Create single and double open-jaws.
            priceable-unit-labels = create-PUs-in-markets2(faring-market1,
     faring-market2,
                               priceable-unit-labels, open-jaw)
            If (faring-market1.destination-city = faring-market2.origin-city)
              // Create round-trips and circle-trips of size 2.
              If (faring-market2.destination = faring-market1.origin)
                priceable-unit-labels = create-PUs-in-markets2(faring-market1,
     faring-market2,
                                   priceable-unit-labels, round-trip)
                priceable-unit-labels = create-PUs-in-markets2(faring-market1,
     faring-market2,
                                   priceable-unit-labels, circle-trip2)
              For slice-number3 from slice-number2 + 1 to number-of-slices
              For faring-market3 in
     faring-markets-on-carrier(faring-market-sets[slice-number3], airline)
                If (faring-market2.destination-city =
     faring-market3.origin-city)
                  // Create circle-trips of size 3.
                  If (faring-market3.destination-city =
     faring-market1.origin-city)
                    priceable-unit-labels =
                      create-PUs-in-markets3(faring-market1, faring-market2,
     faring-
                  //
                  // More iterations for circle-trips of lengths 4 and 5.
                  //
                  . . .
        // Store priceable-unit-labels in faring-atoms.
        For priceable-unit-label in priceable-unit-labels
          For faring-atom-set in priceable-unit-label.faring-atom-sets
            For faring-atom in faring-atom-set
              faring-atom.priceable-unit-labels += priceable-unit-label

    TABLE 18
    create-PUS-from-fare-components(faring-markets, fares, fare-component-sets,
     existing-PU-labels,
                               environmental-information)
        Let slice-numbers = {}
        Let PU-labels = existing-PU-labels
        Let PU-cores = {}
        For faring-market in faring-markets
          slice-numbers += faring-market.slice-number
        For AND-OR in get-OR-AND-OR(faring-markets, fare-component-sets,
     environmental-information)
          //
          // AND-OR is a collection of sets of fare-components, representing
     all the priceable-units
          // that can be constructed by choosing one fare-component from each
     set.
          //
          Let PU-core = nil
          Let surcharges = {}
          Let faring-atom-sets = {}
          For fare-component-set in AND-OR
            surcharges += first(fare-component-set).surcharges
            Let faring-atom-set = {}
            For fare-component in fare-component-set
              faring-atom-set += fare-component.faring-atom
            faring-atom-sets += faring-atom-set
          // Find an existing PU-core with these fares and surcharges, or
     construct a new one.
          For test-PU-core in PU-cores
            If (test-PU-core.surcharges = surcharges)
              PU-core = test-PU-core
          If (PU-core = nil)
            PU-core = new-PU-core()
            PU-core.fares = fares
            PU-core.surcharges = surcharges
            PU-core.slice-numbers = slice-numbers
          // Find an existing PU-label with these faring-atoms, or construct a
     new one.
          Let PU-label = nil
          For test-PU-label in PU-labels
            If (test-PU-label.faring-atom-sets = faring-atom-sets)
              PU-label = test-PU-label
          If (PU-label = nil)
            PU-label = new-PU-label()
            PU-label.faring-atom-sets = faring-atom-sets
            PU-label.slice-numbers = slice-numbers
            PU-label.priceable-unit-cores = {}
            PU-labels += PU-label
          PU-label.priceable-unit-cores += PU-core
        return(PU-labels)

    TABLE 19
    Faring-market        Faring-Atoms      Fares
    Slice 1: UA          BOS.fwdarw.MSP UA100 UA BOS-MSP RT "Q"
    BOS.fwdarw.MSP       BOS.fwdarw.MSP UA200 UA BOS-MSP
                                           RT "M14"
                                           UA BOS-MSP OW "Y"
    Slice 1: NW          BOS.fwdarw.MSP NW300 NW BOS-MSP
                                           RT "HE7"
    BOS.fwdarw.MSP       BOS.fwdarw.MSP NW400 NW BOS-MSP
                                           RT "Q7NR"
                                           NW BOS-MSP OW "F"
    Slice 2: UA MSP.fwdarw.BOS MSP.fwdarw.BOS UA111 same as for the outbound
                         MSP.fwdarw.BOS UA222 UA faring-market
    Slice 2: NW MSP.fwdarw.BOS MSP.fwdarw.BOS NW333 same as for the outbound
                         MSP.fwdarw.BOS NW444 NW faring-market

    TABLE 20
    Priceable-Unit  Slice-1                          Slice-2
    Number and Type Faring-Atom        Slice-1 Fare  Faring-Atom        Slice-2
     Fare
     1 Round-trip   BOS .fwdarw. MSP UA100 RT "Q"        MSP .fwdarw. BOS UA111
     RT "Q"
     2 Round-trip   BOS .fwdarw. MSP UA100 RT "M14"      MSP .fwdarw. BOS UA111
     RT "M14"
     3 Round-trip   BOS .fwdarw. MSP UA100 RT "Q"        MSP .fwdarw. BOS UA222
     RT "Q"
     4 Round-trip   BOS .fwdarw. MSP UA100 RT "M14"      MSP .fwdarw. BOS UA222
     RT "M14"
     5 Round-trip   BOS .fwdarw. MSP UA200 RT "Q"        MSP .fwdarw. BOS UA111
     RT "Q"
     6 Round-trip   BOS .fwdarw. MSP UA200 RT "M14"      MSP .fwdarw. BOS UA111
     RT "M14"
     7 Round-trip   BOS .fwdarw. MSP UA200 RT "Q"        MSP .fwdarw. BOS UA222
     RT "Q"
     8 Round-trip   BOS .fwdarw. MSP UA200 RT "M14"      MSP .fwdarw. BOS UA222
     RT "M14"
     9 Round-trip   BOS .fwdarw. MSP NW300 RT "HE7NR"    MSP .fwdarw. BOS NW333
     RT "HE7"
    10 Round-trip   BOS .fwdarw. MSP NW300 RT "Q7NR"     MSP .fwdarw. BOS NW333
     RT "Q7NR"
    11 Round-trip   BOS .fwdarw. MSP NW300 RT "Q7NR"     MSP .fwdarw. BOS NW444
     RT "Q7NR"
    12 Round-trip   BOS .fwdarw. MSP NW400 RT "HE7NR"    MSP .fwdarw. BOS NW333
     RT "HE7"
    13 Round-trip   BOS .fwdarw. MSP NW400 RT "Q7NR"     MSP .fwdarw. BOS NW333
     RT "Q7NR"
    14 Round-trip   BOS .fwdarw. MSP NW400 RT "HE7NR"    MSP .fwdarw. BOS NW444
     RT "HE7"
    15 One-way      BOS .fwdarw. MSP NW400 RT "Q7NR"     MSP .fwdarw. BOS NW444
     RT "Q7NR"
    16 One-way      BOS .fwdarw. MSP UA100 OW "Y"
    17 One-way      BOS .fwdarw. MSP UA200 OW "Y"
    18 One-way      BOS .fwdarw. MSP NW300 OW "F"
    19 One-way      BOS .fwdarw. MSP NW400 OW "F"
    20 One-way                                       MSP .fwdarw. BOS UA111 OW
     "Y"
    21 One-way                                       MSP .fwdarw. BOS UA222 OW
     "Y"
    22 One-way                                       MSP .fwdarw. BOS NW333 OW
     "F"
    23 One-way                                       MSP .fwdarw. BOS NW444 OW
     "F"

    TABLE 21
      Label   Slice-1            Slice-2            Priceable-
     Number   Faring-Atom Options Faring-Atom Options Unit-Core Options
        1     BOS .fwdarw. MSP UA100 MSP .fwdarw. BOS UA111 1: RT "Q", 2: RT
     "Q"
              BOS .fwdarw. MSP UA200 MSP .fwdarw. BOS UA222 1: RT "M14", 2: RT
     "M14"
        2     BOS .fwdarw. MSP NW300 MSP .fwdarw. BOS NW333 1: RT "Q7NR", 2: RT
     "Q7NR"
              BOS .fwdarw. MSP NW400 MSP .fwdarw. BOS NW444
        3     BOS .fwdarw. MSP NW300 MSP .fwdarw. BOS NW333 1: RT "HE7", 2: RT
     "HE7"
        4     BOS .fwdarw. MSP NW400 MSP .fwdarw. BOS NW333 1: RT "HE7", 2: RT
     "HE7"
                                 MSP .fwdarw. BOS NW444
        5     BOS .fwdarw. MSP UA100                    1: OW "Y"
              BOS .fwdarw. MSP UA200
        6     BOS .fwdarw. MSP NW300                    1: OW "F"
              BOS .fwdarw. MSP NW400
        7                        MSP .fwdarw. BOS UA111 2: OW "Y"
                                 MSP .fwdarw. BOS UA222
        8                        MSP .fwdarw. BOS NW333 2: OW "F"
                                 MSP .fwdarw. BOS NW444

    TABLE 22
    partition-fare-components-into-sets(faring-market)
        //
        // Partition fare-components into sets based on fare and combinability
     record-2.
        //
        Let fare-component-sets = {}
        For fare-component in faring-market.fare-components
          Let fare = fare-component.fare
          Let combinability-record-2 = fare-component.combinability-record-2
          Let previous-set = nil
          For test-set in fare-component-sets
            Let test-fare-component = first(test-set)
            If ((fare = test-fare-component.fare) and
              (combinability-record-2 =
     test-fare-component.combinability-record-2))
              previous-set = test-set
          If (previous-set = nil)
            fare-component-sets += list(fare-component)
          Else
            previous-set += fare-component
        return(fare-component-sets)
    create-PUs-in-markets2(faring-market1, faring-market2, existing-PU-labels,
     PU-type, environmental-information)
        Let fare-component-sets1 =
     partition-fare-components-into-sets(faring-market1)
        Let fare-component-sets2 =
     partition-fare-components-into-sets(faring-market2.)
        Let PU-labels = existing-PU-labels
        For fare-components1 in fare-component-sets1
          For fare-components2 in fare-component-sets2
            Let fare1 = first(fare-components1).fare
            Let fare2 = first(fare-components2).fare
            Let combinability-record-2-1 =
     first(fare-components1).combinability-record-2
            Let combinability-record-2-2 =
     first(fare-components2).combinability-record-2
            // Check fare combinability requirements, by applying each fares's
     combinabilty
            // record-2 to all the other fares within the priceable-unit.
            If ((combinability-record-2-1 = nil or
              apply-combinability-record-2(combinability-record-2-1, fare2,
     PU-type) = pass) and
              (combinability-record-2-2 = nil or
              apply-combinability-record-2(combinability-record-2-2, fare1,
     PU-type) = pass))
              PU-labels = create-PUs-from-fare-components(list(faring-market1,
     faring-market2),
                               list(fare1, fare2),
                               list(fare-components1, fare-components2),
                               PU-labels, environmental-information)
        return(PU-labels)

    TABLE 23
    get-OR-AND-OR(faring-markets, fare-component-sets,
     environmental-information)
        Let size = length(faring-markets)
        If(size = 1)
          return(get-OR-AND-OR-1(faring-markets, fare-component-sets,
     environmental-information)
        Else If (size = 2)
          return(get-OR-AND-OR-2(faring-markets, fare-component-sets,
     environmental-information)
        Else
          return(get-OR-AND-OR-3+(faring-markets, fare-component-sets,
     environmental-information)

    TABLE 24
    apply-deferred-record-2s(fare-components, environmental-information)
        Let faring-atoms = {}
        Let fares = {}
        For fare-component in fare-components
          fares += fare-component.fare
          faring-atoms += fare-component.faring-atom
        For fare-component in fare-components
          For record-2 in fare-component.deferred-record-2s
            If (apply-record-2-PU(record-2, fares, faring-atoms,
                               fare-component.faring-atom,
                               environmental-information)
                <> pass
              return(fail)
        return(pass)

    TABLE 25
    partition-fare-components-by-surcharges(fare-components)
    Let partitions = {}
    For fare-component in fare-components
        Let found-partition = false
        Let surcharges = fare-component.surcharges
        For partition in partitions
          If (first(partition).surcharges surcharges)
            found-partition = true
            partition += fare-component
        If (found-partition = false)
          partitions += list(fare-component)
    return(partitions)

    TABLE 26
    get-OR-AND-OR-1(faring-markets, fare-component-sets,
     environmental-information)
        Let valid-fare-components = {}
        For fare-component in first(fare-component-sets)
          If (apply-deferred-record-2s(list(fare-component),
     environmental-information)
            valid-fare-components += fare-component
        Let OR-AND-OR = {}
        For OR in
     partition-fare-components-by-surcharges(valid-fare-components)
          Let AND-OR = list(OR)
          OR-AND-OR += AND-OR
        return(OR-AND-OR)

        TABLE 27
        get-OR-AND-OR-2(faring-markets, fare-component-sets,
     environmental-information)
            Let OR-AND-OR {}
            Subroutine find-AND-OR(surcharges1, fare-component-set2)
                //
                // Return any AND-OR from OR-AND-OR that has fare-components
     with surcharges surcharges1 in its
                // first set of fare-components, and has fare-component-set as
     its second set of fare-components.
                //
                For AND-OR in OR-AND-OR
                    If (first(first(AND-OR)).surcharges = surcharges1 and
     second(AND-OR) = fare-component-set2)
                       return(AND-OR)
                return(nil)
            Subroutine add-uniform-cross-product(fare-component-set1,
     fare-component-set2)
                //
                // Add the priceable-units that can be had by selecting one
     element from fare-component-set1 and
                // one element from fare-component-set2. Both sets are uniform
     with respect to surcharges.
                //
                Let AND-OR = find-AND-OR(first(fare-component-set1).surcharges,
     fare-component-set2)
                If (AND-OR = nil)
                    OR-AND-OR += list(fare-component-set1, fare-component-set2)
                Else
                    first(AND-OR) = append(first(AND-OR), fare-component-set1)
            Subroutine add-cross-product(fare-component-set1.
     fare-component-set2)
                //
                // Add the priceable-units that can be had by selecting one
     element from fare-component-set1 and
                // one element from fare-component-set2.
                //
                Let uniform-fare-component-sets1 =
     partition-fare-components-by-surcharges(fare-component-set1)
                Let uniform-fare-component-sets2 =
     partition-fare-components-by-surcharges(fare-component-set2)
                For uniform-fare-component-set1 in uniform-fare-component-sets1
                    For uniform-fare-component-set2 in
     uniform-fare-component-sets2
                       add-uniform-cross-product(uniform-fare-component-set1,
     uniform-fare-component-set2)
            Subroutine enumerate-priceable-units(fare-component-set1,
     fare-component-set2)
                //
                // Enumerate priceable-units by selecting one fare-component
     from each set. Test deferred record-2s,
                // and if they pass, add the resulting priceable-unit to the
     OR-AND-OR representation.
                //
                For fare-component1 in fare-component-set1
                    Let valid-fare-components2 = {}
                    For fare-component in fare-component-set2
                       If (apply-deferred-record-2s(list(fare-component1,
     fare-component2), environmental-information))
                           valid-fare-components2 += fare-component2
                    If (valid-fare-components2 <>({})
                       add-cross-product(list(fare-component1),
     valid-fare-components2)
            Let fare-component-set1-with-rules = {}
            Let fare-component-set1-without-rules = {}
            Let fare-component-set2-with-rules = {}
            Let fare-component-set2-without-rules = {}
    For fare-component1 in first (fare-component-sets)
                       If (fare-oomponent1.deferred-record-2s = nil)
                               fare-component-set1-without-rules +=
     fare-component1
                       Else
                               fare-component-set1-with-rules +=
     fare-component1
                For fare-component in second(fare-component-sets)
                       If (fare-component.deferred-record-2s = nil)
                               fare-component-set2-without-rules +=
     fare-component2
                       Else
                               fare-component-set2-with-rules +=
     fare-component2
                // There is no need to enumerate combinations of
     fare-components that have no deferred rules.
                add-cross-product(fare-component-set1-without-rules,
     fare-component-set2-without-rules)
                // For the remainder of fare-components, though, explicit
     enumeration is necessary.
                enumerate-priceable-units(fare-component-set1-with-rules,
     fare-component-set2-without-rules)
                enumerate-priceable-units(fare-component-set1,
     fare-component-set2-with-rules)
                return(OR-AND-OR)

    TABLE 28
    reevaluate-deferred-record-2s(faring-markets, fare-component-set,
     environmental-information)
        set-time-bounds(faring-markets)
        Let fare-components = {}
        For fare-component in fare-component-set
            Let result = pass
            Let deferred-record-2s = {}
            For record-2 in fare-component.deferred-record-2s
                Let record-2-result, record-2-surcharges =
                    apply-record-2-FC(record-2, fare-component.faring-atom,
     environmental-information)
                If (record-2-result = pass)
                    fare-component.surcharges += record-2-surcharges
                Else If (record-2-result = defer)
                    deferred-record-2s += record-2
                Else
                    result = fail
            If (result = pass)
                fare-component.deferred-record-2s = deferred-record-2s
                fare-components += fare-component
        return(fare-components)

    TABLE 29
    get-OR-AND-OR-3+(faring-markets, fare-component-sets,
     environmental-information)
        Let OR-AND-OR = { {} }
        For fare-component-set in fare-component-sets
            Let valid-fare-components =
     reevaluate-deferred-record-2s(faring-markets, fare-component-set,
     environmental-information)
            Let new-OR-AND-OR = {}
            For OR in
     partition-fare-components-by-surcharges(valid-fare-components)
                For previous-AND-OR in OR-AND-OR
                    new-OR-AND-OR += postpend(previous-AND-OR, OR)
            OR-AND-OR = new-OR-AND-OR
        return(OR-AND-OR)

    TABLE 30
     Multi-Slice Single-Slice
    Slice Itinerary                           Division
     PU-Labels   PU-Labels
      1   1.1 BOS.fwdarw.MSP UA123            1.1.1 BOS.fwdarw.MSP
     {A-123}     {}
                                                                         {F-13}
          {}
                                                                         {}
          {I-1}
      1   1.2 BOS.fwdarw.CHI NW315 CHI_MSP UA739 1.2.1 BOS.fwdarw.MSP;
     CHI.fwdarw.MSP {B-13 C-12} {}
                                                                         {B-13}
          {H-1}
                                                                         {C-12}
          {G-1}
                                                                         {}
          {G-1 H-1}
      1   1.3 BOS.fwdarw.MSP CO450            1.3.1 BOS.fwdarw.MSP       {}
          {J-1}
      2   2.1 MSP.fwdarw.MIA UA901            2.1.1 MSP.fwdarw.MIA
     {A-123}     {}
                                                                         {}
          {K-2}
      2   2.2 MSP.fwdarw.CHI UA623 CHI_MIA UA841 2.2.1 MSP.fwdarw.MIA
     {A-123}     {}
                                                                         {}
          {K-2}
                                              2.2.2 MSP.fwdarw.CHI;
     CHI.fwdarw.MIA {C-12 D-23} {}
                                                                         {C-12}
          {M-2}
                                                                         {D-23}
          {L-2}
                                                                         {}
          {L-2 M-2}
      2   2.3 MSP.fwdarw.MIA FL207            2.3.1 MSP.fwdarw.MIA       {E-23}
          {}
      3   3.1 MIA.fwdarw.BOS UA112            3.1.1 MIA.fwdarw.BOS
     {A-123}     {}
      3   3.2 MIA.fwdarw.CHI UA487 CHI.fwdarw.BOS NW316 3.2.1 MIA.fwdarw.CHI;
     CHI.fwdarw.BOS {D-23 B-13} {}
                                                                         {D-23}
          {O-3}
                                                                         {B-13}
          {N-3}
                                                                         {}
          {N-3 O-3}
      3   3.3 MIA.fwdarw.MSP FL208 MSP.fwdarw.BOS UA558 3.3.1 MIA.fwdarw.MSP;
     MSP.fwdarw.BOS {E23 F13}   {}
                                                                         {E23}
          {P-3}

    TABLE 31
    Name    Faring-Markets                                        Comment
    A-123   1: UA BOS.fwdarw.MSP 2: UA MSP.fwdarw.MIA 3: UA MIA.fwdarw.BOS
     3-Component Circle Trip
    B-13    1: NW BOS.fwdarw.CHI                   3: NW CHI.fwdarw.BOS Round
     Trip
    C-12    1: UA CHI.fwdarw.MSP 2: UA CHI.fwdarw.MSP                   Round
     Trip
    D-23                      2: UA CHI.fwdarw.MIA 3: UA MIA.fwdarw.CHI Round
     Trip
    E-23                      2: FL MSP.fwdarw.MIA 3: FL MIA.fwdarw.MSP Round
     Trip
    F-13    1: UA BOS.fwdarw.MSP                   3: UA MSP.fwdarw.BOS Round
     Trip
    G-1     1: NW BOS_CHI                                         One Way
    H-1     1: UA CHI.fwdarw.MSP                                     One Way
    I-1     1: UA BOS.fwdarw.MSP                                     One Way
    J-1     1: CO BOS.fwdarw.MSP                                     One Way
    K-2                       2: UA MSP.fwdarw.MIA                   One Way
    L-2                       2: UA MSP.fwdarw.CHI                   One Way
    M-2                       2: UA CHI.fwdarw.MIA                   One Way
    N-3                                         3: UA MIA.fwdarw.CHI One Way
    O-3                                         3: NW CHI.fwdarw.BOS One Way
    P-3                                         3: UA MSP.fwdarw.BOS One Way

    TABLE 32
                                           Single-
          Multi-Slice          Itin- Divi- Slice     Backward
    Slice PU-Labels            erary sion  PU-Labels Projection
      1   1.1 {A-123}           1.1  1.1.1 {}        {}
      1   1.2 {F-13}            1.1  1.1.1 {}        {}
      1   1.3 {}                1.1  1.1.1 {I-1}     {}
                                1.2  1.2.1 {G-1 H-1}
                                1.3  1.3.1 {J-1}
      1   1.4 {B-13 C-12}       1.2  1.2.1 {}        {}
      1   1.5 {B-13}            1.2  1.2.1 {H-1}     {}
      1   1.6 {C-12}            1.2  1.2.1 {G-1}     {}
      2   2.1 {A-123}           2.1  2.1.1 {}        {A-123}
                                2.2  2.2.1 {}
      2   2.2 {}                2.1  2.1.1 {K-2}     {}
                                2.2  2.2.2 {L-2
                                           M-2}
      2   2.3 {C-12 D-23}       2.2  2.2.2 {}        {C-12}
      2   2.4 {C-12}            2.2  2.2.2 {M-2}     {C-12}
      2   2.5 {D-23}            2.2  2.2.2 {L-2}     {}
      2   2.6 {E-23}            2.3  2.3.1 {}        {}
      3   3.1 {A-123}           3.1  3.1.1 {}        {A-123}
      3   3.2 {D-23 B-13}       3.2  3.2.1 {}        {D-23 B-13}
      3   3.3 {D-23}            3.2  3.2.1 {O-3}     {D-23}
      3   3.4 {B-13}            3.2  3.2.1 {N-3}     {B-13}
      3   3.5 {}                3.2  3.2.1 {N-3 O-3} {}
      3   3.6 {E23 F13}         3.3  3.3.1 {}        {E-23 F-13}
      3   3.7 {E23}             3.3  3.3.1 {P-3}     {E-23}

    TABLE 33
                                                      Backward-
                          Next-Slice  Backward-Link   Link Open-
    Slice Open-Label-Set  Projection  Slice-Label-Set Label-Set
      0   0.1 {}          {}
      1   1.1 {A-123}     {A-123}     1.1 {A-123}     0.1 {}
      1   1.2 {F-13}      {}          1.2 {F-13}      0.1 {}
      1   1.3 {}          {}          1.3 {}          0.1 {}
      1   1.4 {B-13 C-12} {C-12}      1.4 {B-13 C-12} 0.1 {}
      1   1.5 {B-13}      {}          1.5 {B-13}      0.1 {}
      1   1.6 {C-12}      {C-12}      1.6 {C-12}      0.1 {}
      2   2.1 {A-123}     {A-123}     2.1 {A-123}     1.1 {A-123}
      2   2.2 {}          {}          2.2 {}          1.1 {}
      2   2.3 {D-23}      {D-23}      2.3 {C-12 D-23} 1.6 {C-12}
                                      2.5 {D-23}      1.3 {}
      2   2.4 {E-23}      {E-23}      2.6 {E-23}      1.3 {}
      2   2.5 {D-23 F-13} {D-23 F-13} 2.5 {D-23}      1.2 {F-13}
      2   2.6 {E-23 F-13} {E-23 F-13} 2.6 {E-23}      1.2 {F-13}
      2   2.7 {F-13}      {F-13}      2.2 {}          1.2 {F-13}
      2   2.8 {D-23 B-13} {D-23 B-13} 2.3 {C-12 D-23} 1.4 {B-13
                                                      C-12}
                                      2.5 {D-23}      1.5 {B-13}
      2   2.9 {E-23 B-13} {E-23 B-13} 2.6 {E-23}      1.5 {B-13}
      2   2.10 {B-13}     {B-13}      2.4 {C-12}      1.4 {B-13
                                                      C-12}
                                      2.2 {}          1.5 {B-13}
      3   3.1 {}          {}          3.1 {A-123}     2.1 {A-123}
                                      3.5 {}          2.2 {}
                                      3.3 {D-23}      2.3 {D-23}
                                      3.7 {E-23}      2.4 {E-23}
                                      3.6 {E-23 F-13} 2.6 {E-23
                                                      F-13}
                                      3.2 {D-23 B-13} 2.8 {D-23
                                                      B-13}
                                      3.4 {B-13}      2.10 {B-13}