A new bid price approach to dynamic resource allocation in network revenue management

• We develop a joint seat allocation and bid pricing mathematical formulation.
• We obtain time-dependent bid prices with corresponding resource allocations.
• We develop a column generation algorithm to solve large-scale problems.
• We develop an efficient heuristic procedure for solving the NP-hard sub problem.

Firms selling perishable products use a variety of techniques to maximize revenue through the dynamic control of their inventories. One of the most powerful and simple approaches to address this issue consists of assigning threshold values (“bid prices”) to each resource, and to accept requests whenever their revenue exceeds the sum of the bid prices associated with its constituent resources. In this context, we propose a new customer choice-based mathematical program to estimate time-dependent bid prices. In contrast with most approaches from the current literature, ours is characterized by its flexibility. Indeed, it can easily embed technical and practical constraints that occur in most central reservation systems (CRS). To solve the model, we develop a column generation algorithm, in which the NP-hard subproblem is addressed via an efficient heuristic procedure. Our computational results illustrate the performance of the method, through comparisons with alternative proposals.