یک الگوریتم برنامهریزی پویا بر اساس تقریب درآمد مورد انتظار برای مسئله مدیریت درآمد شبکه ای

Since American Airlines successfully applied revenue management (RM) to raise its revenue, RM has become a common technique in the airline industry. Due to the current hub-and-spoke operation of the airline industry, the focus of RM research has shifted from the traditional single-leg problem to the network-type problem. The mainstream approaches, bid price and virtual nesting, are faced with some limitations such as inaccuracy due to their suboptimal nature and operation interruption caused by the required updates. This study developed an algorithm to generate a seat control policy by approximating the expected revenue function in a dynamic programming (DP) model. In order to deal with the issue of dimensionality for the DP model in a network context, this study used a suitable parameterized function and a sampling concept to achieve the approximation. In the numerical experiment, the objective function value of the developed algorithm was very close to the one achieved by the optimal control. We believe that this approach can serve as an alternative to the current mainstream approaches for the network RM problem for airlines and will provide an inspiring concept for other types of multi-resource RM problems.

Revenue management (RM) has become common practice in the airline industry ever since American Airlines successfully applied several RM techniques to raise its revenue. For example, it has been estimated that RM practices generated an additional revenue of US$1.4 billion for American Airlines over a 3-year period around 1988 (Smith et al., 1992). In today’s market it is very difficult for any major airline to operate profitably without RM, since according to most estimates the revenue gained by applying RM is about 4–5%, which is comparable to many airlines’ total profitability in a good year (Talluri and van Ryzin, 2004). Nonetheless, how to realize the basic concept of RM, selling the right seat to the right customer at the right price, remains a challenge. Due to the current hub-and-spoke operation of the airline industry, the focus of RM research has shifted from the traditional single-leg problem to the network problem. With multiple types of products and resources, the decision of how to sell one type of product is complicated by its impact on the future sales of the product types sharing the same resource(s). The problem complexity and the associated computational load make it impossible to derive the optimal control for a problem of practical size. The mainstream approaches, bid price and virtual nesting, have some limitations such as the inaccuracy due to their suboptimal nature and the operation interruption caused by the required updates. This study developed an algorithm to generate a seat control policy by approximating the expected revenue function in a dynamic programming (DP) model. In order to deal with the issue of dimensionality in a network context, this study used a suitable parameterized function and a sampling concept to achieve the approximation. The remainder of this paper is organized as follows. Section 2 provides the background of the problem and reviews the related literature. The DP model for the network RM problem and the algorithm based on a parameterized function are presented in Section 3. The numerical experiment is described in Section 4. Finally, the findings of this study are summarized and conclusions are drawn in Section 5.

Due to the current hub-and-spoke operation of the airline industry, research in the network RM problem for airlines is very important. The mainstream approaches, bid price and virtual nesting, have some limitations such as the inaccuracy due to their suboptimal nature and the interruption of the operation as a result of the required updates. This study developed a solution algorithm that generates a seat control policy by approximating the expected revenue function in a DP model. In order to deal with the issue of dimensionality in the context of a network, this study used a suitable parameterized function and a sampling approach to achieve the approximation. Since the numerical experiment is based on a small two-leg network, it was possible to use a DP model to determine the expected revenue of the optimal control policy and the control policy developed by this study. The quality of the solution is consistent and quite close to that of the optimal control. It is worth noting that only a few sampling points are needed to achieve a good solution quality. This new approach can be used as an alternative to the popular mainstream approaches for the network RM problem for the airline industry, and should be an inspiring concept for other types of multi-resource RM problems. In terms of future research directions, there are some issues that require further attention. First, at this moment, the parameterized function used in this study is an exponential-type function, which is simple and appears to works well. Nonetheless, it is possible that some other types of functions satisfying the characteristics of the expected revenue function in the DP model can achieve better control. In addition, there is a chance that a customized non-linear regression procedure, replacing the built-in function in the software package, can raise the computational efficiency or solution quality. Finally, in order to fully verify the strength and the limitation of the proposed algorithm, a simulation experiment based on large-scale problems with real operational data is being considered.