Abstract:
A revenue management software system supports decisions to accept or deny requests for resource capacity (seats, rooms, volume/weight, air time, etc.) using control logic that accesses multidimensional lookup tables of price values for each resource (flight leg, hotel day, etc.). Each dimension of each lookup table corresponds to a variable that affects the value for the resource. As an example where the resource is airline seating capacity for a given flight itinerary, a two-dimensional threshold value table is employed for each flight leg in the itinerary where the first dimension specifies the current time slot and the other dimension the current number of reservations accepted (reservation level) for the flight leg. A request for a seat on the flight is accepted if and only if its net revenue exceeds or equals the sum of the current table values (i.e. the table entries corresponding to the current time and current reservation level) for each requested flight leg.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates in general to a revenue management system (also referred to as “yield management” system) for allocating resources or inventory in which a multidimensional lookup table of threshold values is employed for each resource as the control logic for dynamically adjusting the acceptable revenue value for the resources as a function of two or more variables. 
     2. Description of the Prior Art 
     Revenue management systems seek to maximize the revenue generated from a fixed service or productive capacity by selectively accepting or denying requests for capacity. For example, in airlines a network of flights with a set of seats are available for sale on a given day, and customers request seats in advance of travel for various itineraries on the network. Based on the current reservations already accepted for each flight (alternatively, the remaining capacity available), the time remaining in the sales horizon and forecasts of future demand for itineraries, airlines must decide which itineraries and fare classes to accept and which to deny (or close out). 
     These decisions are very detailed and complicated to make because future demand is typically highly uncertain and one must evaluate complex tradeoffs between the current and future value of capacity. Therefore, revenue management decisions are typically made or guided by a software system (revenue management system) that incorporates a variety of advanced statistical and mathematical methods. Revenue management is widely used in the airline, hotel and car-rental industries and is spreading to the energy, natural gas pipelines, broadcasting, shipping, sports, entertainment facilities, manufacturing, equipment leasing and cargo industries. Indeed, the practice is applicable in any industry that has limited short-term capacity flexibility and variable demand. 
     A variety of mathematical models have been proposed to solve the problem of which requests to accept or deny based on current capacity and forecasts of future demand. However, regardless of the mathematical model and assumptions used, revenue management software systems ultimately need an internal control logic to implement the accept/deny recommendations. To date, two control schemes have been developed to implement accept/deny decisions: nested capacity allocation and static-bid prices. 
     The oldest and most widespread approach to implementing accept/deny decisions is to use nested capacity allocations (also called “booking limits”) on the various classes and rates for the capacity. This is the approach used in the early work of Littlewood (1972) on discount fare class allocation. It was popularized in the academic literature by Belobaba (1987, 1989). This is the approach used in many of the older commercial revenue management systems. 
     One example of a nested capacity allocation scheme is known as Single-resource Nested Allocations. This approach was originally developed to allocate capacity of a single resource, for example a single flight leg, to one of n possible demand classes (fare-classes in airline industry). The control logic works as follows: 
     Let c be the total capacity. Let the net revenues of the n demand types be denoted f i  and assume without loss of generality that these demand classes are indexed so that f 1 &gt;f 2 &gt;Y&gt;f n . A so-called nested allocation logic specifies values (protection levels) x 1 , x 2 , Y, x n  that satisfy 
     
       
         0≦x n ≦x  n−1 ≦Y≦x n =c. 
       
     
     Let y denote the remaining capacity. The logic is to accept demand class i if and only if 
     
       
         y&gt;x i i=1,Y,n 
       
     
     That is, demand class i is accepted if the remaining capacity exceeds the protection level, x i , for that class. An alternative and more popular method to implement this same logic is to define a set of booking limits, b i , using 
     
       
         b i =cBx i   
       
     
     Let r denote the number of reservations on hand (r=c−y). In this case, the logic is to accept a request from demand type i if and only if 
     
       
         r&lt;b i   
       
     
     That is, accept demand class i if and only if the number of reservations on hand is less than the booking limit for demand class i. The maximum available capacity for any class i is usually refelTed to as the authorization level and is defined by 
     
       
         a i =max{b i Br,0} 
       
     
     These are the control logic schemes described in Belobaba (1987, 1989) and Brumelle et al. (1990, 1993) and elsewhere. Belobaba (1987, 1988) describes some approximate methods for setting allocation parameters while Brumelle et al. (1990, 1993) describe exact algorithms for computing the parameters. 
     Whatever method is used to compute the parameter values, the nested allocation structure has some distinct advantages. Namely, it has the desirable feature that a small number of control parameters (n booking limits or protection levels) can be calculated once by an optimization module. Then, the accept/deny decisions dynamically adjust as available capacity changes. That is, as more capacity is sold, more demand classes are “closed out” as booking limits are reached. Alternatively, when customers cancel, more capacity becomes available and some demand classes may “open up” as the available capacity exceeds their booking limits. In this way, the nested allocation structure adjusts to the evolving capacity conditions. 
     While the nested allocation scheme works well for a single resource, extending it to allocate capacity for multiple resources (legs of a flight network for example) is somewhat problematic. For example, it is not clear how to rank demand class that use different resources, so the nested structure becomes difficult to apply. Also, if allocations are defined for all revenue values and every combination of resources, the number of allocation values required becomes too large for practical implementation in a reservation system. 
     To avoid this large number of allocation values, most approaches for extending nested allocation control logic to networks involve converting the multiple-resource allocation problem into a collection of single-resource problems and then applying the controls generated by this collection of single-resource allocation problems. 
     This is accomplished as follows: First, the revenue values for a multiple resource request are adjusted by quantities that reflect the displacement value of the other resources used by the request. These displacement-adjusted fare values are then used to compute nested allocations for each leg. Displacement adjusted values are often clustered into “virtual classes” first to reduce the number of classes involved. This process of creating virtual classes is called indexing by Smith et al. (1992). See Williamson (1992) and Vinod (1990) for further discussion of this approach, which also goes by the name of virtual nesting (Smith et al. 1992). 
     These displacement-adjusted values have some advantages: They require only a small number of control variables and the nested allocation structure maintains the favorable property of adjusting accept/deny decisions as available capacity changes. They also provide a maximum available capacity for each demand class through the authorization levels. However, the displacement adjustment process and clustering into virtual classes adds a significant amount of complexity to the control logic. This complexity has made their implementation prohibitive for most users of revenue management systems. 
     An alternative control logic for multiple-resource problems is to use what are called resource bidprices. This idea was first proposed by Simpson (1989) and was extensively investigated in the Ph.D. dissertation of Williamson (1992). See also Cuny (1992) and Phillips (1994). Let m denote the number of resources to allocate. In a bid price control scheme, values (bid prices) ν i , i=1, . . . ,m are set for each of the m resources. Suppose a request comes in to purchase a set of resources {i 1 , . . . ,i k }. Then a bid price control would accept the request of net revenue value if and only if 
     
       
         f&gt;ν 1 +Y+ν ik   
       
     
     That is, a request is accepted if and only if the fare exceeds the sum of the bid prices of all the capacity units required to satisfy the demand. The interpretation of the values ν i  is that they represent the threshold value of resource capacity. Again, a variety of optimization methods and approximations have been proposed for determining the bid price parameter values. (See Simpson (1989) and Williamson (1992).) 
     The advantage of the bid price logic is that it requires very few parameters, one value for each resource, and does not require separate displacement adjustment and indexing steps. The main weakness is that the logic is not dynamic. Specifically, the accept/deny decisions do not change if remaining capacity fluctuates and/or the time remaining in the horizon changes. As a result, the bid price values ν i  must be updated very frequently (usually by re-forecasting and re-optimizing a mathematical model) to ensure that they track changes in the available capacity among all resources. Ideally, this updating of bid-prices has to be done after each booking or cancellations (or change in the remaining resource) which is prohibitive to do operationally. They also do not provide any indication of the maximum available capacity for a given demand class and cannot be used directly to compute authorization levels. 
     SUMMARY OF THE INVENTION 
     In view of the foregoing, a need exists for a revenue management scheme that is robust enough to accommodate allocation of multiple resources, each of which is dependent on multiple variables, yet which possesses simplicity and ease of implementation. The present invention satisfies this need through use of multidimensional lookup tables that are employed to manage revenue from each resource as a function of a plurality of variables (such as time and capacity, for example). The main benefit of the approach is to add a high degree of flexibility and dynamic adjustment ability to the control logic while keeping the number of controls used to within acceptable operational limits. 
     In this control logic, a multidimensional table (array) of threshold values is specified for each resource. Each dimension (axis) of the table corresponds to a variable that affects the threshold value of the resource. In an exemplary two-dimensional table for determining threshold values for travel reservations, one dimension of the table, t, is selected to index the number of remaining time periods and the other, x, is selected to index the remaining capacity for the desired reservation. 
     The lookup tables are employed in the method of the present invention in the following manner. First, a request for a resource, or a combination of resources, is received in a system computer either from another system or computer, or form an operator entering the request manually. The request not only identifies each of the resources, but also identifies a revenue value for the resources. For example, a multiple flight leg itinerary for an airline reservation represents a multiple resource allocation scenario, with each leg of the flight representing one of the resources, and the entered or calculated expected fare for the itinerary representing the revenue value. 
     Once the request has been entered, the computer accesses the lookup table for each resource identified in the request. The control logic for using the tables is that the threshold value used at any point in time for any given resource is obtained by looking in the appropriate place in the table. As the variables defining the dimensions (e.g., available capacity and the time remaining) of the table change, the threshold value in the table can adapt. After the threshold values for the present combination of variables are extracted from the tables, the net revenue of a request is compared to the sum of the threshold values of the resources required by the request. If the net revenue exceeds or equals the total of the threshold values, then it is accepted; if it does not, it is rejected. The ability of the threshold values for each resource to change as the variables (e.g., remaining capacity and remaining time) change, adds robustness and stability to the sale process—for instance, it offers protection that a sudden unexpected surge in demand at a low fare would not result in too much inventory being sold at a too low a rate (a problem with the static bid-price controls); at the same time, a persistent and inconsistent (with the forecasts) failure of demand to appear between re-forecasting re-optimizations would result in the current threshold value to automatically go down, a feature not present either in the allocation controls or static bid-price controls. 
     Thus, through this dynamic threshold value control logic, a considerable amount of dynamic adjustment capability can be achieved in a revenue or yield management system. At the same time, it preserves simplicity and speed, and requires only a modest number of control parameters, namely one table for each resource. Further, the present invention offers significant generalization in the degree of control, as well as superior robustness with respect to forecasting errors and operational factors compared to the current control logic used to control inventory in revenue management systems. 
     Another major advantage of the tables is that they can be used to quickly compute maximum allocations for each demand type. This is achieved by successively adding the threshold values and then decrementing each resource&#39;s capacity value until the sum of the threshold values exceeds the net revenue of the demand type. The amount by which the capacity was decremented gives the maximum capacity allocation for the demand type. This logic follows simply by considering how many requests of a given type would be accepted in sequence. 
     This decision logic requires only a simple table lookup (database query or memory access) operation, which is very fast. It is capable of mimicking the decisions of nested allocation and traditional bid price controls, but provides additional flexibility to allow the threshold values to adjust to capacity and time changes. It also allows for easy calculation of maximum available capacity for any given type of request. Moreover, since the lookup table logically separates the optimization modules and reservation-acceptance modules, it provides improved additional robustness in the operation of revenue management systems. Also, it simulates frequent re-optimizations and is highly resilient to forecasting errors and bias in the forecasts. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The features and advantages of the present invention will become apparent form the following detailed description of a preferred embodiment thereof, taken in conjunction with the accompanying drawings, in which: 
     FIG. 1 is a schematic diagram of networked computer system that can be employed to implement the preferred embodiment of the present invention; 
     FIGS. 2A and 2B are example two dimensional threshold value tables that are employed to illustrate the functionality of the preferred embodiment; 
     FIG. 3 is a flow chart illustrating the logic used in an exemplary application of the preferred embodiment for processing requests for seat reservations using the threshold value tables; and 
     FIG. 4 is a flow chart illustrating the logic used in an exemplary application of the preferred embodiment for determining the maximum number of seats available at a predetermined fare using the threshold value tables. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     With reference first to FIG. 1, a revenue management system  10  is illustrated that is employed for implementing a first preferred embodiment of the present invention for managing reservations for a limited capacity resource, such as seats on an airline flight. The system  10  includes a plurality of networked computers  12 , each of which communicates with a threshold value table server  14 . In this embodiment of the invention, the threshold value table server  14  manages access to a plurality of lookup tables referred to as dynamic threshold value tables, each of which contains threshold values for a resource as a function of two or more variables. A reservation system computer  16  is interfaced to the threshold value table server  14  which handles reservation bookings requested through the computers  12 , and manages the reservation yield. Finally, a database  18  is provided for maintaining historical records of all processed reservations. 
     In the operation of the system  10 , a system operator enters a request for either a reservation or an authorization level for a particular itinerary into one of the computers  12 . In response, the bid-plice table server  14  accesses all applicable threshold value tables for the itinerary, and supplies them to the reservation system computer  16  for processing. In the case of an itinerary consisting of multiple airline flight legs, a threshold value table will be provided for each flight leg. In this example, as will be discussed in greater detail below in conjunction with FIGS. 2A-2B, the reservation system computer  16  employs the threshold value tables to determine acceptable price values for each flight leg of the requested itinerary. The sum of these is compared to the net revenue expected from the use of the resources for the reservation system to determine whether the reservation will be accepted and/or how many reservations at the given revenue value will be accepted. The net revenue value is received by the system either by being entered by the system operator or another computer system. In addition, this value may be calculated by another system. 
     To better understand the threshold value tables and their use, reference is made to FIGS. 2A and 2B which illustrate two examples of such tables for two undefined resources, Resource  1  and Resource  2 . Each of the tables comprises a two-dimensional table (array) of numerical values that is specified for each resource. One dimension or axis of the table, t, indexes the number of remaining time periods available for reserving the resource, and the other, x, indexes the remaining capacity for the resource. The shaded area in each of the tables represent regions where a revenue value of 80 and 25 for Resource  1  and Resource  2 , respectively, will be accepted for the particular combination of t and x. 
     The threshold value used at any point in time for any given resource is obtained by looking in the appropriate place in the table. For example, consider Table  1  of FIG.  2 A. If the remaining capacity for this resource is 3 units and the remaining time index is 7, then the table value is 69.61. Thus, the threshold value in effect under these conditions is 69.91. If the available capacity changes or the time remaining changes, the threshold value in the table can adapt. Continuing the example, if the remaining time index is 7 and 2 of the 3 units of capacity are sold, one unit of capacity remains. In this case, the value in Table  1  of FIG. 2A indicates that the threshold value has increased to 116.6. 
     As discussed above in conjunction with FIG. 1, the reservation system computer  16  compares the net revenue of a request to the sum of the threshold values of the resources required by the request. If the net revenue exceeds or equals the total of the threshold values, then it is accepted; if it does not, it is rejected. For example, suppose the time index remaining is 7, the Table  1  resource has 3 units of capacity remaining and the Table  2  resource has 4 units of capacity remaining. The acceptable threshold values for each resource are then 69.91 and 4.001, respectively. If a request is received that requires both resources with a net revenue of 70, the computer  16  compares it to the sum 69.91+4.001=73.911. Since 70&lt;73.991, the request is rejected. 
     The difference between this process and conventional bid price logic is that the threshold value for each resource changes as remaining capacity and remaining time change. For example, if there is a cancellation of a previously accepted request for the resource in Table  1  so that the remaining capacity increases to 4, the new sum becomes 34.71+4.001=38.781. In this case, a request with net revenue of 70 will be accepted. After accepting this request, however, the remaining capacity of resource  1  would be 3 again and the threshold value would rise to its previous value of 69.91. Therefore, another request of the same type would be rejected if it arrived next. 
     The logic of this decision rule is diagramed in the flow chart of FIG. 3 for the specific example where each resource is a seat on a flight leg of a requested itinerary i, and the threshold values in each lookup table represent minimum prices that will be accepted for the corresponding flight leg. First, at step  100 , the seat reservation request is received from a system operator or another system, and identifies the itinerary i, as well as the fare f, which the passenger wishes to pay. Next, at step  102 , the reservation system computer  16  performs a lookup operation for the current threshold value for each flight leg in the itinerary. This is accomplished by sending the current time and current capacity vector to the threshold value table server  14 . In response, at step  104 , the threshold value table server  14  accesses the threshold value table for each of the flight legs, and retrieves the price value for each leg corresponding to the time and capacity vector. The threshold values for all of the legs in the itinerary are then returned to the reservation system computer  16 . Finally, at step  106 , the reservation system computer sums all of the retrieved threshold values, and, at step  108 , compares the sum to the requested fare f. If f is greater than or equal to the sum the reservation is accepted; otherwise, it is rejected. If the reservation is accepted, a record of the reservation is sent to the database  18  so that the current capacity will be properly adjusted for the next reservation request requiring any of the legs in the itinerary i. 
     A second major advantage of the dynamically adjustable threshold value tables is that they can be used to quickly compute maximum allocations for each demand type. This is achieved by successively adding the threshold values and then decrementing each resource&#39;s capacity value until the sum of the threshold values exceeds the net revenue of the demand type. The amount by which the capacity was decremented gives the maximum capacity allocation for the demand type. This logic follows simply by considering how many requests of a given type would be accepted in sequence. The logic is diagramed in the flow chart in FIG. 4, and an example of this authorization level calculation follows. First, at step  200 , a system operator enters a request for the maximum possible seat reservations that will be accepted for an itinerary i at a fare per seat of no more than A count k is initialized to 0 to keep track of the total number of seats available atf Next, at f. step  202 , the process of FIG. 3 is carried out to determine whether a first seat reservation will be accepted at fare for the current capacity and time vector. Assuming it will be accepted, k is incremented by 1 at step  204 , and step  202  is repeated, but this time with the current used capacity incremented by 1, and the current available capacity decremented by 1. This process is repeated until the sum of the threshold values is greater than or equal to the fare for the (k+1)th request. When this occurs, the value k is determined at step  206  to be the number of reservations that will be accepted at the fare f for the itinerary i, and this value is returned to the reservation/booking system. 
     To illustrate this process more clearly, the tables in FIGS. 2A and 2B may be employed in the following example. Consider Tables  1  and  2  with 10 units of time remaining, with Resource  1  having 6 units of capacity remaining (threshold value of 19.95) and with Resource  2  having 4 units remaining (threshold value of 14.5). Suppose it is desired that an authorization level be computed for a demand class that has a net revenue of 160 and requires both Resources  1  and  2 . 
     Comparing 160 to the current threshold values of 19.95+14.50=34.45, the first request of this type would be accepted. Proceeding, the capacity values of Resources  1  and  2  are decremented to 5 and 3, respectively, which yield threshold values of 44.03 and 38.66, respectively. The new sum of the prices is 44.03+38.66=82.69. Since this sum is still less than 160, a second request of this type would be accepted. Continuing in this manner, it is determined that up to 3 units of the 160 demand type can be accepted without the threshold value total exceeding 160. However, the fourth request of this type would push the total threshold value fiom the tables up to 207.03, so that this request would be rejected. Thus, the maximum capacity that would be sold B the authorization level B is 3 units. In this way, an authorization level can be quickly computed for any demand type with any associated net revenue and requiring any arbitrary set of resources. 
     Although the foregoing examples illustrate the process of the present invention, it will of course be understood that the invention is not limited to any particular application. On the contrary, the threshold value tables can be used for managing any type of resource reservation application where the threshold value of one or more resources varies as a function of two or more variables. For example, although the invention is particularly useful for managing transportation and accommodation related sales or reservations (e.g., airline, train, bus and hotel reservations, etc.), the invention may also be employed for managing cargo inventory. In this application, three-dimensional threshold value lookup tables are preferably employed, with one dimension for each of the following three variables that have an influence on current acceptable threshold values: time, weight and volume. Further, although the invention is particularly suited for determining acceptable monetary values for travel reservations, the lookup tables can be used for determining any type of acceptable threshold value that fluctuates as a function of two or more variables. 
     Other applications of the present invention include allocation of advertising time slots and allocation of tickets to facilities (sports, theaters, cinema, amusement parks, resorts). In the case of advertising time slots, the dimensions for the lookup table will be remaining available time-slots, and the time of broadcast for the media industry (television, radio, print media, Internet advertising, etc.). In the case of tickets to facilities, the dimensions for the lookup table will be time remaining until the scheduled event, and number of available seats remaining in each class. 
     In conclusion, the present invention, through use of the dynamically adjustable threshold value tables, provides a vastly improved and robust revenue or yield management system and method that can easily accommodate changes in resource threshold values in response to many variables, without requiring complex computer software. Although the present invention has been disclosed in terms of a preferred embodiment and variations thereon, it will be understood that numerous additional variations and modifications could be made thereto without departing from the scope of the invention as set forth in the following claims.