Robust uncapacitated multiple allocation hub location problem under demand uncertainty: minimization of cost deviations

Subject Areas : Mathematical Optimization

Aleksejs Lozkins ¹ , Mikhail Krasilnikov ² , Vladimir Bure ³

1 - Department of Mathematical Game Theory and Statistical Decisions, Saint Petersburg State University, 7-9, Universitetskaya nab., St. Petersburg, Russian Federation, 199034|Department of Mathematical optimization and Modeling, Ltd. BIA-Technologies, 94, Moskovskiy avenue, St. Petersburg, Russian Federation, 196084
2 - Department of Mathematical optimization and Modeling, Ltd. BIA-Technologies, 94, Moskovskiy avenue, St. Petersburg, Russian Federation, 196084
3 - Department of Mathematical Game Theory and Statistical Decisions, Saint Petersburg State University, 7-9, Universitetskaya nab., St. Petersburg, Russian Federation, 199034

Received: 2020-10-09 Accepted : 2020-10-09 Published : 2020-09-01

Keywords: Benders decomposition, Pareto, Stochastic programming, optimal cuts, Hub location problem, Absolute deviation · Robust solution,

Abstract :

The hub location–allocation problem under uncertainty is a real-world task arising in the areas such as public and freight transportation and telecommunication systems. In many applications, the demand is considered as inexact because of the forecasting inaccuracies or human’s unpredictability. This study addresses the robust uncapacitated multiple allocation hub location problem with a set of demand scenarios. The problem is formulated as a nonlinear stochastic optimization problem to minimize the hub installation costs, expected transportation costs and expected absolute deviation of transportation costs. To eliminate the nonlinearity, the equivalent linear problem is introduced. The expected absolute deviation is the robustness measure to derive the solution close to each scenario. The robust hub location is assumed to deliver the least costs difference across the scenarios. The number of scenarios increases size and complexity of the task. Therefore, the classical and improved Benders decomposition algorithms are applied to achieve the best computational performance. The numerical experiment on CAB and AP dataset presents the difference of resulting hub networks in stochastic and robust formulations. Furthermore, performance of two Benders decomposition strategies in comparison with Gurobi solver is assessed and discussed.

References:

Alumur SA, Nickel S, Saldanha-da Gama F (2012) Hub location under uncertainty. Transp Res Part B Methodol 46(4):529–543
Beasley JE (1990) Or-library: distributing test problems by electronic mail. J Oper Res Soc 41(11):1069–1072
Benders JF (1962) Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik 4(1):238–252
Boukani FH, Moghaddam BF, Pishvaee MS (2016) Robust optimization approach to capacitated single and multiple allocation hub location problems. Comput Appl Math 35(1):45–60
Campbell JF, O’Kelly ME (2012) Twenty-fve years of hub location research. Transp Sci 46(2):153–169
Contreras I (2015) Hub location problems. Location science. Springer, Berlin, pp 311–344
Contreras I, Cordeau JF, Laporte G (2011) Stochastic uncapacitated hub location. Eur J Oper Res 212(3):518–528
de Camargo RS, Miranda G Jr, Luna HP (2008) Benders decomposition for the uncapacitated multiple allocation hub location problem. Comput Oper Res 35(4):1047–1064
de Camargo RS, de Miranda Jr G, Ferreira RP (2011) A hybrid outerapproximation/benders decomposition algorithm for the single allocation hub location problem under congestion. Oper Res Lett 39(5):329–337
de Sá EM, de Camargo RS, de Miranda G (2013) An improved benders decomposition algorithm for the tree of hubs location problem. Eur J Oper Res 226(2):185–202
de Sá EM, Morabito R, de Camargo RS (2018) Benders decomposition applied to a robust multiple allocation incomplete hub location problem. Comput Oper Res 89:31–50
Hamacher HW, Labbé M, Nickel S, Sonneborn T (2004) Adapting polyhedral properties from facility to hub location problems. Discrete Appl Math 145(1):104–116
Kahag MR, Niaki STA, Seifbarghy M, Zabihi S (2019) Bi-objective optimization of multi-server intermodal hub-location-allocation problem in congested systems: modeling and solution. J Ind Eng Int 15(2):221–248
Magnanti TL, Wong RT (1981) Accelerating benders decomposition: algorithmic enhancement and model selection criteria. Oper Res 29(3):464–484
Marianov V, Serra D (2003) Location models for airline hubs behaving as m/d/c queues. Comput Oper Res 30(7):983–1003
Meraklı M, Yaman H (2016) Robust intermodal hub location under polyhedral demand uncertainty. Transp Res Part B Methodol 86:66–85
Mercier A, Cordeau JF, Soumis F (2005) A computational study of benders decomposition for the integrated aircraft routing and crew scheduling problem. Comput Oper Res 32(6):1451–1476
O’kelly ME (1986) The location of interacting hub facilities. Transp Sci 20(2):92–106
Papadakos N (2008) Practical enhancements to the Magnanti–Wong method. Oper Res Lett 36(4):444–449
Sim T, Lowe TJ, Thomas BW (2009) The stochastic p-hub center problem with service-level constraints. Comput Oper Res
36(12):3166–3177
Yahyaei M, Bashiri M (2017) Scenario-based modeling for multiple allocation hub location problem under disruption risk:
multiple cuts benders decomposition approach. J Ind Eng Int 13(4):445–453
Yang TH (2009) Stochastic air freight hub location and fight routes planning. Appl Math Model 33(12):4424–4430
Yu CS, Li HL (2000) A robust optimization model for stochastic logistic problems. Int J Prod Econ 64(1–3):385–397
Zetina CA, Contreras I, Cordeau JF, Nikbakhsh E (2017) Robust uncapacitated hub location. Transp Res Part B Methodol 106:393–410