Title: Solving the hierarchical data selection problem arising in airline revenue management systems

Authors: J. Xu, A. Lim, M. Sohoni

Addresses: Manhattan Associates, Inc., 10th Floor, 2300 Windy Ridge Pkwy, Atlanta, GA 30339, USA. ' Marketing Analytics, Inc., 500 Davis Street, Suite 1001, Evanston, IL 60201, USA. ' Indian School of Business, Gachibowli, Hyderabad 500 032, India

Abstract: In this paper, we describe an important optimisation problem arising in airline revenue management systems. The problem is to select the maximum number of average fare data while keeping the selected data in a non increasing hierarchical order. We first formulate the problem mathematically using 0–1 binary integer programming, and then further derive a stronger formulation using clique cuts. Moreover, an extension of the problem is studied where the relative importance of each data point can be derived from passenger count information. We develop an efficient dynamic programming-based algorithm to solve the problem optimally. The preliminary computational results using real airline data show that our approach can solve the problem efficiently and save significantly much information that are previously discarded.

Keywords: data selection; dynamic programming; longest increasing subsequence; optimisation; airline revenue management; average fare data; airline fares.

DOI: 10.1504/IJRM.2008.018178

International Journal of Revenue Management, 2008 Vol.2 No.1, pp.63 - 77

Published online: 06 May 2008 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article