Two-stage stochastic programming model for capacitated complete star p-hub network with different fare classes of customers

Document Type : Research Paper


1 Department of Industrial Engineering, Yazd University, Yazd, Iran

2 yazd university


In this paper, a stochastic programming approach is applied to the airline network revenue management problem. The airline network with the arc capacitated single hub location problem based on complete–star p-hub network is considered. We try to maximize the profit of the transportation company by choosing the best hub locations and network topology, applying revenue management techniques to allocate limited perishable capacity and provide booking limits for all itineraries and fare classes. In order to characterize the uncertainty of demand in the airline market, we introduce stochastic variations caused by seasonally passengers’ demands through a number of scenarios. The proposed model deals with finding the location of hub facilities, the assignment of demand nodes to these located hub facilities and allocating the limited capacity of aircraft seats on each rout to different customer classes in order to maximize the profit. Due to the computational complexity of the resulted model, a hybrid algorithm improved by a caching technique based on standard genetic operators is used to find a near optimal solution of the problem. Numerical experiments are carried out on the Turkish network data set. The performance of the solutions obtained by the proposed algorithm is compared with the pure GA and Imperialist Competitive Algorithm in terms of the computational time requirements and solution quality.


Main Subjects

Adibi, A., & Razmi, J. (2015). 2-Stage stochastic programming approach for hub location problem under uncertainty: A case study of air network of Iran. Journal of Air Transport Management47, 172-178.
Alumur, S. A., Nickel, S., & Saldanha-da-Gama, F. (2012). Hub location under uncertainty. Transportation Research Part B: Methodological46(4), 529-543.
Alumur, S., & Kara, B. Y. (2008). Network hub location problems: The state of the art. European journal of operational research190(1), 1-21.
Amaruchkul, Kannapha, William L. Cooper, and Diwakar Gupta. "Single-leg air-cargo revenue management." Transportation Science 41.4 (2007): 457-469.
Aslani, S., Modarres, M., & Sibdari, S. (2014). On the fairness of airlines’ ticket pricing as a result of revenue management techniques. Journal of Air Transport Management40, 56-64.
Belobaba, P. P. (1989). OR practice—application of a probabilistic decision model to airline seat inventory control. Operations Research37(2), 183-197.
Belobaba, P. P., & Weatherford, L. R. (1996). Comparing decision rules that incorporate customer diversion in perishable asset revenue management situations. Decision Sciences27(2), 343-363.
Birge, J. R., & Louveaux, F. (2011). Introduction to stochastic programming. Springer Science & Business Media.
Brumelle, S. L., & McGill, J. I. (1993). Airline seat allocation with multiple nested fare classes. Operations Research41(1), 127-137.
Campbell, J. F. (1994). Integer programming formulations of discrete hub location problems. European Journal of Operational Research72(2), 387-405.
Campbell, J. F., & O'Kelly, M. E. (2012). Twenty-five years of hub location research. Transportation Science46(2), 153-169.
Çetiner, D. (2013). Fair revenue sharing mechanisms for strategic passenger airline alliances (Vol. 668). Springer Science & Business Media.
Chen, S., Gallego, G., Li, M. Z., & Lin, B. (2010). Optimal seat allocation for two-flight problems with a flexible demand segment. European Journal of Operational Research201(3), 897-908.
Chiang, W. C., Chen, J. C., & Xu, X. (2006). An overview of research on revenue management: current issues and future research. International Journal of Revenue Management1(1), 97-128.
Cizaire, C., & Belobaba, P. (2013). Joint optimization of airline pricing and fare class seat allocation. Journal of Revenue and Pricing Management,12(1), 83-93.
Contreras, I., Cordeau, J. F., & Laporte, G. (2011). Stochastic uncapacitated hub location. European Journal of Operational Research212(3), 518-528.
Curry, R. E. (1990). Optimal airline seat allocation with fare classes nested by origins and destinations. transportation science24(3), 193-204.
Ebrahimi-Zade, A., Hosseini-Nasab, H., & Zahmatkesh, A. (2016). Multi-period hub set covering problems with flexible radius: A modified genetic solution. Applied Mathematical Modelling40(4), 2968-2982.
Farahani, R. Z., Hekmatfar, M., Arabani, A. B., & Nikbakhsh, E. (2013). Hub location problems: A review of models, classification, solution techniques, and applications. Computers & Industrial Engineering64(4), 1096-1109.
Feng, Bo, Yanzhi Li, and Zuo-Jun Max Shen. "Air cargo operations: literature review and comparison with practices." Transportation Research Part C: Emerging Technologies 56 (2015): 263-280.
Feng, Y., & Xiao, B. (2006). Integration of pricing and capacity allocation for perishable products. European Journal of Operational Research168(1), 17-34.
Holland, J. H. (1975). Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. U Michigan Press.
Huang, Kuancheng, and Ko-chen Chang. "An approximate algorithm for the two-dimensional air cargo revenue management problem." Transportation Research Part E: Logistics and Transportation Review 46.3 (2010): 426-435.
Jaillet, P., Song, G., & Yu, G. (1996). Airline network design and hub location problems. Location science4(3), 195-212.
Kara, B. Y., & Tansel, B. C. (2000). On the single-assignment p-hub center problem. European Journal of Operational Research125(3), 648-655.
Kimes, S. E. (1989). Yield management: a tool for capacity-considered service firms. Journal of operations management8(4), 348-363.
Kratica, J., Stanimirović, Z., Tošić, D., & Filipović, V. (2007). Two genetic algorithms for solving the uncapacitated single allocation p-hub median problem. European Journal of Operational Research182(1), 15-28.
Lapp, M., & Weatherford, L. (2014). Airline network revenue management: Considerations for implementation. Journal of Revenue and Pricing Management13(2), 83-112.
Littlewood, K. (1972). Forecasting and Control of Passenger Bookings, AGIFORS 12th Annul Symposium Proceedings. October, Nathanya, Israel, 193-204.
McGill, J. I., & Van Ryzin, G. J. (1999). Revenue management: Research overview and prospects. Transportation science33(2), 233-256.
Moed, M. C., Stewart, C. V., & Kelly, R. B. (1991, November). Reducing the search time of a steady state genetic algorithm using the immigration operator. In Tools for Artificial Intelligence, 1991. TAI'91., Third International Conference on (pp. 500-501). IEEE.
Mou, D., & Wang, X. (2014). Uncertain Programming for Network Revenue Management. Mathematical Problems in Engineering2014.
Nechval, N., Purgailis, M., Rozevskis, U., & Nechval, K. (2013). Adaptive Stochastic Airline Seat Inventory Control under Parametric Uncertainty. In International Conference on Analytical and Stochastic Modeling Techniques and Applications (pp. 308-323). Springer Berlin Heidelberg.
O'kelly, M. E. (1987). A quadratic integer program for the location of interacting hub facilities. European Journal of Operational Research32(3), 393-404.
Pfeifer, P. E. (1989). The airline discount fare allocation problem. Decision Sciences20(1), 149-157.
Radcliffe, N. J. (1991). Forma Analysis and Random Respectful Recombination. In ICGA (Vol. 91, pp. 222-229).
Sim, T., Lowe, T. J., & Thomas, B. W. (2009). The stochastic p-hub center problem with service-level constraints. Computers & Operations Research,36(12), 3166-3177.
Tan, Pinar Z., and Bahar Y. Kara. "A hub covering model for cargo delivery systems." Networks 49.1 (2007): 28-39.
Talluri, K. T. (2001). Airline revenue management with passenger routing control: A new model with solution approaches. International Journal of Services Technology and Management2(1-2), 102-115.
Toh, R. S., & Higgins, R. G. (1985). The impact of hub and spoke network centralization and route monopoly on domestic airline profitability.Transportation Journal, 16-27.
Topcuoglu, H., Corut, F., Ermis, M., & Yilmaz, G. (2005). Solving the uncapacitated hub location problem using genetic algorithms. Computers & Operations Research32(4), 967-984.
Williamson, E. L. (1992). Airline network seat inventory control: Methodologies and revenue impacts. [Cambridge, Mass.: Massachusetts Institute of Technology, Dept. of Aeronautics & Astronautics], Flight Transportation Laboratory,[1992].
Wollmer, R. D. (1992). An airline seat management model for a single leg route when lower fare classes book first. Operations Research40(1), 26-37.
Yang, T. H. (2009). Stochastic air freight hub location and flight routes planning. Applied Mathematical Modelling33(12), 4424-4430.
Zhang, D., & Adelman, D. (2009). An approximate dynamic programming approach to network revenue management with customer choice.Transportation Science43(3), 381-394.
Zhang, D., & Cooper, W. L. (2009). Pricing substitutable flights in airline revenue management. European Journal of Operational Research197(3), 848-861.
Zhang, D., & Cooper, W. L. (2005). Revenue management for parallel flights with customer-choice behavior. Operations Research53(3), 415-431.
Zhao, W., & Zheng, Y. S. (2001). A dynamic model for airline seat allocation with passenger diversion and no-shows. Transportation Science35(1), 80-98.