Virtual fare methods for a computerized airline seat inventory control system

• US 5,270,921 A
• Filed: 01/11/1991
• Issued: 12/14/1993
• Est. Priority Date: 12/19/1990
• Status: Expired due to Term

• Current Assignee: Accenture Global Services Limited (Accenture PLC)
• Original Assignee: Andersen Consulting LLP (Accenture PLC)
• Inventors: Hornick, Scot W.
• Primary Examiner(s): Envall, Jr., Roy N.
• Assistant Examiner(s): Shingala, Gita
• Application Number:
  US07/640,077
• Time in Patent Office: 1,068 Days
• Field of Search: 364/407, 364/401, 364/403
• US Class Current: 705/6
• CPC Class Codes: G06Q 10/02 Reservations, e.g. for tickets, services or events
• CPC Class Codes: G06Q 10/025 Coordination of plural reservations, e.g. plural trip segments, transportation combined with accommodation
• CPC Class Codes: G06Q 10/087 Inventory or stock management, e.g. order filling, procurement or balancing against orders

Abstract

An airline seat reservation system wherein seat reservations are controlled using, in part, a computerized seat inventory control system. The seat inventory control system, based on a concept termed Network-Based Expected Marginal Seat Revenue (EMSR), does not require the large number of variables required by the other network-based approaches, and it incorporates a probabilistic demand model without resorting to computationally intractable integer programming. The seat inventory control system uses iterative leg-based methods to control bookings in a flight network comprised of a plurality of itinerary/fare class combinations using a plurality of flight legs. When considering a particular flight leg, the total fare paid by a passenger using the leg is adjusted by taking into account an estimate of the displacement cost of the travel on the other legs of the itinerary to create a virtual fare. Expected marginal seat revenues (or more precisely, their current approximations) provide the displacement costs on the legs when computing virtual fares. Using these virtual fares, a leg-based optimization method is applied to the individual legs one-by-one to compute new approximations of the expected marginal seat revenues. This method is iterated until the expected marginal seat revenues concerge to their network-optimal values.

Claims

1. An airline seat reservation system, comprising:

(a) a programmed computer;

(b) data storage means, connected to the programmed computer, for storing a database describing a flight network and seat reservation requests, the flight network comprising a plurality of flight legs a, and itinerary p and fare class i combinations, each flight leg a having a residual seating capacity C_a, and each itinerary p and fare class i combination having a revenue yield fⁱ_p for a seat reserved therein;

(c) the programmed computer comprising seat assignment means for processing the database describing the flight network to assign seats in a flight leg a to one or more itinerary p and fare class i combinations, the seat assignment means comprising;

(1) means for calculating an initial expected marginal seat revenue (EMSR) λ

_a for all flight legs a;

(2) means for computing an unnested EMSR-prorated virtual fare vⁱ_p,a for every itinerary p and fare class i combination that contains a particular flight leg a having a nonzero residual seating capacity C_a so that;

##EQU20## (3) means for calculating a new EMSR λ

_a for the particular flight leg a based on the virtual fares vⁱ_p,a by applying Newton'"'"'s method to a seating capacity constraint for the particular flight leg a;

##EQU21## wherein Qⁱ _p is an inverse of a cumulative probability density function of demand for fare class i travel on itinerary p, thereby ensuring that a total number of seats assigned to the itinerary p and fare class i combinations are equal to the residual seating capacity of the particular flight leg a, wherein the virtual fares vⁱ_p,a are updated at each step of the Newton'"'"'s method since each step changes the EMSR λ

_a for the particular flight leg a;

(4) means for converging the EMSR λ

_a for the particular flight leg a;

(5) means for terminating the seat assignment means when the changes in the EMSR'"'"'s λ

_a '"'"'s for all flight legs a are insignificant;

(d) reservation terminal means, operatively connected to the programmed computer, for entering a seat reservation request for a particular itinerary p and fare class i combination; and

(e) the programmed computer comprising reservation means for receiving the seat reservation request for the particular itinerary p and fare class i combination from the reservation terminal means, for accepting the seat reservation request in accordance with a value selected from a group comprising at least one of the following;

a globally optimal set of EMSR'"'"'s λ

_a '"'"'s and the total number of seats assigned to the itinerary pa nd fare class i combinations for recording the seat reservation request in the database, and for transmitting an electronic status indication of the seat reservation request from the computer to the reservation terminal means.

2. The apparatus of claim 1, wherein the means for calculating further comprises means for performing a binary search when the EMSR λ

_a fails to converge with Newton'"'"'s method.

3. The apparatus of claim 1, wherein the means for terminating further comprises means for terminating the seat assignment means when the changes in EMSR'"'"'s λ

_a '"'"'s for all flight legs a are less than a tolerance value.

4. The apparatus of claim 1, wherein the reservation means further comprises means for accepting the seat reservation request when the total number of seats assigned to the itinerary p and fare class i combinations is not exceeded.

5. The apparatus of claim 1, wherein the reservation means further comprises means for accepting the seat reservation request when the seat reservation request would yield revenue greater than or equal to a sum of the EMSR'"'"'s λ

_a '"'"'s for all flight legs a in the itinerary p.

6. An airline seat reservation system, comprising:

(a) a programmed computer;

(b) data storage means, connected to the programmed computer, for storing a database describing a flight network and seat reservation requests, the flight network comprising a plurality of flight legs a, and itinerary p and fare class i combinations, each flight leg a having a residual seating capacity C_a, and each itinerary p and fare class i combination having a revenue yield fⁱ_p for a seat reserved therein;

(c) the programmed computer comprising seat assignment means for processing the database describing the flight network to assign seats in a flight leg a to one or more itinerary p and fare class i combinations, the seat assignment means comprising;

(i) means for calculating an initial expected marginal sat revenue (EMSR) λ

_a for all the flight legs a;

(2) means for computering a nested EMSR-prorated virtual fare vⁱ_p,a for each itinerary p and fare class i combination that contains a particular flight leg a having a nonzero residual seating capacity C_a so that;

##EQU22## (3) means for sorting the itinerary p and fare class i combinations into a list ordered by descending values of virtual fares vⁱ_p,a ;

(4) means for processing the sorted list of virtual fares vⁱ_p,a one-by-one to find an intersection point defining a new EMSR λ

_a for the particular flight leg a between functions;

##EQU23## wherein x is an independent variable, f^j _a is a jth largest virtual fare on leg a, and π

_j is a probability that more than C_a passengers are willing to pay ^j _a or more to travel on leg a;

(5) means for converging the EMSR λ

_a for the particular flight leg a;

(6) means for terminating the seat assignment means when the changes in the EMSR'"'"'s λ

_a '"'"'s for all flight legs a are insignificant;

(d) reservation terminal means, operatively connected to the programmed computer, for entering a seat reservation request for a particular itinerary p and fare class i combination; and

(e) the programmed computer comprising reservation means for receiving the seat reservation request for the particular itinerary p and fare class i combination from the reservation terminal means, for accepting the seat reservation request in accordance with a globally optimal set of EMSR'"'"'s λ

_a '"'"'s, for recording the seat reservation request in the database, and for transmitting an electronic status indication of the seat reservation request from the computer to the reservation terminal means.

7. The apparatus of claim 6, wherein the means for terminating further comprises means for terminating the seat assignment means when the changes in EMSR'"'"'s λ

_a '"'"'s for all flight legs a are less than a tolerance value.

8. The apparatus of claim 6, wherein the reservation means further comprises means for accepting the seat reservation request when the seat reservation request would yield revenue greater than or equal to a sum of the EMSR'"'"'s λ

_a '"'"'s for all flight legs a in the itinerary p.

9. An airline seat reservation system, comprising:

(a) a programmed computer;

(b) data storage means, connected to the programmed computer, for storing a database describing a flight network and seat reservation requests, the flight network comprising a plurality of flight legs a, and itinerary p and fare class i combinations, each flight leg a having a residual seating capacity C_a, and each itinerary p and fare class i combination having a revenue yield fⁱ_p for a seat reserved therein;

(c) the programmed control comprising seat assignment means for processing the database describing the flight network to assign seats in a flight leg a to one or more itinerary p and fare class i combinations, the seat assignment means comprising;

(1) means for calculating an initial expected marginal seat revenue (EMSR) λ

_a for all the flight legs a;

(2) means for computing a nested EMSR-differential virtual fare vⁱ_p,a for each itinerary p and fare class i combination that contains a particular flight leg a having a nonzero residual seating capacity C_a so that;

##EQU24## (3) means for sorting the itinerary p and fare class i combinations into a list ordered by descending virtual fares vⁱ_p,a for the particular flight leg a;

(4) means for processing the sorted list of virtual fares vⁱ_p,a one-by-one to find an intersection point defining a new EMSR λ

_a for the particular flight leg a between functions;

##EQU25## wherein x is an independent variable, f^j _a is a jth largest virtual fare on leg a, and π

_j is a probability that more than C_a passengers are willing to pay the virtual fare f^j_a or more to travel on leg a;

(5) means for terminating the seat assignment means when the changes in the EMSR'"'"'s λ

_a '"'"'s for all flight legs a are insignificant;

(d) reservation terminal means, operatively connected to the programmed computer, for entering a seat reservation request for a particular itinerary p and fare class i combination; and

(e) the programmed computer comprising reservation means for receiving the seat reservation request for the particular itinerary p and fare class i combination from the reservation terminal means, for accepting the seat reservation request in accordance with a globally optimal set of EMSR'"'"'s λ

_a '"'"'s, for recording the seat reservation request in the database, and for transmitting an electronic status indication of the seat reservation request to the reservation terminal means.

10. The apparatus of claim 9, wherein the means for terminating further comprises means for terminating the seat assignment means when the changes in EMSR'"'"'s λ

_a '"'"'s for all flight legs a are less than a tolerance value.

11. The apparatus of claim 9, wherein the reservation means further comprises means for accepting the seat reservation request when the seat reservation request would yield revenue greater than or equal to a sum of the EMSR'"'"'s λ

_a s for all flight legs a in the itinerary p.

12. A system for allocating physical resources, comprising:

(a) a computer;

(b) data storage means, connected to the computer, for storing a database describing a known resource capacity for each of a plurality of resource categories a, a known demand distribution for each of a plurality of demand categories z, a known revenue yield for a resource reserved within each demand category z, and a booking limit for each demand category z;

(c) the computer comprising resource assignment means for processing the database to assign resources in a resource category a to one or more demand categories z, the resource assignment means comprising;

(1) means for calculating an initial expected marginal resource revenue (EMRR) λ

_a for all resource categories a;

(2) means for computing an unnested EMRR-prorated virtual price v_z,a for every demand category z that contains a particular resource category a having a nonzero residual capacity C_a so that;

##EQU26## (3) means for calculating a new EMRR λ

_a for the particular demand category a based on the virtual prices v_z,a by applying Newton'"'"'s method to a resource capacity constraint for the particular resource category a;

##EQU27## wherein Q_z is an inverse of a cumulative probability density function of demand for demand category z, thereby ensuring that a total number of resources assigned to the demand category z are equal to the residual capacity C_a of the particular resource category a, wherein the virtual prices v_z,a are updated at each step of the Newton'"'"'s method since each step changes the EMRR λ

_a for the particular resource category a;

(4) means for converging the EMRR λ

_a for the particular resource category a;

(5) means for terminating the resource assignment means when the changes in the EMRR'"'"'s λ

_a '"'"'s for all resource categories a are insignificant;

(d) reservation terminal means, operatively connected to the computer, for entering a resource reservation request for a particular demand category z; and

(e) the computer comprising reservation means, for receiving the resource reservation request for the particular demand category z from the reservation terminal means, for accepting the resource reservation request in accordance with a globally optimal set of EMRR'"'"'s λ

_a '"'"'s, for recording the resource reservation request in the database, and for transmitting an electronic status indication of the resource reservation request to the reservation terminal means.

13. The apparatus of claim 12, wherein the means for calculating further comprises means for performing a binary search when the EMRR λ

_a fails to converge with Newton'"'"'s method.

14. The apparatus of claim 12, wherein the means for terminating further comprises means for terminating the resource assignment means when the changes in EMRR'"'"'s λ

_a '"'"'s for all resource categories a are less than a tolerance value.

15. The apparatus of claim 12, wherein the reservation means further comprises means for accepting the resource reservation request when the total number of resources assigned to the demand categories z is not exceeded.

16. The apparatus of claim 12, wherein the reservation means further comprises means for accepting the resource reservation request when the resource reservation request would yield revenue greater than or equal to a sum of the EMRR'"'"'s λ

_a '"'"'s for all resource categories a in the demand categories z.

17. A system for allocating physical resources, comprising:

(a) a computer;

(b) data storage means, connected to the computer, for storing a database describing a known resource capacity for each of a plurality of resource categories a, a known demand distribution for each of a plurality of demand categories z, a known revenue yield for a resource reserved within each demand category z and a booking limit for each demand category z;

(c) the computer comprising resource assignment means for processing the database to assign resources in a resource category a to one or more demand categories z, the resource assignment means comprising;

(1) means for calculating an initial expected marginal resource revenue (EMRR) λ

_a for all the resource categories a;

(2) means for computering a nested EMRR-prorated virtual price v_z,a for each demand category z that contains a particular resource category a having a nonzero residual capacity C_a so that;

##EQU28## (3) means for sorting the demand categories z into a list ordered by descending values of virtual prices v_z,a ;

(4) means for processing the sorted list of virtual prices v_z,a one-by-one to find an intersection point defining a new EMRR λ

_a for the particular resource category a between functions;

##EQU29## wherein x is an independent variable, f^j_a is a jth largest virtual price in resource category a, and π

_j is a probability that more than C_a customers are willing to pay f^j_a or more for a reservation in resource category a;

(5) means for converging the EMRR λ

_a for the particular resource categories a;

(6) means for terminating the resource assignment means when the changes in the EMRR'"'"'s λ

_a '"'"'s for all resource categories a are insignificant;

(d) reservation terminal means, operatively connected to the computer, for entering a resource reservation request for a particular demand category z; and

(e) the computer comprising reservation means for receiving the resource reservation request for the particular demand category z from the reservation terminal means, for accepting the resource reservation request in accordance with a globally optimal set of EMRR'"'"'s λ

_a '"'"'s, for recording the resource reservation request in the database, and for transmitting an electronic status indication of the resource reservation request to the reservation terminal means.

18. The apparatus of claim 17, wherein the means for terminating further comprises means for terminating the resource assignment means when the changes in EMRR'"'"'s λ

_a '"'"'s for all resource categories a are less than a tolerance value.

19. The apparatus of claim 17, wherein the reservation means further comprises means for accepting the resource reservation request when the resource reservation request would yield revenue greater than or equal to a sum of the EMRR'"'"'s λ

_a '"'"'s for all resource categories a in the demand category z.

20. A system for allocating physical resources, comprising:

(a) a computer;

(b) data storage means, connected to the computer, for storing a database describing a known resource capacity for each of a plurality of resource categories a, a known demand distribution for each of a plurality of demand categories z, a known revenue yield for a resource reserved within each demand category a, and a booking limit for each demand category z;

(c) the computer comprising resource assignment means for processing the database to assign resources in a resource category a to one or more demand categories z, the resource assignment means comprising;

(1) means for calculating an initial expected marginal resource revenue (EMRR) λ

f_a for all the resource categories a;

(2) means for computing a nested EMRR-differential virtual price v_z,a for each demand category z that utilizes a particular resource category a having a nonzero residual capacity C_a so that;

##EQU30## (3) means for sorting the demand categories z into a list ordered by descending virtual prices v_z,a ;

(4) means for processing the sorted list of virtual prices v_z,a one-by-one to find an intersection point defining a new EMRR λ

_a for the particular resource category a between functions;

##EQU31## wherein x is an independent variable, f^j_a is a jth largest virtual price in resource category a, and π

_j is a probability that more than C_a customers are willing to pay the virtual price f^j_a or more for a for a reservation in resource category a;

(5) means for terminating the resource assignment means when the changes in the EMRR'"'"'s λ

_a '"'"'s for all resource categories a are insignificant;

(d) reservation terminal means, operatively connected to the computer, for entering a resource reservation request for a particular demand category z; and

(e) The computer comprising reservation means for receiving the resource reservation request for the particular demand category z from the reservation terminal means, for accepting the resource reservation request in accordance with a globally optimal set of EMRR'"'"'s λ

_a '"'"'s, for recording the resource reservation request in the database, and for transmitting an electronic status indication of the resources reservation request to the reservation terminal means.

21. The apparatus of claim 20, wherein the means for terminating further comprises means for terminating the resource assignment means when the changes in EMRR'"'"'s λ

_a '"'"'s for all resource categories a are less than a tolerance value.

22. The apparatus of claim 20, wherein the reservation means further comprises means for accepting the resource reservation request when the resource reservation request would yield revenue greater than or equal to a sum of the EMRR'"'"'s λ

_a '"'"'s for all resource categories a in the demand category z.