Chance-constrained programming and robust optimization approaches for uncertain hub location problems in a cooperative competitive environment

Document Type : Article


1 Department of Industrial Engineering, South Tehran Branch, Islamic Azad University, Tehran, Iran

2 Department of Industrial Engineering, Karaj Branch, Islamic Azad University, Karaj, P.O. Box 31485/313, Iran


In this paper, we propose an integer programming model for Capacitated Multi-Allocation Median Hub Location Problem, which is applied in a both cooperative and competitive environment among airlines. We divide the hubs into six independent categories by comparing the parameters of the ticket price, travel time, and the service quality of hub airports are controlled by follower and leader airlines. In this paper, the degree of importance of time and cost parameters determine by a multivariate Lagrange interpolation method, which can play an important role in allocating travelers to follower airline hubs. Then, based on the seasonal demand of travelers, we consider travel demand as uncertain parameters. To determine the deterministic equivalent forms of this category of hub location models, robust optimization method and chance-constrained programming model are used. Finally, the proposed model test in a case study. Based on the results, a coalition of follower airlines can absorb nearly 2% of travelers of leader airline due to lower travel cost and travel time compared to that of leader airline.


1. Rodriguez-Martin, I. and Salazar-Gonzalez, J. "Solving a capacitated hub location problem", Eur. J. Oper. Res., 184(2), pp. 468-479 (2008).
2. Campbell, J.F. "Hub location for time definite  ransportation", Comput. Oper. Res., 36(12), pp. 3107- 3116 (2009).
3. Yaman, H., Kara, B.Y., and Tansel, B.C. "The latest arrival hub location problem for cargo delivery systems with stopovers", Transport. Res. B-Meth., 41(8), pp. 906-919 (2007).
4. Van Belle, J., Valckenaers, P., and Cattrysse, D. "Cross-docking: State of the art", Omega., 40(6), pp. 827-846 (2012).
5. Campbell, J.F. "Integer programming formulations of discrete hub location problems", Eur. J. Oper. Res., 72(2), pp. 387-405 (1994).
6. Hakimi, S.L. "Optimum distribution of switching centers in a communication network and some related graph theoretic problems", Oper. Res., 13(3), pp. 462- 475 (1965).
7. Marianov, V., Serra, D., and ReVelle, C. "Location of hubs in a competitive environment", Eur. J. Oper. Res., 114(2), pp. 363-371 (1999).
8. Wagner, B. "A note on "location of hubs in a competitive environment", Eur. J. Oper. Res., 184(1), pp. 57-62 (2008). 
9. Soyster, A.L. "Convex programming with set-inclusive constraints and applications to inexact linear programming", Oper. Res., 21(5), pp. 1154-1157 (1973).
10. Ben-Tal, A. and Nemirovski, A. "Robust solutions of uncertain linear programs", Oper. Res. Let., 25(1), pp. 1-13 (1999).
11. Bertsimas, D. and Sim, M. "The price of robustness", Oper. Res., 52(1), pp. 35-53 (2004).
12. Nourzadeh, F., Ebrahimnejad, S., Khalili-Damghani, K., et al. "Forecasting the international air passengers of Iran using an artificial neural network", Int. J. Ind. Syst. Eng., 34(4), pp. 562-581 (2020).
13. Sasaki, M. and Fukushima, M. "Stackelberg hub location problem", J. Oper. Res. Soc. JPN., 44(4), pp. 390-402 (2001).
14. Sasaki, M. "Hub network design model in a competitive environment with  flow threshold", J. Oper. Res. Soc. JPN., 48(2), pp. 158-171 (2005).
15. Sasaki, M., Campbell, J.F., Krishnamoorthy, M., et al. "Designing hub and spoke transportation systems for a competitive environment", In Int. Con. Ind. Eng. Syst. Manage., pp. 13-15 (2009).
16. Eiselt, H.A. and Marianov, V. "A conditional p-hub location problem with attraction functions", Comput. Oper. Res., 36(12), pp. 3128-3135 (2009).
17. Lin, M.H. "Strategic airline alliances and endogenous Stackelberg equilibria", Transport. Res. E- Log., 40(5), pp. 357-384 (2004).
18. Zou, L. and Chen, X. "The effect of code-sharing alliances on airline profitability", J. Air. Transp. Manag., 58, pp. 50-57 (2017).
19. Yimga, J.O. "Airline code-sharing and its effects on on-time performance", J. Air. Transp. Manag., 58, pp. 76-90 (2017).
20. Adibi, A. and Razmi. J. "2-stage stochastic programming approach for hub location problem under uncertainty: A case study of air network of Iran", J. Air. Transp. Manag., 47, pp. 172-178 (2015).
21. Boukani, F.H., Moghaddam, B.F., and Pishvaee, M.S. "Robust optimization approach to capacitated single and multiple allocation hub location problems", Comput. Appl. Math., 35(1), pp. 45-60 (2016).
22. Tikani, H., Honarvar, M., and Mehrjerdi, Y.Z. "Developing an integrated hub location and revenue management model considering multi-classes of customers in the airline industry", Comput. Appl. Math., 37(3), pp. 3334-3364 (2018).
23. Nikoofal, M.E. and Sadjadi, S.J. "A robust optimization model for p-median problem with uncertain edge lengths", Int. J. Adv. Manuf. Tech., 50(1-4), pp. 391- 397 (2010).
24. Ghaffari-Nasab, N., Ghazanfari, M., and Teimoury, E. "Robust optimization approach to the design of huband- spoke networks", Int. J. Adv. Manuf. Tech., 76(5- 8), pp. 1091-1110 (2015).
25. Zetina, C.A., Contreras, I., Cordeau, J.F., et al. "Robust uncapacitated hub location", Transport. Res. B-Meth., 106, pp. 393-410 (2017).
26. Charnes, A., Cooper, W.W., and Symonds, G.H. "Cost horizons and certainty equivalents: an approach to stochastic programming of heating oil", Manag. Sci., 4(3), pp. 235-263 (1958).
27. Gao, Y. and Qin, Z. "A chance constrained programming approach for uncertain p-hub center location problem", Comput. Ind. Eng., 102, pp. 10-20 (2016).
28. Farina, M., Giulioni, L., and Scattolini, R. "Stochastic linear model predictive control with chance constraints-a review", J. Process. Contr., 44(1), pp. 53-67 (2016).
29. Tan, X., Gong, Z., Chiclana, F., et al. "Consensus modeling with cost chance constraint under uncertainty opinions", Appl. Soft. Comput., 67(1), pp. 721- 727 (2017).
30. Elci, O., Noyan, N., and Bulbul, K. "Chanceconstrained stochastic programming under variable reliability levels with an application to humanitarian relief network design", Comput. Oper. Res., 96(1), pp. 91-107 (2018).
31. Saniee, K. "A simple expression for multivariate Lagrange interpolation", SIAM. Undergrad. Res. Online., 1(1), pp. 1-9 (2008).
32. Charnes, A. and Cooper, W.W. "Chance-constrained programming", Manag. Sci., 6(1), pp. 73-79 (1959).
33. Di Bucchianico, A., Coefficient of Determination (R2), John Wiley & Sons (2008).
34. Houda, M. "Comparison of approximations in stochastic and robust optimization programs", In Prague Stochastics, pp. 418-425 (2006).