# US 8,571,903 B1 · Pricing graph representation for sets of pricing solutions for travel planning system

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,571,903 B1
- Document ID: US8571903B1
- Status: Granted
- Kind: B1
- Application number: 10/609,032
- Filed: 2003-06-27
- Granted: 2013-10-29
- Earliest claimed: 1998-07-02
- Assignees: Google Inc.
- Applicants: Carl G. DeMarcken
- Inventors: Carl G. DeMarcken
- Web page: https://patentgrep.com/patent/US8571903B1

## CPC

- G06Q 10/02: Reservations, e.g. for tickets, services or events
- G06Q 10/025: {Coordination of plural reservations, e.g. plural trip segments, transportation combined with accommodation}
- G06Q 10/0283: {for travel seating}
- G06Q 10/04: Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" (market predictions or forecasting for commercial activities G06Q30/0202)
- G06Q 30/0283: Price estimation or determination
- G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR

## 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

### Claim 1

A computer program product residing on a non-transitory computer readable storage medium for determining fares for sets of itineraries, the computer program product comprising instructions for causing one or more computers to:
decompose the sets of itineraries into faring atoms, with a faring atom corresponding to a sequence of flight segments associated with a single fare;
retrieve fares, with fares comprising a carrier, a market, fare class, and a price;
retrieve fare rules for the faring atoms from a fare rules database;
retrieve routings for a fare;
for a retrieved fare:
apply the retrieved fare rules to a faring atom, to determine if the retrieved fare rules permit a fare component to be constructed, and if a fare component is permitted to be constructed, based on applying the retrieved fare rules:
produce the fare component as a combination of the faring atom and the retrieved fare; and
compute travel options comprising prices for at least some of the sequence of flight segments, using the fare component.

### Claim 2 (depends on 1)

The computer program product of claim 1 wherein the faring atoms are data structures that comprise:
a storage space to store results of applying the fare rules to the faring atoms, with the result being one of pass, fail, no match, unavailable or defer.

### Claim 3 (depends on 1)

The computer program product of claim 1 wherein the faring atoms are data structures and, for a particular one of the faring atoms, the data structure includes a list of legs and departure times and dates for the legs, a faring-market that the particular one of the faring atoms is in, and cached results that store results of applying fare rule records to the particular one of the faring atoms, with the result being one of pass, fail, no match, unavailable or defer.

### Claim 4 (depends on 2)

The computer program product of claim 2 wherein the flight sequences are represented as a set of lists of itineraries.

### Claim 5 (depends on 3)

The computer program product of claim 3 wherein the instructions for causing one or more computers to compute prices comprise instructions for causing one or more computers to:
for applying a fare rule to a faring atom, determine if the faring atom has cached results for the fare rule, and if it has cached results,
retrieve the cached results for the fare rule from the faring atom to evaluate whether the faring atom can construct a different fare component.

### Claim 6 (depends on 5)

The computer program product of claim 5 wherein the instructions to retrieve the cached results retrieves the result of applying fare rules to the faring atom and avoids repeating of applying fare rules to the faring atom for those fare components common to multiple trips.

### Claim 7 (depends on 1)

The computer program product of claim 1 wherein instructions for causing one or more computers to compute prices for more than one of the flight segments in a sequence of flight segments cause one or more computers to share computational work among more than one flight segment.

### Claim 8 (depends on 1)

The computer program product of claim 1 further comprising instructions to produce a representation of fares useable with flight segments of the itinerary sets using a structure that shares flight segments and fares across multiple trips.

### Claim 9

A computer implemented method for determining fares for sets of itineraries, the method comprising:
decomposing, by one or more computers, the sets of itineraries into faring atoms, with a faring atom corresponding to a sequence of flight segments associated with a single fare;
retrieving fares, with fares comprising a carrier, a market, fare class, and a price;
retrieving fare rules for the faring atoms from a fare rules database;
retrieving routings for a fare;
for a retrieved fare:
applying, by one or more computers, the retrieved fare rules to a faring atom, to determine if the retrieved fare rules permit a fare component to be constructed, and if a fare component is permitted to be constructed, based on applying the retrieved fare rules:
produce the fare component as a combination of the faring atom and the retrieved fare; and
compute, by one or more computers, travel options comprising prices for at least some of the sequence of flight segments, using the fare component.

### Claim 10 (depends on 9)

The method of claim 9 wherein the faring atoms are data structures that comprise a storage space to store results of applying the fare rules to the faring atoms, with the result being one of pass, fail, no match, unavailable or defer.

### Claim 11 (depends on 9)

The method of claim 9 wherein faring atoms are data structures and for a particular one of the faring atoms, the data structure includes a list of legs and departure times and dates for the legs, a faring market that the particular faring atom is in, and cached results that store results of applying fare rule records to the particular faring atom, with the result being one of pass, fail, no match, unavailable or defer.

### Claim 12 (depends on 10)

The method of claim 10 wherein trips are represented as a set of lists of itineraries.

### Claim 13 (depends on 11)

The method of claim 11 wherein computing prices comprises:
for applying a fare rule to a faring atom, determining if the faring atom has cached results, and if it has cached results,
retrieving the cached results for the fare rule from the faring atom to evaluate whether the faring atom can construct a different fare component.

### Claim 14 (depends on 13)

The method of claim 13 wherein retrieving the cached results retrieves the result of applying fare rules to the faring atom and avoids repeating of applying fare rules to the faring atom for those fare components common to multiple trips.

### Claim 15 (depends on 9)

The method of claim 9 wherein computing prices for at least some of the sequence of flight segments comprises sharing computational work among more than one flight segment.

### Claim 16 (depends on 9)

The method of claim 9 further comprising:
producing a representation of fares useable with flight segments of multiple trips using a structure that shares flight segments and fares across the multiple trips.

### Claim 17

A computer system for travel planning comprising:
a processor;
a memory in which resides a computer program product for determining fares for sets of itineraries, the computer program product comprising instructions for causing a computer to:
decompose the sets of itineraries into faring atoms, with a faring atom corresponding to a sequence of flight segments associated with a single fare;
retrieve fares, with fares comprising a carrier, a market, fare class, and a price;
retrieve fare rules for the faring atoms from a fare rules database;
retrieve routings for a fare;
for a retrieved fare:
apply the retrieved fare rules to a faring atom, to determine if the retrieved fare rules permit a fare component to be constructed, and if a fare component is permitted to be constructed, based on applying the retrieved fare rules:
produce the fare component as a combination of the faring atom and the retrieved fare; and
compute travel options comprising prices for at least some of the sequence of flight segments, using the fare component.

### Claim 18 (depends on 17)

The system of claim 17 wherein the faring atoms are data structures that comprise a storage space to store results of applying the fare rules to the faring atoms, with the result being one of pass, fail, no match, unavailable or defer.

### Claim 19 (depends on 17)

The system of claim 17 wherein faring atoms are data structures and for a particular one of the faring atoms, the data structure includes a list of legs and departure times and dates for the legs, a faring market that the particular one of the faring atoms is in, and cached results that store results of applying fare rule records to the particular one of the faring atoms, with the result being one of pass, fail, no match, unavailable or defer.

### Claim 20 (depends on 17)

The system of claim 17 wherein the computer program product comprises instructions for causing one or more computers to link fares and fare components.

### Claim 21 (depends on 19)

The system of claim 19 wherein the computer program product comprises instructions for causing one or more computers to:
for applying a fare rule to a faring atom, determine if the faring atom has cached results, and if it has cached results,
retrieve the cached results for the fare rule from the faring atom to evaluate whether the faring atom can construct a different fare component.

### Claim 22 (depends on 17)

The system of claim 17 wherein the instructions to retrieve fare rule results avoids repeated computation of prices for those fare components common to multiple trips.

### Claim 23

A computer-implemented method for determining a set of fares for a set of itineraries, the method comprising:
retrieving by operation of one or more computers, from one or more databases, itinerary sets of sequences of flight segments for at least one slice of a journey; and, for each itinerary set of sequences of flight segments:
computing prices by one or more computers for more than one of the flight segments in the set of sequences of flight segments by one or more computers;
parsing retrieved itinerary sets into one or more travel unit segments associated with a single fare, with a fare comprising a carrier, a market, a fare class, and a price;
applying fare rules to the one or more travel unit segments to produce fare components;
storing information associated with applying of the fare rules to the one or more travel unit segments, the information comprising a result status of applying the rule with the result status being pass, fail or defer status in a portion of the one or more travel unit segments, and the information to evaluate subsequent application of those fare rules to fare component; and
constructing by operation of one or more computers, from the fare components, travel options comprising a set of fares that are valid for and associated with the itinerary sets.

### Claim 24 (depends on 23)

The method of claim 23 wherein the one or more travel unit segments are faring atoms that are represented as data structures that are shared across itineraries.

### Claim 25 (depends on 23)

The method of claim 23 wherein computing prices comprises retrieving fares for those fare components of the set of sequences of flight segments that are shared across trips.

### Claim 26 (depends on 23)

The method of claim 23 wherein a set of trips is represented as a set of lists of itineraries.

### Claim 27 (depends on 23)

The method of claim 23 wherein applying a fare rule to a travel unit segment comprises:
determining if the travel unit segment has cached results for the fare rule; and if it has cached results,
retrieving the cached results for the fare rule from the travel unit segment to evaluate whether the travel unit segment can construct a different fare component.

### Claim 28 (depends on 27)

The method of claim 27 further comprising producing a representation of fares useable with flight segments of multiple trips, the representation including flight segments and fares that are shared across the multiple trips.

### Claim 29

A computer program product residing on a non-transitory computer readable storage medium for determining a set of fares for a set of itineraries, the computer readable storage medium comprising instructions for causing a computer to:
retrieve, from one or more databases, itinerary sets of sequences of flight segments for at least one slice of a journey; and
compute prices for more than one of the flight segments in the set of sequences of flight segments by instructions to:
parse retrieved itinerary sets into one or more travel unit segments spanned by a single fare with a fare comprising a carrier, a market, fare class, and a price;
apply fare rules to the one or more travel unit segments, to produce fare components;
store information associated with applying the fare rules to the one or more travel unit segments, the information comprising a result status of applying the rule with the result status being pass, fail or defer status in a portion of the one or more travel unit segments, and the information to evaluate subsequent application of those fare rules to fare components; and
construct, from the fare components, travel options comprising a set of fares that are valid for and associated with the itinerary sets.

### Claim 30 (depends on 29)

The computer program product of claim 29 wherein the one or more travel unit segments are faring atoms that are represented as data structures that are shared across itineraries.

### Claim 31 (depends on 29)

The computer program product of claim 29 wherein computing prices comprises instructions to retrieve fares for those fare components of the set of sequences of flight segments that are shared across trips.

### Claim 32 (depends on 29)

The computer program product of claim 29 wherein applying a fare rule to a travel unit segment comprises instructions to:
determine if the travel unit segment has cached results for the fare rule, and if it has cached results,
retrieve the cached results for the fare rule from the travel unit segment to evaluate whether the travel unit segment can construct a different fare component.

### Claim 33 (depends on 32)

The computer program product of claim 32, further comprising instructions to:
produce a representation of fares useable with flight segments of multiple trips, the representation including flight segments and fares that are shared across the multiple trips.

### Claim 34

A computer system for determining a set of fares for a set of itineraries comprising:
a computer; and
a computer readable medium storing a computer program that causes one or more computers to:
retrieve, from one or more databases, a set of sequences of flight segments for at least one slice of a journey; and
compute prices for more than one of the flight segments in the set of sequences of flight segments by instructions to:
parse retrieved itinerary sets into one or more travel unit segments associated with a single fare with a fare comprising a carrier, a market, fare class, and a price;
apply fare rules to the one or more travel unit segments to produce fare components;
store information associated with applying the fare rules to the one or more travel unit segments, the information comprising a result status of applying the rule with the result status being pass, fail or defer status in a portion of the one or more travel unit segments, and the information to evaluate subsequent application of those fare rules to fare components; and
construct, from the fare components, travel options comprising a set of fares that are valid for and associated with the itinerary sets.

### Claim 35 (depends on 34)

The computer system of claim 34 wherein the one or more travel unit segments are faring atoms that are represented as data structures that are shared across itineraries.

### Claim 36 (depends on 34)

The computer system of claim 34 wherein the instructions to compute prices comprises instructions to retrieve fares for those fare components of the set of sequences of flight segments that are shared across trips.

### Claim 37 (depends on 34)

The computer system of claim 34 wherein applying a fare rule to a travel unit segment comprises instructions to:
determine if the travel unit segment has cached results for the fare rule, and if it has cached results, retrieve the cached results for the fare rule from the travel unit segment to evaluate whether the travel unit segment can construct a different fare.

### Claim 38 (depends on 36)

The computer system of claim 36 further comprising instructions to produce a representation of fares useable with flight segments of the trips, the representation including flight segments and fares that are shared across the trips.

### Claim 39 (depends on 23)

The method of claim 23, wherein storing information associated with application of the fare rules stores the information into a fare component structure and the method further comprises:
checking a fare component for stored results of applying a fare rule to the fare component and if a stored result is found,
applying the stored result to the fare component.

### Claim 40 (depends on 29)

The computer program product of claim 29 wherein instructions to store information associated with application of the fare rules comprises storing the information into a fare component structure and the product further comprises instructions to:
check a fare component for stored results of applying a fare rule to the fare component and if a stored result is found,
apply the stored result to the fare component.

### Claim 41 (depends on 34)

The computer system of claim 34 wherein instructions to store information associated with application of the fare rules comprises storing the information into a fare component structure and the computer program further comprises instructions to:
check a fare component for stored results of applying a fare rule to the fare component and if a stored result is found,
apply the stored result to the fare component.