Upgrading Uncapacitated Multiple Allocation P-Hub‎ ‎Median‎ ‎Problem‎ ‎Using‎ ‎Benders Decomposition Algorithm

Document Type : Original Scientific Paper

Authors

1 ‎Department of Mathematics, ‎Shahed University, ‎Tehran‎, ‎I‎. ‎R‎. ‎Iran

2 ‎Department of Computer Sciences, ‎Shahed University, ‎Tehran‎, ‎I‎. ‎R‎. ‎Iran

Abstract

‎The Hub Location Problem (HLP) is a significant problem in combinatorial optimization consisting of two main components‎: ‎location and network design‎. ‎The HLP aims to develop an optimal strategy for various applications‎, ‎such as product distribution‎, ‎urban management‎, ‎sensor network design‎, ‎computer network‎, ‎and communication network design‎. ‎Additionally‎, ‎the upgrading location problem arises when modifying specific components at a cost is possible‎. ‎This paper focuses on upgrading the uncapacitated multiple allocation p-hub median problem (u-UMApHMP)‎, ‎where a pre-determined budget and bound of changes are given‎. ‎The aim is to modify certain network parameters to identify the p-hub median that improves the objective function value concerning the modified parameters‎. ‎We propose a non-linear mathematical formulation for u-UMApHMP to achieve this goal‎. ‎Then‎, ‎we employ the McCormick technique to linearize the model‎. ‎Subsequently‎, ‎we solve the linearized model using the CPLEX solver and the Benders decomposition method‎. ‎Finally‎, ‎we present experimental results to demonstrate the effectiveness of the proposed approach‎.

Keywords

Main Subjects

References

[1] A. M. Campbell, T. J. Lowe and L. Zhang, The p-hub center allocation problem, Eur. J. Oper. Res. 176 (2007) 819 - 835, https://doi.org/10.1016/j.ejor.2005.09.024.
[2] S. Alumur and B. Y. Kara, Network hub location problems: the state of the art, Eur. J. Oper. Res. 190 (2008) 1- 21, https://doi.org/10.1016/j.ejor.2007.06.008.
[3] S. A. Alumur, J. F. Campbell, I. Contreras, B. Y. Kara, V. Marianov and M. E. O’Kelly, Perspectives on modeling hub location problems, Eur. J. Oper. Res. 291 (2021) 1 - 17, https://doi.org/10.1016/j.ejor.2020.09.039.
[4] Y. Lee, B. H. Lim and J. S. Park, A hub location problem in designing digital data service networks: Lagrangian relaxation approach, Location Science 4 (1996) 185 -194, https://doi.org/10.1016/S0966-8349(96)00009-5.
[5] R. S. Toh and R. G. Higgins, The impact of hub and spoke network centralization and route monopoly on domestic airline profitability, Transp. J. 24 (1985) 16 -27.
[6] M. Sasaki, J. F. Campbell, M. Krishnamoorthy and A. T. Ernst, A Stackelberg hub arc location model for a competitive environment, Comput. Oper. Res. 47 (2014) 27 - 41, https://doi.org/10.1016/j.cor.2014.01.009.
[7] H. Yaman, B. Y. Kara and B. Ç. Tansel, The latest arrival hub location problem for cargo delivery systems with stopovers, Transp. Res. B: Methodol. 41 (2007) 906 - 919, https://doi.org/10.1016/j.trb.2007.03.003.
[8] J. H. Lee and I. Moon, A hybrid hub-and-spoke postal logistics network with realistic restrictions: a case study of Korea Post, Expert Syst. Appl. 41 (2014) 5509 - 5519, https://doi.org/10.1016/j.eswa.2014.02.027.
[9] A. J. Goldman, Optimal locations for centers in a network, Transportation Sci. 3 (1969) 352 -360.
[10] S. L. Hakimi and S. N. Maheshwari, Optimum locations of centers in networks, Operations Res. 20 (1972) 967- 973.
[11] M. E. O’Kelly, The location of interacting hub facilities, Transp. Sci. 20 (1986) 92 -106.
[12] M. E. O’Kelly, Activity levels at hub facilities in interacting networks, Geogr. Anal. 18 (1986) 343 - 356, https://doi.org/10.1111/j.1538-4632.1986.tb00106.x.
[13] M. E. O’Kelly, A quadratic integer program for the location of interacting hub facilities, European J. Oper. Res. 32 (1987) 393 - 404, https://doi.org/10.1016/S0377-2217(87)80007-3.
[14] A. T. Ernst and M. Krishnamoorthy, Efficiant algorithms for the incapacitated single allocation p-hub median problem, Location Science 4 (1996) 139 - 154, https://doi.org/10.1016/S0966-8349(96)00011-3.
[15] A. T. Ernst and M. Krishnamoorthy, Exact and heuristic algorithms for the uncapacitated multiple allocation p-hub median problem, Eur. J. Oper. Res. 104 (1998) 100 - 112, https://doi.org/10.1016/S0377-2217(96)00340-2.
[16] X. Zhang, S. Dong and Y. Liu, P-hub median location optimization of huband-spoke air transport networks in express enterprise, Concurr. Computat. Pract. Exp. 31 (2019) p. e4981, https://doi.org/10.1002/cpe.4981.
[17] J. F. Campbell, Integer programming formulations of discrete hub location problems, Eur. J. Oper. Res. 72 (1994) 387 - 405, https://doi.org/10.1016/0377-2217(94)90318-2.
[18] D. Skorin-Kapov, J. Skorin-Kapov and M. O’Kelly, Tight linear programming relaxations of uncapacitated p-hub median problems, Eur. J. Oper. Res. 94 (1996) 582 -593, https://doi.org/10.1016/0377-2217(95)00100-X.
[19] J. F. Campbell, Hub location and P-hub median problem, Oper. Res. 44 (1996) 923 - 935.
[20] A. T. Ernst and M. Krishnamoorthy, An exact solution approach based on shortest-paths for p-hub median problems, INFORMS J. Comput. 10 (1998) 149 - 162, https://doi.org/10.1287/ijoc.10.2.149.
[21] J. G. Klincewicz, Heuristics for the p-hub location problem, Eur. J. Oper. Res. 53 (1991) 25 - 37, https://doi.org/10.1016/0377-2217(91)90090-I.
[22] J. G. Klincewicz, Avoiding local optima in the p-hub location problem using tabu search and grasp, Ann. Oper. Res. 40 (1992) 283 - 302, https://doi.org/10.1007/BF02060483.
[23] S. Abdinnour-Helm, Using simulated annealing to solve the p-hub median problem, Int. J. Phys. Distrib. Logist. Manag. 31 (2001) 203 - 220, https://doi.org/10.1108/09600030110389532.
[24] J. G. Klincewicz, Enumeration and search procedures for a hub location problem with economies of scale, Ann. Oper. Res. 110 (2002) 107 - 122, https://doi.org/10.1023/A:1020715517162.
[25] M. R. Silva and C. B. Cunha, New simple and efficient heuristics for the uncapacitated single allocation hub location problem, Comput. Oper. Res. 36 (2009) 3152 - 3165, https://doi.org/10.1016/j.cor.2008.12.019.
[26] J. F. Chen, A hybrid heuristic for the uncapacitated single allocation hub location problem, Omega 35 (2007) 211 - 220, https://doi.org/10.1016/j.omega.2005.05.004.
[27] J. Kratica, Z. Stanimirovic, D. Tosic and V. Filipovic, Two genetic algorithms for solving the uncapacitated single allocation phub median problem, Eur. J. Oper. Res. 182 (2007) 15 - 28, https://doi.org/10.1016/j.ejor.2006.06.056.
[28] H. Yaman, Star p-hub median problem with modular arc capacities, Comput. Oper. Res. 35 (2008) 3009-3019, https://doi.org/10.1016/j.cor.2007.01.014.
[29] R. S. De Camargo, G. Miranda Jr. and H. P. Luna, Benders decomposition for the uncapacitated multiple allocation hub location problem, Comput. Oper. Res. 35 (2008) 1047-1064, https://doi.org/10.1016/j.cor.2006.07.002.
[30] I. Contreras, J. F. Cordeau and G. Laporte, Benders decomposition for large-scale uncapacitated hub location, Oper. Res. 59 (2011) 1477 - 1490, https://doi.org/10.1287/opre.1110.0965.
[31] H. Mokhtar, M. Krishnamoorthy and A. T. Ernst, A modified benders method for the single and multiple allocation p-hub median problems, Oper. Res. Proc. 1 (2017) 135 - 141.
[32] A. Zabihi and M. Gharakhani, A literature survey of HUB location problems and methods with emphasis on the marine transportations, Uncertain Supply Chain Manag. 6 (2018) 91 - 116.
[33] A. Zabihi, M. Gharakhani and A. Afshinfar, A multi criteria decision-making model for selecting hub port for Iranian marine industry, Uncertain Supply Chain Manag. 4 (2016) 195 - 206.
[34] E. Korani, A. Eydi, I. Nakhai Kamalabadi and K. Mohammdian, Logical selection of potential hub nodes in location of strategic facilities by a hybrid methodology of data envelopment analysis and analytic hierarchical process: Iran aviation case study, Inter. j. transp. eng. 7 (2019) 171 - 193, https://doi.org/ 10.22119/IJTE.2018.127685.1400.
[35] D. R. Fulkerson and G. C. Harding, Maximizing the minimum source-sink path subject to a budget constraint, Math. Program. 13 (1977) 116 - 118, https://doi.org/10.1007/BF01584329.
[36] S. E. Hambrusch and H. Y. Tu, Edge weight reduction problems in directed acyclic graphs, J. Algorithms 24 (1997) 66- 93, https://doi.org/10.1006/jagm.1997.0856.
[37] G. N. Frederickson and R. Solis-Oba, Increasing the weight of minimum spanning trees, J. Algorithms 33 (1999) 244 - 266, https://doi.org/10.1006/jagm.1999.1026.
[38] K. U. Drangmeister, S. O. Krunke, M. V. Marathe, H. Noltemeier and S. S. Ravi, Modifying edges of a network to obtain short subgraphs, Theoret. Comput. Sci. 203 (1998) 91-121, https://doi.org/10.1016/S0304-3975(97)00290-9.
[39] S. O. Krumke, M. V. Marathe, H. Noltemeier, R. Ravi and S. S. Ravi, Approximation algorithms for certain network improvement problems, J. Comb. Optim. 2 (1998) 257 - 288, https://doi.org/10.1023/A:1009798010579.
[40] A. R. Sepasian and E. Monabbati, Upgrading min-max spanning tree problem under various cost functions, Theoret. Comput. Sci. 704 (2017) 87-91, https://doi.org/10.1016/j.tcs.2017.08.006.
[41] R. E. Burkard, B. Klinz and J. Zhang, Bottleneck capacity expansion problems with general budget constraints, RAIRO Oper. Res. 35 (2001) 1- 20, https://doi.org/10.1051/ro:2001100.
[42] R. E. Burkard, Y. Lin and J. Zhang, Weight reduction problems with certain bottleneck objectives, European J. Oper. Res. 153 (2004) 191 - 199, https://doi.org/10.1016/S0377-2217(02)00713-0.
[43] E. Gassner, Up- and downgrading the 1-median in a network, Technical report 2007–2016, Graz University of Technology.
[44] E. Gassner, Up- and downgrading the 1-center in a network, Eur. J. Oper. Res. 198 (2009) 370 - 377, https://doi.org/10.1016/j.ejor.2008.09.013.
[45] E. Gassner, A game-theoretic approach for downgrading the 1-median in the plane with Manhattan metric, Ann. Oper. Res. 172 (2009) 393 - 404, https://doi.org/10.1007/s10479-009-0641-1.
[46] A. R. Sepasian and F. Rahbarnia, Upgrading p-median problem on a path, J. Math. Model. Algorithms Oper. Res. 14 (2015) 145 - 157, https://doi.org/10.1007/s10852-014-9265-9.
[47] A. R. Sepasian, Upgrading the 1-center problem with edge length variables on a tree, Discrete Optim. 29 (2018) 1 - 17, https://doi.org/10.1016/j.disopt.2018.02.002.
[48] J. F. Campbell, A survey of network hub location, Stud. Locational Anal. 6 (1994) 31 - 49.
[49] R. Zanjirani Farahani, M. Hekmatfar, A. B. Arabani and E. Nikbakhsh, Hub location problems: a review of models, classification, solution techniques and applications, Comput. Ind. Eng. 64 (2013) 1096 - 1109, https://doi.org/10.1016/j.cie.2013.01.012.
[50] J. F. Campbell and M. E. O’Kelly, Twenty-five years of hub location research, Transp. Sci. 46 (2012) 153- 169.
[51] S. A. MirHassani and F. Hooshmand, Methods and Models in Mathematical Programming, Springer, 2019.
[52] R. Rahmaniani, T. G. Crainic, M. Gendreau and W. Rei, The Benders decomposition algorithm: a literature review, European J. Oper. Res. 259 (2017) 801 - 817, https://doi.org/10.1016/j.ejor.2016.12.005.
[53] J. F. Benders, Partitioning procedures for solving mixed-variables programming problems, Numer. Math. 4 (1962) 238 - 252, https://doi.org/10.1007/BF01386316.
[54] A. M. Geoffrion and G. W. Graves, Multicomodity distribution system design by Benders decomposition, Manag. Sci. 20 (1974) 822 - 844.
[55] S. Wandelt, W. Dai, J. Zhang and X. Sun, Toward a reference experimental benchmark for solving hub location problems, Transp. Sci. 56 (2022) 543 - 564.
Mathematics Interdisciplinary Research
Volume 9, Issue 2
June 2024
Pages 131-150

Files

Share

How to cite

Statistics