Document Type : Research Paper
Authors
1 Department of Industrial Engineering, Faculty of Engineering, Kharazmi University, Tehran, Iran.
2 Department of Systems and Industrial Engineering University of Arizona, Tucson, Arizona, USA.
3 Department of System Science and Industrial Engineering, Binghamton University, Binghamton, New York, USA.
Abstract
Hub location problems (HLP) have multiple applications in logistic systems, the airways industry, supply chain network design, and telecommunication. In the HLP, the selected nodes as hubs perform the principal role in processing the inflow arising from other nodes. So, congestion would be inevitable at hub nodes. This paper considers a p-hub median problem with multiple hub node servers delivering service at variable rates. Since the service rates are limited and variable, a queue is formed at each hub server. To tackle this problem, we developed a mixed-integer linear programming model that optimizes the selected hub nodes to reduce congestion under an allowable defined queue length at each server and minimize the total costs of the model, including transportation and hub establishment costs. We utilized the Civil Aeronautics Board (CAB) dataset containing 25 USA cities, which is a valuable source for designing numerical examples in the HLP, to prove the model's efficiency. The results obtained from the designed sample problems show that strategic decisions on defining the number of hubs and maximum acceptable queue length at each hub server will significantly impact the hub location network design.
Keywords
Main Subjects
- Campbell, J.F. (1994). Integer programming formulations of discrete hub location problems. European journal of operational research, 72(2), 387–405. https://doi.org/10.1016/0377-2217(94)90318-2
- O'kelly, M. E. (1986). The location of interacting hub facilities. Transportation science, 20(2), 92-106. https://doi.org/10.1287/trsc.20.2.92
- Klincewicz, J.G. (1996). A dual algorithm for the uncapacitated hub location problem. Location science, 4(3), 173-184. https://doi.org/10.1016/S0966-8349(96)00010-1
- Skorin-Kapov, D., Skorin-Kapov, J., & O’Kelly, M. (1996). Tight linear programming relaxations of uncapacitated p-hub median problems. European journal of operational research, 94(3), 582–593. https://doi.org/10.1016/0377-2217(95)00100-X
- Ernst, A.T., & Krishnamoorthy, M. (1998). An exact solution approach based on shortest-paths for p-hub median problems. Informs journal on computing, 10(2), 149–162. https://doi.org/10.1287/ijoc.10.2.149
- Mayer, G., & Wagner, B. (2002). Hub locator: an exact solution method for the multiple-allocation hub location problems. Computers and operations research, 29(6), 715–739. https://doi.org/10.1016/S0305-0548(01)00080-6
- Hamacher, H.W., Labbé, M., Nickel, S., & Sonneborn, T. (2004). Adapting polyhedral properties from facility to hub location problems. Discrete applied mathematics, 145(1), 104–116. https://doi.org/10.1016/j.dam.2003.09.011
- Marı́n, A., Cánovas, L., & Landete, M. (2006). New formulations for the uncapacitated multiple-allocation hub location problem. European journal of operational research, 172(1), 274–292. https://doi.org/10.1016/j.ejor.2004.09.047
- Marı́n, A. (2005). Uncapacitated euclidean hub location: strengthened formulation new facets and a relax-and-cut algorithm. Journal of global optimization, 33, 393–422. https://doi.org/10.1007/s10898-004-6099-4
- Cánovas, L., García, S., & Marín, A. (2007). Solving the uncapacitated multiple-allocation hub location problem by means of a dual ascent technique. European journal of operational research, 179(3), 990–1007. https://doi.org/10.1016/j.ejor.2005.08.028
- O'Kelly, M. E. (1987). A quadratic integer program for the location of interacting hub facilities. European journal of operational research, 32(3), 393–404. https://doi.org/10.1016/S0377-2217(87)80007-3
- Klincewicz, J.G. (1991). Heuristics for the p-hub location problem. European journal of operational research, 53(1), 25–37. https://doi.org/10.1016/0377-2217(91)90090-I
- Aykin, T. (1995). Networking policies for hub-and-spoke systems with application to the air transportation system. Transportation science, 29(3), 201–221. https://doi.org/10.1287/trsc.29.3.201
- Aykin, T. (1994). Lagrangian relaxation based approaches to capacitated hub-and-spoke network design problem. European journal of operational research, 79(3), 501–523.
- Ebery, J., Krishnamoorthy, M., Ernst, A., & Boland, N. (2000). The capacitated multiple-allocation hub location problems: formulations and algorithms. European journal of operational research, 120(3), 614–631. https://doi.org/10.1016/S0377-2217(98)00395-6
- Boland, N., Krishnamoorthy, M., Ernst, A.T., & Ebery, J. (2004). Preprocessing and cutting for multiple-allocation hub location problems. European journal of operational research, 155(3), 638–653. https://doi.org/10.1016/S0377-2217(03)00072-9
- Marı́n, A. (2005). Formulating and solving the splittable capacitated multiple-allocation hub location problems. Computers and operations research, 32(12), 3093–3109. https://doi.org/10.1016/j.cor.2004.04.008
- Ernst, A.T., & Krishnamoorthy, M. (1999). Solution algorithms for the capacitated single allocation hub location problem. Annals of operations research, 86, 141–159. https://doi.org/10.1023/A:1018994432663
- Labbé, M., Yaman, H., & Gourdin, E. (2005). A branch and cut algorithm for hub location problems with single assignment. Mathematical programming, 102, 371–405. https://doi.org/10.1007/s10107-004-0531-x
- Contreras, I., Díaz, J.A., & Fernández, E. (2008). Branch and price for large-scale capacitated hub location problems with single assignment. Informs journal on computing, 23(1), 41-55. https://doi.org/10.1287/ijoc.1100.0391
- Contreras, I., Díaz, J.A., & Fernández, E. (2009). Lagrangian relaxation for the capacitated hub location problem with single assignment. Operations research spectrum, 31, 483–505. https://doi.org/10.1007/s00291-008-0159-y
- Aguilar, I. C. (2009). Network hub location: models, algorithms, and related problems(Doctoral dissertation, Universitat Politècnica de Catalunya (UPC)). https://dialnet.unirioja.es/servlet/tesis?codigo=21447
- Campbell, J. F., Ernst, A. T., & Krishnamoorthy, M. (2002). Hub location problems. In Facility location: applications and theory (pp. 373–407). Berlin Heidelberg: Springer.
- Alumur, S., & Kara, B.Y. (2008). Network hub location problems: the state of the art. European journal of operational research, 190 (1), 1–21. https://doi.org/10.1016/j.ejor.2007.06.008
- Ebery, J. (1999). Solving large single-allocation p-hub problems with two or three hubs. European journal of operational research, 128(2), 447-458. https://dx.doi.org/10.1016/S0377-2217(99)00370-7
- Adler, N., &Hashai.N. (2005). Effect of open skies in the Middle East region. Transportation research part a: policy and practice, 39(10), 878–894. https://doi.org/10.1016/j.tra.2005.04.001
- O’Kelly, M.E., Bryan, D., Skorin-Kapov, D., & Skorin-Kapov, J. (1996). Hub network with single and multiple allocation: a computational study. Location science, 4(3), 125–38. https://doi.org/10.1016/S0966-8349(96)00015-0
- Riedi, R.H., Crouse, M.S., Ribeiro, V.J., & Baraniuk, R.G. (1999). A multiracial wavelet model with application to network traffic. IEEE Transactions on information theory, 45(3), 992-1018. https://doi.org/10.1109/18.761337
- Ashour, M., & Le-Ngoc, T. (2003, December). Priority queuing of long-range dependent traffic. GLOBECOM'03. IEEE global telecommunications conference (IEEE Cat. No. 03CH37489)(pp. 3025-3029). IEEE. https://doi.org/10.1109/GLOCOM.2003.1258791
- Marianov, V., & Serra, D. (2003). Location models for airline hubs behaving as M/D/c queues. Computers and operations research, 30(7), 983–1003. https://doi.org/10.1016/S0305-0548(02)00052-7
- Elhedhli, S., & Xiaolong Hu, F. (2005). Hub-and-spoke network design with congestion. Computers & operations research, 32(6), 1615–1632. https://doi.org/10.1016/j.cor.2003.11.016
- Mohammadi, M., Jolai, F., & Rostami, H. (2011). An M/M/c queue model for hub covering location problem. Mathematical and computer modelling, 54(11-12), 2623–2638.
- Rahimi, Y., Tavakkoli-Moghaddam, R., Mohammadi, M., & Sadeghi, M. (2016). Multi-objective hub network design under uncertainty considering congestion: an 𝑀∕𝑀∕𝑐∕𝐾 queue system. Applied mathematical modelling, 40(5-6), 4179–4198. https://doi.org/10.1016/J.APM.2015.11.019
- Zhalechian, M., Tavakkoli-Moghaddam, R., & Rahimi, Y. (2017). A self-adaptive evolutionary algorithm for a fuzzy multi-objective hub location problem: an integration of responsiveness and social responsibility. Engineering applications of artificial intelligence, 62, 1-16. https://doi.org/10.1016/j.engappai.2017.03.006
- Khodemoni-yazdi, M., Tavakkoli-Moghaddam, R., Bashiri, M., & Rahimi, Y. (2019). Solving a new bi-objective hierarchical hub location problem with an M∕M∕c queuing framework. Engineering applications of artificial intelligence, 78, 53-70. https://doi.org/10.1016/j.engappai.2018.10.004
- Karimi-Mamaghan, M., Mohammadi, M., Pirayesh, A., Karimi-Mamaghan, A.M., & Irani, H. (2020). Hub-and-spoke network design under congestion: a learning based metaheuristic. Transportation research part e: logistics and transportation review, 142, 102069. https://doi.org/10.1016/j.tre.2020.102069
- Bütün, C., Petrovic, S., & Muyldermans, L. (2021). The capacitated directed cycle hub location and routing problem under congestion. European journal of operational research, 292(2), 714-734.
- Alumur, S. A., Campbell, J. F., Contreras, I., Kara, B. Y., Marianov, V., & O’Kelly, M. E. (2021). Perspectives on modeling hub location problems. European journal of operational research, 291(1), 1-17.
- Najy, W., & Diabat, A. (2020). Benders decomposition for multiple-allocation hub-and-spoke network design with economies of scale and node congestion. Transportation research part b: methodological, 133, 62-84.
- Alumur, S.A., Nickel, S., Rohrbeck, B., & Saldanha-da-Gama, F. (2018). Modeling congestion and service time in hub location problems. Applied mathematical modelling, 55, 13-32.
- Sadeghi, M., Tavakkoli-Moghaddam, R., & Babazadeh, R. (2018). An efficient artificial bee colony algorithm for a reliable p-hub covering location problem with travel time budget. International journal of industrial engineering: theory, applications and practice, 25(1), 40–53.
- Zhalechian, M., Tavakkoli-Moghaddam, R., Rahimi, Y., & Jolai, F. (2017). An interactive possibilistic programming approach for a multi-objective hub location problem: economic and environmental design. Applied soft computing, 52, 699-713.
- Korani, E., & Eydi, A. (2021). Bi-level programming model and KKT penalty function solution approach for reliable hub location problem. Expert systems with applications, 184, 115505. https://doi.org/10.1016/j.eswa.2021.115505
- Mahmoodjanloo, M., Tavakkoli-Moghaddam, R., Baboli, A., & Jamiri, A. (2020). A multi-modal competitive hub location pricing problem with customer loyalty and elastic demand. Computers & operations research, 123, https://doi.org/10.1016/j.cor.2020.105048
- Golestani, M., Moosavirad, S.H., Asadi, Y., & Biglari, S. (2021). A multi-objective green hub location problem with multi item-multi temperature joint distribution for perishable products in cold supply chain. Sustainable production and consumption, 27, 1183-1194.
- Alizadeh Firozi, M., Kiani, V., & Karimi, H. (2022). Improved genetic algorithm with diversity and local search for uncapacitated single allocation hub location problem. Journal of decisions and operations research, 6(4), 536-552.
- Zahiri, B., Mousazadeh, M., & Bozorgi-Amiri, A. (2014). A robust stochastic programming approach for blood collection and distribution network design. International journal of research in industrial engineering, 3(2), 1-11.
- Farrokhi-Asl, H., & Tavakkoli-Moghaddam, R. (2016). Solving a bi-objective transportation vehicle routing problem for waste collection by a new hybrid algorithm. International journal of research in industrial engineering, 5-1(4), 16-42.
- Ghodratnama, R., Tavakkoli-Moghaddam, R., & Azaron, A. (2015). Robust and fuzzy goal programming optimization approaches for a novel multi-objective hub location-allocation problem: a supply chain overview. Applied soft computing, 37, 255-276. https://doi.org/10.1016/j.asoc.2015.07.038
)