Column generation algorithms for airline network revenue management problems

Ulusan, Aybike (2014) Column generation algorithms for airline network revenue management problems. [Thesis]

[thumbnail of AybikeUlusan_10048110.pdf] PDF

Download (451kB)


At the heart of the airline revenue management problem (ARM) lies the seat allocation problem, which has the ultimate aim of finding the right combination of passengers that will result in maximum profit. Due to the dynamic nature of the problem, optimal seat allocations can change continuously over the reservation period. In addition, widely used bid-price booking control policy which necessitates the dual information is obliged to be updated as the demand and capacity values adjust over the reservation period. Thus, in order to make changes in an interactive basis, it is crucial to solve the seat allocation problem in a small amount of time. This study embodies column generation algorithms applied to ARM problems. Networkbased ARM problems are computationally hard to solve even if the airline network is small. However, in this study we challenged ourselves with large-scale airline networks. For computational efficiency, the network is divided into subnetworks by means of date and time information. The overall network is decomposed to origin destination pairs, so that each pair is treated as a single-leg problem. The resulting seat allocation models (static, dynamic and deterministic linear programming) having a non-linear objective function are linearized by means of the transformation technique proposed by Dantzig which embodies a transformation only by means of additional decision variables. Since column generation can not cope with problems extending row-wise, Dantzigs formulation is the perfect fit. After applying column generation, the numerical results for the models is demonstrated.
Item Type: Thesis
Uncontrolled Keywords: Airline revenue management. -- Column generation. -- Linearization. -- Origin-destination based decomposition. -- Havayolu gelir yönetimi. -- Kolon türetme. -- Doğrusallaştırma. -- Başlangıç ve bitiş çiftlerine ayrıştırma.
Subjects: T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Industrial Engineering
Faculty of Engineering and Natural Sciences
Depositing User: IC-Cataloging
Date Deposited: 31 Mar 2016 10:34
Last Modified: 26 Apr 2022 10:06

Actions (login required)

View Item
View Item