Dynamic seat allocations for network revenue management in the airline industry

Most of the mathematical programming models for network seat inventory control problem do not account for the nesting of origin-destination (O-D) itineraries and fare classes on each flight leg. This dissertation develops a discrete-time dynamic programming (DP) model that implicitly considers the nested nature of the problem and provides a unified framework applicable to a large-scale O-D network. By using an optimal bid price policy an accept/deny decision for each booking request can be made to maximize the total expected revenue. Moreover, as a practical issue in airline industry, group reservations on various O-D and fare class combinations are also incorporated into the model.; Given the decision time period and network capacity, an upper bound for the optimal future revenue function is provided by analyzing a deterministic Integer Programming (IP) problem. It is proved that when customer demands are large, the upper bounds are asymptotically optimal under fixed network capacity. Even though the bid price properties have been analyzed by other researchers in the single and double flight-leg scenarios, two counter examples are presented to show that some of their monotonic results turn out to be in error. In effect, it is shown that critical decision time periods do not exist for two connected flight-leg networks and single flight-legs with multiple bookings.; In order to implement a bid price control strategy in real time, several approximation methods are proposed based on a network decomposition scheme and a function approximation technique. The performance of the different methods is evaluated by their computational efficiencies and revenue impacts. Computational results are presented on a set of randomly generated problems with network sizes ranging from a two flight-leg network to a hub-and-spoke network consisting of 50 flight-legs. Significant revenue increases over a non-nested booking limit control are obtained by a single-leg-based (SLB) approach and a double-leg-based approach with and without function approximation (DLBFA and DLB). The DLB approach consistently performs well in terms of revenue growth, while the DLBFA method results in a significant reduction of data storage space.