Joint Optimization of Star P-hub Median Problem and Seat Inventory Control Decisions Considering a Hybrid Routing Transportation System

Tikani, Hamid; Honarvar, Mahboobeh; Zare Mehrjerdi, Yahia

doi:10.22034/2016.3.06

Joint Optimization of Star P-hub Median Problem and Seat Inventory Control Decisions Considering a Hybrid Routing Transportation System

Document Type : Research Paper

Authors

Department of Industrial Engineering, Yazd University, Yazd, Iran

10.22034/2016.3.06

Abstract

In this paper, we study the problem of integrated capacitated hub location problem and seat inventory control considering concept and techniques of revenue management. We consider an airline company maximizes its revenue by utilizing the best network topology and providing proper booking limits for all itineraries and fare classes. The transportation system arises in the form of a star/star network and includes both hub-stop and non-stop flights. This problem is formulated as a two-stage stochastic integer program with mixed-integer recourse. We solve various instances carried out from the Turkish network data set. Due to the NP-hardness of the problem, we propose a hybrid optimization method, consisting of an evolutionary algorithm based on genetic algorithm and exact solution. The quality of the solutions found by the proposed meta-heuristic is compared with the original version of GA and the mathematical programming model. The results obtained by the proposed model imply that integrating hub location and seat inventory control problem would help to increase the total revenue of airline companies. Also, in the case of serving non-stop flights, the model can provide more profit by employing less number of hubs.

Keywords

Main Subjects

logistics, transportation, distribution, and materials Handling

References

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 Management, Vol. 47, pp. 172-178.

Alumur, S. A., Nickel, S., & Saldanha-da-Gama, F. (2012). Hub location under uncertainty. Transportation Research Part B: Methodological, Vol. 46(4), pp. 529-543.

Belobaba, P. (1987). Air travel demand and airline seat inventory management. Cambridge, MA: Flight Transportation Laboratory, Massachusetts Institute of Technology,[1987].

Belobaba, P. P. (1989). OR practice—application of a probabilistic decision model to airline seat inventory control. Operations Research, Vol. 37(2), pp. 183-197.

Bertsimas, D., & De Boer, S. (2005). Simulation-based booking limits for airline revenue management. Operations Research, Vol. 53(1), pp. 90-106.

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 Research, Vol. 41(1), pp. 127-137.

Campbell, J. F. (1994). Integer programming formulations of discrete hub location problems. European Journal of Operational Research, Vol. 72(2), pp. 387-405.

Campbell, J. F. (1996). Hub location and the p-hub median problem. Operations Research, 44(6), pp. 923-935.

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 Management, Vol. 1(1), pp. 97-128.

Contreras, I., Cordeau, J. F., & Laporte, G. (2011). Stochastic uncapacitated hub location. European Journal of Operational Research, Vol. 212(3), pp. 518-528.

Contreras, I., Fernández, E., & Marín, A. (2009). Tight bounds from a path based formulation for the tree of hub location problem. Computers & Operations Research, Vol. 36(12), pp. 3117-3127.

Cook, G. N., & Goodwin, J. (2008). Airline Networks: A Comparison of Hub-and-Spoke and Point-to-Point SystemsAirline Networks: A Comparison of Hub-and-Spoke and Point-to-Point Systems. Journal of Aviation/Aerospace Education & Research, 17(2).

Curry, R. E. (1990). Optimal airline seat allocation with fare classes nested by origins and destinations. transportation science, Vol. 24(3), pp. 193-204.

De Boer, S. V., Freling, R., & Piersma, N. (2002). Mathematical programming for network revenue management revisited. European Journal of Operational Research, Vol. 137(1), pp. 72-92.

Ernst, A. T., & Krishnamoorthy, M. (1996). Efficient algorithms for the uncapacitated single allocation p-hub median problem. Location science, Vol. 4(3), pp. 139-154.

Feng, Y., & Xiao, B. (2001). A dynamic airline seat inventory control model and its optimal policy. Operations Research, Vol. 49(6), pp. 938-949.

Glover, F., Glover, R., Lorenzo, J., & McMillan, C. (1982). The passenger-mix problem in the scheduled airlines. Interfaces, Vol. 12(3), pp. 73-80.

Holland, J. H. (1975). Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. U Michigan Press.

Jeng, C. Y. (1987). Routing strategies for an idealized airline network.

Kara, B. Y., & Tansel, B. C. (2000). On the single-assignment p-hub center problem. European Journal of Operational Research, Vol. 125(3), pp. 648-655.

Kratica, J., Milanović, M., Stanimirović, Z., & Tošić, D. (2011). An evolutionary-based approach for solving a capacitated hub location problem. Applied Soft Computing, Vol. 11(2), pp. 1858-1866.

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 Research, Vol. 182(1), pp. 15-28.

Labbé, M., & Yaman, H. (2004). Projecting the flow variables for hub location problems. Networks, Vol. 44(2), pp. 84-93.

Labbé, M., & Yaman, H. (2008). Solving the hub location problem in a star–star network. Networks, Vol. 51(1), pp. 19-33.

Labbé, M., Yaman, H., & Gourdin, E. (2005). A branch and cut algorithm for hub location problems with single assignment. Mathematical programming, Vol. 102(2), pp. 371-405.

Lee, T. C., & Hersh, M. (1993). A model for dynamic airline seat inventory control with multiple seat bookings. Transportation Science, Vol. 27(3), pp. 252-265.

Lin, C. C., Lin, J. Y., & Chen, Y. C. (2012). The capacitated p-hub median problem with integral constraints: An application to a Chinese air cargo network. Applied Mathematical Modelling, Vol. 36(6), pp. 2777-2787.

Littlewood, K. (1972). Forecasting and Control of Passengers. In 12th AGIFORS Symposium Proceedings, Vol. 95, pp. 128.

Marianov, V., & Serra, D. (2003). Location models for airline hubs behaving as M/D/c queues. Computers & Operations Research, Vol. 30(7), pp. 983-1003.

Mayer, G., & Wagner, B. (2002). HubLocator: an exact solution method for the multiple allocation hub location problem. Computers & Operations Research, Vol. 29(6), pp. 715-739.

McGill, J. I., & Van Ryzin, G. J. (1999). Revenue management: Research overview and prospects. Transportation science, Vol. 33(2), pp. 233-256.

Mendes, J. J. D. M., Gonçalves, J. F., & Resende, M. G. (2009). A random key based genetic algorithm for the resource constrained project scheduling problem. Computers & Operations Research, Vol. 36(1), pp. 92-109.

Mou, D., & Wang, X. (2014). Uncertain Programming for Network Revenue Management. Mathematical Problems in Engineering, 2014.

O'kelly, M. E. (1987). A quadratic integer program for the location of interacting hub facilities. European Journal of Operational Research, Vol. 32(3), pp. 393-404.

Robinson, L. W. (1995). Optimal and approximate control policies for airline booking with sequential nonmonotonic fare classes. Operations Research, Vol. 43(2), pp. 252-263.

Sim, T., Lowe, T. J., & Thomas, B. W. (2009). The stochastic p-hub center problem with service-level constraints. Computers & Operations Research, Vol. 36(12), pp. 3166-3177.

Taguchi G, Chowdhury S, Taguchi S. Robust engineering. McGraw-Hill Professional; 2000.

Talluri, K. T., & Van Ryzin, G. J. (2004). The theory and practice of revenue management. Number 68 in International series in operations research and management science.

Tan, P. Z., & Kara, B. Y. (2007). A hub covering model for cargo delivery systems. Networks, Vol. 49(1), pp. 28-39.

Van Ryzin, G., & Vulcano, G. (2008). Simulation-based optimization of virtual nesting controls for network revenue management. Operations Research, Vol. 56(4), pp. 865-880.

Wang, K. (1983). Optimum seat allocation for multi-leg flights with multiple fare types. In AGIFORS PROCEEDINGS.

Wollmer, R. D. (1986). A hub-spoke seat management model. Unpublished Internal Report, Mc Donnell Douglas Corporation, Long Beach, CA.

Wollmer, R. D. (1992). An airline seat management model for a single leg route when lower fare classes book first. Operations Research, Vol. 40(1), pp. 26-37.

Yaman, H. (2008). Star p-hub median problem with modular arc capacities.Computers & Operations Research, Vol. 35(9), pp. 3009-3019.

Yaman, H. (2011). Allocation strategies in hub networks. European Journal of Operational Research, Vol. 211(3), pp. 442-451.

Yaman, H., & Elloumi, S. (2012). Star p-hub center problem and star p-hub median problem with bounded path lengths. Computers & Operations Research, Vol. 39(11), pp. 2725-2732.

Yang, T. H. (2009). Stochastic air freight hub location and flight routes planning. Applied Mathematical Modelling, Vol. 33(12), pp. 4424-4430.

Yang, T. H. (2010). A two-stage stochastic model for airline network design with uncertain demand. Transportmetrica, Vol. 6(3), pp. 187-213.

Yoon, M. G., Lee, H. Y., & Song, Y. S. (2012). Linear approximation approach for a stochastic seat allocation problem with cancellation & refund policy in airlines. Journal of Air Transport Management, Vol. 23, pp. 41-46.

Zade, A. E., Sadegheih, A., & Lotfi, M. M. (2014). A modified NSGA-II solution for a new multi-objective hub maximal covering problem under uncertain shipments. Journal of Industrial Engineering International, Vol. 10(4), pp.185-197.