Indexed on: 09 Dec '05Published on: 09 Dec '05Published in: OR Spectrum
This paper develops a model-free simulation-based optimization model to solve a seat-allocation problem arising in airlines. The model is designed to accommodate a number of realistic assumptions for real-world airline systems—in particular, allowing cancellations of tickets by passengers and overbooking of planes by carriers. The simulation–optimization model developed here can be used to solve both single-leg problems and multi-leg or network problems. A model-free simulation–optimization approach only requires a discrete-event simulator of the system along with a numerical optimization method such as a gradient-ascent technique or a meta-heuristic. In this sense, it is relatively “easy” because alternative models such as dynamic programming or model-based gradient-ascent usually require more mathematically involved frameworks. Also, existing simulation-based approaches in the literature, unlike the one presented here, fail to capture the dynamics of cancellations and overbooking in their models. Empirical tests conducted with our approach demonstrate that it can produce robust solutions which provide revenue improvements over heuristics used in the industry, namely, EMSR (Expected Marginal Seat Revenue) for single-leg problems and DAVN (Displacement Adjusted Virtual Nesting) for networks.