Pricing graph representation for sets of pricing solutions 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 computer program product residing on a computer readable medium for determining a set of fares for a set of itineraries comprising instructions for causing a computer to:

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

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

apply rules to the faring atoms to produce fare components;

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

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

construct priceable units from the fare components; and

link itineraries and priceable units into pricing solutions.

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

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

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

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

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

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

group faring atoms by faring markets; and

partition itineraries into divisions of faring atoms.

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

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

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

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

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

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

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

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

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

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

constructing priceable units from the fare components; and

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

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

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

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

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

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

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

grouping faring atoms by faring markets; and

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

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

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

17. A method for determining pricing solutions comprises:

retrieving itinerary sets for all slices of a journey;

decomposing said itinerary sets into faring atoms;

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

constructing priceable unit data structures from the faring components; and

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

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

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

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

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

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

grouping faring atoms by faring markets; and

partitioning itineraries into divisions of faring atoms.

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

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

22. A computer system for determining pricing solutions comprises:

a computer; and

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

retrieve itinerary sets for all slices of a journey;

decompose said itinerary sets into faring atoms;

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

construct priceable unit data structures from the faring components; and

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

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

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

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

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

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

group faring atoms by faring markets; and

partition itineraries into divisions of faring atoms.

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

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

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 (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, Galileo, Amadeus and WorldSpan. 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 computer program product residing on a computer readable medium for determining a set of fares for a set of itineraries includes instructions for causing a computer to retrieve itinerary sets for at least one slice of a journey and parse retrieved itinerary sets into faring atoms that correspond to one or more travel unit segments spanned by a single fare, wherein faring atoms are shared across itineraries. The product also includes instructions to cause the computer to apply rules to the faring atoms to produce fare components and construct from the fare components a set of fares that are valid for and associated with the itinerary sets.

According to a further aspect of the invention a method for determining a set of fares for a set of itineraries includes retrieving itinerary sets for at least one slice of a journey, parsing retrieved itinerary sets into faring atoms that correspond to one or more travel unit segments spanned by a single fare and applying rules to the faring atoms to produce fare components. The method also includes constructing from the fare components a set of fares that are valid for and associated with the itinerary sets.

According to a further aspect of the invention, a method for determining pricing solutions includes retrieving itinerary sets for all slices of a journey and decomposing said itinerary sets into faring atoms. The method also includes applying rules to said faring atoms to produce valid faring atoms that are grouped into faring components, constructing priceable unit data structures from the faring components and linking itineraries and priceable units into a data structure that represents pricing solutions.

According to a still further aspect of the invention, a computer system for determining pricing solutions includes a computer and a computer readable medium storing a computer program. The computer program has instructions that causes the computer to retrieve itinerary sets for all slices of a journey, decompose said itinerary sets into faring atoms, apply rules to the faring atoms to produce valid faring atoms that are grouped into faring components, construct priceable unit data structures from the faring components, and link itineraries and priceable units into a data structure that represents pricing solutions.

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-3c (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 tile databases 20a-20b to the server 12. The network 22 can be any local or wide area networks or an arrangement such as the Internet.

The clients 30a-30c are preferably smart clients. That is, using client 30c as all 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 solution 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. deMarckeni 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 call 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, DFW_LAX UA103 UA BOS-LAX RT
     "QE7NR"
                    Slice 2: LAX.fwdarw.BOS UA515             UA BOS-LAX RT
     "QE7NR"
           5        Slice 1: BOS.fwdarw.DFW UA100, DFW_LAX UA103 UA BOS-LAX OW
     "Y"
                    Slice 2: LAX.fwdarw.BOS UA515             UA BOS-LAX OW "Y"
           6        Slice 1: BOS.fwdarw.DFW UA100, DFW_LAX UA103 UA BOS-LAX OW
     "Y"
                    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
     C0716
     28   Itin.                    Slice 2: BOS.fwdarw.DFW AA67, DFW.fwdarw.LAX
     C0717
     29   Itin.                    Slice 2: BOS.fwdarw.DFW AA67, DFW.fwdarw.LAX
     C0719
     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 DL18O
     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 PU-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, oonstructing 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 pseudo-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.origiin-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 faring-atoms     Slice 2 NW MSP_faring-atoms
    ORD_MSP NW220 12APR97 13:00         MSP_ORD NW301 15APR97 19:00
    ORD_MSP NW220 13APR97 13:00         MSP_ORD NW577 16APR97 12:00
    ORD_MSP NW220 14APR97 13:00         MSP_ORD NW301 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-pemitted-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        Faraing-Atoms     Fares
    Slice 1: UA       BOS.fwdarw.MSP UA10O 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 UA111 same as for the outbound
    MSP.fwdarw.BOS    MSP.fwdarw.BOS UA222 UA faring-market
    Slice 2: NW       MSP.fwdarw.BOS NW333 same as for the outbound
    MSP.fwdarw.BOS    MSP.fwdarw.BOS NW444 NW faring-market

    TABLE 20
    Priceable-Unit
    Number and    Slice-1 Faring-   Slice-1       Slice-2           Slice-2
    Type          Atom              Fare          Faring-Atom       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 Faring-Atom Slice-2 Faring-Atom Priceable-Unit-Core
    Number  Options           Options           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))
                    previsous-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-set2 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-component2 in fare-component-set2
                    If (apply-deferred-record-2s(list(fare-component1,
     fare-component2), environmental-information))
                       valid-fare-components2 += fare-component2
                If (valid-fare-component2 < > { })
                    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-component1.deferred-record-2s = nil)
                       fare-component-set1-without-rules += fare-component1
                Else
                       fare-component-set1-with-rules += fare-component1
        For fare-component2 in second(fare-component-sets)
                If (fare-component2.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-wihtout-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,
     enviromental-information)
        Let OR-AND-OR = {0}
        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-CHI UA623 CHI_MIA UA841     2.2.1 MSP.fwdarw.MIA
     {A-123}     { }
                                                                         { }
          {K-2}
                                              2.2.2 MSP-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-BOS UA558 3.3.1 MIA.fwdarw.MSP; MSP-BOS
     {E23 F13}   { }
                                                                         {E23}
          {P-3}

    TABLE 31
    Name                   Faring.fwdarw.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
          Multi-Slice     Itin-           Single-Slice Backward
    Slice PU-Labels       erary Division  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
                            Next-Slice    Backward-Link     Backward-Link
    Slice Open-Label-Set    Projection    Slice-Label-Set   Open-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}