A Robust Optimization Approach for the Hub Arc Location Problem

Subject Areas : Supply chain management and logistics

Marjan Gharavipour ¹ ( Department of Industrial Engineering & Management Systems, Amirkabir University of Technology )
Mohsen Sheikh Sajadieh ² ( تهران-دانشگاه امیرکبیر-دانشکده صنایع )
Matineh Ziari ³ ( School of Industrial Engineering, College of Engineering, University of Tehran )

Received: 2024-02-28 Accepted : 2024-04-21 Published : 2024-04-21

Keywords: Hub arc location, Isolated hub, Uncertainty, Robust Optimization, Min-Max Regret Model, Genetic Algorithm,

Abstract :

Hub networks play a crucial role in optimizing transportation flow and reducing overall costs by efficiently connecting origins and destinations through strategically placed hub nodes. The decision of hub location carries significant long-term implications and necessitates consideration of various factors within an uncertain environment. This paper addresses the hub arc location problem in hub networks, considering setup costs, isolated hubs, and uncertain flows between nodes. To tackle this challenge, a two-stage stochastic programming model is formulated to incorporate the uncertainty in flow volumes. Additionally, a robust optimization approach is proposed to enhance the resilience of hub location decisions against uncertain scenarios. The problem is solved using a tailored Genetic algorithm, which achieves optimal solutions with high quality and reasonable computational time. The results demonstrate the effectiveness of the proposed methodology in handling the uncertain nature of the hub location problem, contributing to the advancement of transportation planning and logistics optimization. The findings provide valuable insights for practical applications in real-world scenarios, offering a framework for decision-makers to make informed choices regarding hub network design and location. By integrating uncertainty and robust optimization techniques, this paper offers a comprehensive approach to address complex transportation network problems and improve overall efficiency in transportation systems.

References:

Adibi, A. and J. Razmi (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 47: 172-178.
Ahmadi, T., H. Karimi, H. Davoudpour and S. A. Hosseinijou (2015). "A robust decision-making approach for p-hub median location problems based on two-stage stochastic programming and mean-variance theory: a real case study." The International Journal of Advanced Manufacturing Technology 77: 1943-1953.
Alumur, S. A., J. F. Campbell, I. Contreras, B. Y. Kara, V. Marianov and M. E. O’Kelly (2021). "Perspectives on modeling hub location problems." European Journal of Operational Research 291(1): 1-17.
Alumur, S. A., S. Nickel and F. Saldanha-da-Gama (2012). "Hub location under uncertainty." Transportation Research Part B: Methodological 46(4): 529-543.
Bashiri, M. and S. Mehrabi (2010). Stochastic p-hub center covering problem with delivery time constraint. 2010 IEEE International Conference on Industrial Engineering and Engineering Management, IEEE.
Berman, O., Z. Drezner and G. O. Wesolowsky (2007). "The transfer point location problem." European journal of operational research 179(3): 978-989.
Campbell, J. F. (2009). "Hub location for time definite transportation." Computers & Operations Research 36(12): 3107-3116.
Campbell, J. F., A. T. Ernst and M. Krishnamoorthy (2005). "Hub arc location problems: part I—introduction and results." Management Science 51(10): 1540-1555.
Campbell, J. F., A. T. Ernst and M. Krishnamoorthy (2005). "Hub arc location problems: part II—formulations and optimal algorithms." Management Science 51(10): 1556-1571.
Campbell, J. F., G. Stiehr, A. T. Ernst and M. Krishnamoorthy (2003). "Solving hub arc location problems on a cluster of workstations." Parallel Computing 29(5): 555-574.
Chou, C.-C. (2010). "Application of FMCDM model to selecting the hub location in the marine transportation: A case study in southeastern Asia." Mathematical and computer modelling 51(5-6): 791-801.
Contreras, I., J.-F. Cordeau and G. Laporte (2011). "Stochastic uncapacitated hub location." European Journal of Operational Research 212(3): 518-528.
de Sá, E. M., R. Morabito and R. S. de Camargo (2018). "Benders decomposition applied to a robust multiple allocation incomplete hub location problem." Computers & Operations Research 89: 31-50.
Ernst, A. T. and M. Krishnamoorthy (1996). "Efficient algorithms for the uncapacitated single allocation p-hub median problem." Location science 4(3): 139-154.
Farahani, R. Z., M. Hekmatfar, A. B. Arabani and E. Nikbakhsh (2013). "Hub location problems: A review of models, classification, solution techniques, and applications." Computers & industrial engineering 64(4): 1096-1109.
Gao, Y. and Z. Qin (2016). "A chance constrained programming approach for uncertain p-hub center location problem." Computers & Industrial Engineering 102: 10-20.
Gelareh, S. and S. Nickel (2007). "A benders decomposition algorithm for single allocation hub location problem." Proceeding of GOR2007.
Ghaderi, A. and R. Rahmaniani (2016). "Meta-heuristic solution approaches for robust single allocation p-hub median problem with stochastic demands and travel times." The International Journal of Advanced Manufacturing Technology 82: 1627-1647.
Ghaffari-Nasab, N., M. Ghazanfari and E. Teimoury (2015). "Robust optimization approach to the design of hub-and-spoke networks." The International Journal of Advanced Manufacturing Technology 76: 1091-1110.
Ghaffari–Nasab, N., M. Ghazanfari, A. Saboury and M. Fathollah (2015). "The single allocation hub location problem: a robust optimisation approach." European Journal of Industrial Engineering 9(2): 147-170.
Ghaffarinasab, N. (2018). "An efficient matheuristic for the robust multiple allocation p-hub median problem under polyhedral demand uncertainty." Computers & Operations Research 97: 31-47.
Ghaffarinasab, N. (2022). "Stochastic hub location problems with Bernoulli demands." Computers & Operations Research 145: 105851.
Ghaffarinasab, N. and B. Y. Kara (2022). "A conditional β-mean approach to risk-averse stochastic multiple allocation hub location problems." Transportation Research Part E: Logistics and Transportation Review 158: 102602.
Habibzadeh Boukani, F., B. Farhang Moghaddam and M. S. Pishvaee (2016). "Robust optimization approach to capacitated single and multiple allocation hub location problems." Computational and Applied Mathematics 35: 45-60.
Hamid, M., M. Bastan, M. Hamid and F. Sheikhahmadi (2019). "Solving a stochastic multi-objective and multi-period hub location problem considering economic aspects by meta-heuristics: application in public transportation." International Journal of Computer Applications in Technology 60(3): 183-202.
Hekmatfar, M. and M. Pishvaee (2009). "Hub location problem." Facility location: concepts, models, algorithms and case studies: 243-270.
Hu, Q.-M., S. Hu, J. Wang and X. Li (2021). "Stochastic single allocation hub location problems with balanced utilization of hub capacities." Transportation Research Part B: Methodological 153: 204-227.
Hult, E., H. Jiang and D. Ralph (2014). "Exact computational approaches to a stochastic uncapacitated single allocation p-hub center problem." Computational Optimization and Applications 59: 185-200.
Klincewicz, J. G. (1998). "Hub location in backbone/tributary network design: a review." Location Science 6(1-4): 307-335.
Makui, A., M. Rostami, E. Jahani and A. Nikui (2002). "A multi-objective robust optimization model for the capacitated P-hub location problem under uncertainty." Management Science Letters 2(2): 525-534.
Marianov, V. and D. Serra (2003). "Location models for airline hubs behaving as M/D/c queues." Computers & Operations Research 30(7): 983-1003.
Martins de Sá, E., I. Contreras, J.-F. Cordeau, R. Saraiva de Camargo and G. de Miranda (2015). "The hub line location problem." Transportation Science 49(3): 500-518.
Meraklı, M. and H. Yaman (2016). "Robust intermodal hub location under polyhedral demand uncertainty." Transportation Research Part B: Methodological 86: 66-85.
Miranda Junior, G. d., R. S. d. Camargo, L. R. Pinto, S. V. Conceição and R. P. M. Ferreira (2011). "Hub location under hub congestion and demand uncertainty: the Brazilian case study." Pesquisa Operacional 31: 319-349.
Mohammadi, M., F. Jolai and R. Tavakkoli-Moghaddam (2013). "Solving a new stochastic multi-mode p-hub covering location problem considering risk by a novel multi-objective algorithm." Applied Mathematical Modelling 37(24): 10053-10073.
Mohammadi, M., J. Razmi and R. Tavakkoli-Moghaddam (2013). "MULTI-OBJECTIVE INVASIVE WEED OPTIMIZATION FOR STOCHASTIC GREEN HUB LOCATION ROUTING PROBLEM WITH SIMULTANEOUS PICK-UPS AND DELIVERIES." Economic Computation & Economic Cybernetics Studies & Research 47(3).
Mohammadi, M., S. Torabi and R. Tavakkoli-Moghaddam (2014). "Sustainable hub location under mixed uncertainty." Transportation Research Part E: Logistics and Transportation Review 62: 89-115.
O’Kelly, M. E. and D. Bryan (1998). "Hub location with flow economies of scale." Transportation research part B: Methodological 32(8): 605-616.
Qin, Z. and Y. Gao (2017). "Uncapacitated p-hub location problem with fixed costs and uncertain flows." Journal of Intelligent Manufacturing 28(3): 705-716.
Rahmaniani, R., A. Ghaderi, N. Mahmoudi and F. Barzinepour (2013). "Stochastic p-robust uncapacitated multiple allocation p-hub location problem." International Journal of Industrial and Systems Engineering 14(3): 296-314.
Rahmati, R., H. Neghabi, M. Bashiri and M. Salari (2023). "Stochastic regional-based profit-maximizing hub location problem: a sustainable overview." Omega: 102921.
Ramos, C., R. Ramos and T. Ramos (2004). Solving a stochastic model for the hub location problem. Proceedings of the 4th WSEAS International Conference on Applied Informatics and Communications.
Ravelo, S. V. (2021). "Minimum constellation covers: hardness, approximability and polynomial cases." Journal of Combinatorial Optimization 41: 603-624.
Rostami, B., N. Kämmerling, J. Naoum-Sawaya, C. Buchheim and U. Clausen (2021). "Stochastic single-allocation hub location." European Journal of Operational Research 289(3): 1087-1106.
Rostami, M., E. Farahani and D. Moradinezhad (2012). "A stochastic capacitated p-hub location problem: A case study of iran." Journal of American Science 8(11): 620-628.
Sasaki, M., J. F. Campbell, A. T. Ernst and M. Krishnamoorthy (2009). Hub arc location with competition. Technical Report.
Sener, N. and O. Feyzioglu (2023). "Multiple allocation hub covering flow problem under uncertainty." Annals of Operations Research 320(2): 975-997.
Shahabi, M. and A. Unnikrishnan (2014). "Robust hub network design problem." Transportation Research Part E: Logistics and Transportation Review 70: 356-373.
Shang, X., K. Yang, W. Wang, W. Wang, H. Zhang and S. Celic (2020). "Stochastic hierarchical multimodal hub location problem for cargo delivery systems: Formulation and algorithm." IEEE Access 8: 55076-55090.
Taherkhani, G., S. A. Alumur and M. Hosseini (2021). "Robust stochastic models for profit-maximizing hub location problems." Transportation science 55(6): 1322-1350.
Talbi, E.-G. and R. Todosijević (2017). "The robust uncapacitated multiple allocation p-hub median problem." Computers & Industrial Engineering 110: 322-332.
Wang, J. and Z. Qin (2020). "Chance constrained programming models for uncertain hub covering location problems." Soft Computing 24(4): 2781-2791.
Wang, S., Z. Chen and T. Liu (2020). "Distributionally robust hub location." Transportation Science 54(5): 1189-1210.
Wang, T., Q. Meng, B. Niu and Z. Tan (2013). Hub-and-Spoke Liner Shipping Network Design with Demand Uncertainty. International Forum on Shipping, Ports and Airports (IFSPA) 2013: Trade, Supply Chain Activities and Transport: Contemporary Logistics and Maritime IssuesHong Kong Polytechnic University.
Yang, K., Y. Liu and X. Zhang (2011). Stochastic p-hub center problem with discrete time distributions. Advances in Neural Networks–ISNN 2011: 8th International Symposium on Neural Networks, ISNN 2011, Guilin, China, May 29–June 1, 2011, Proceedings, Part II 8, Springer.
Yang, T.-H. (2009). "Stochastic air freight hub location and flight routes planning." Applied Mathematical Modelling 33(12): 4424-4430.
Zetina, C. A., I. Contreras, J.-F. Cordeau and E. Nikbakhsh (2017). "Robust uncapacitated hub location." Transportation Research Part B: Methodological 106: 393-410.
Zhai, H., Y.-K. Liu and K. Yang (2016). "Modeling two-stage UHL problem with uncertain demands." Applied Mathematical Modelling 40(4): 3029-3048.
Zhai, H., Y. Liu and W. Chen (2012). "Applying minimum-risk criterion to stochastic hub location problems." Procedia Engineering 29: 2313-2321.