×

Robust optimization approach to capacitated single and multiple allocation hub location problems. (English) Zbl 1338.90211

Summary: Hub location problem is one of the new emerging and prosperous areas in the classical facility location theory. As a part of the decision-making process, supply chain managers of organizations and companies must pay special attention to these issues. In strategic planning, decisions have long-term effects and program implementation will take a long time. Hence, in the decisions taken, uncertainty should be considered. Uncertainty can be regarded as a property of the system that describes the flaws of human knowledge about a system and its progress included. This paper considers single allocation and multiple allocation hub location problems (SAHLP and MAHLP). First, general models of capacitated single and multiple allocation hub location problems (CSAHLP and CMAHLP) are introduced, then a robust optimization approach is used for dealing with uncertain parameters. Finally, the uncertainty of parameters such as fixed setup cost and capacity of each hub on Iranian Aviation Dataset [H. Karimi and M. Bashiri, “Hub covering location problems with different coverage types”, Sci. Iran. 18, No. 6, 1571–1578 (2011)] are studied and the results are presented. The results suggest that ignoring uncertainty in the supply chain network design sometimes causes large losses and expenses. In turn, these inflicted losses cause delay in the implementation phase in long-term expected plans and suspicion in all organizational activities.

MSC:

90B80 Discrete location and assignment
90B06 Transportation, logistics and supply chain management
Full Text: DOI

References:

[1] Abdinnour-Helm S (1998) A hybrid heuristic for the uncapacitated hub location problem. Eur J Oper Res 106:489-499 · Zbl 0991.90081 · doi:10.1016/S0377-2217(97)00286-5
[2] Alumur SA, Kara BY, Karasan OE (2009) The design of single allocation incomplete hub networks. Transp Res Part B 43:936-951 · doi:10.1016/j.trb.2009.04.004
[3] Alumur SA, Nickel S, Saldanha-da-Gama F (2012) Hub location under uncertainty. Transp Res Part B 46:529-543 · doi:10.1016/j.trb.2011.11.006
[4] Alumur S, Kara BY (2008) Network hub location problems: the state of the art. Eur J Oper Res 190:1-21 · Zbl 1146.90455 · doi:10.1016/j.ejor.2007.06.008
[5] Aykin T (1994) Lagrangean relaxation based approaches to capacitated hub-and-spoke network design problem. Eur J Oper Res 79:501-523 · Zbl 0813.90074 · doi:10.1016/0377-2217(94)90062-0
[6] Boland N, Krishnamoorthy M, Ernst AT, Ebery J (2004) Preprocessing and cutting for multiple allocation hub location problems. Eur J Oper Res 155:638-653 · Zbl 1049.90034 · doi:10.1016/S0377-2217(03)00072-9
[7] Calik H, Alumur SA, Kara BY, Karasan OE (2009) A tabu-based heuristic for the hub covering problem over incomplete hub networks. Comput Oper Res 36:3088-3096 · Zbl 1177.90201 · doi:10.1016/j.cor.2008.11.023
[8] Campbell JF (1994a) A survey of network hub location. Stud Locat Anal 6:31-49
[9] Campbell JF (1994b) Integer programming formulations of discrete hub location problems. Eur J Oper Res 72:387-405 · Zbl 0790.90048 · doi:10.1016/0377-2217(94)90318-2
[10] Campbell JF (1996) Hub location and the p-hub median problem. Oper Res 44:1-13 · Zbl 0879.90127 · doi:10.1287/opre.44.6.923
[11] Campbell JF, Ernst AT, Krishnamoorthy M (2005a) Hub arc location problems: part I-introduction and results. Manag Sci 51:1540-1555 · Zbl 1232.90258 · doi:10.1287/mnsc.1050.0406
[12] Campbell JF, Ernst AT, Krishnamoorthy M (2005b) Hub arc location problems: part II-formulations and optimal algorithms. Manag Sci 51:1556-1571 · Zbl 1232.90259 · doi:10.1287/mnsc.1050.0407
[13] Cánovas L, García S, Marín A (2007) Solving the uncapacitated multiple hub location problem by means of a dual-ascent technique. Eur J Oper Res 179:990-1007 · Zbl 1163.90595 · doi:10.1016/j.ejor.2005.08.028
[14] Chen JF (2007) A hybrid heuristic for the uncapacitated single allocation hub location problem. Omega 35:211-220 · doi:10.1016/j.omega.2005.05.004
[15] Contreras I, Cordeau J-F, Laporte G (2011) Stochastic uncapacitated hub location. Eur J Oper Res 212:518-528 · Zbl 1237.90130 · doi:10.1016/j.ejor.2011.02.018
[16] Contreras I, Cordeau J-F, Laporte G (2012) Benders decomposition for large-scale uncapacitated hub location. Oper Res. doi:10.1287/opre.1110.0965 · Zbl 1242.90094
[17] Contreras I, Fernández E, Marín A (2009) Tight bounds from a path based formulation for the tree of hub location problem. Comput Oper Res 36:3117-3127 · Zbl 1176.90351 · doi:10.1016/j.cor.2008.12.009
[18] Contreras I, Fernández E, Marín A (2010) The tree of hubs location problem. Eur J Oper Res 202:390-400 · Zbl 1175.90396 · doi:10.1016/j.ejor.2009.05.044
[19] Correia I, Nickel S, Saldanha-da-Gama F (2010) The capacitated single allocation hub location problem revisited: a note on a classical formulation. Eur J Oper Res 207:92-96 · Zbl 1205.90174
[20] Correia I, Nickel S, Saldanha-da-Gama F (2011) Hub and spoke network design with single-assignment, capacity decisions and balancing requirements. Appl Math Model 35:4841-4851 · Zbl 1228.90047 · doi:10.1016/j.apm.2011.03.046
[21] Costa MG, Captivo ME, Climaco J (2007) Capacitated single allocation hub location problem: a bi-criteria approach. Comput Oper Res (in press). doi:10.1016/j.cor.2007.04.005 · Zbl 1171.90454
[22] de Camargo RS, Miranda JRG, Ferreira RPM (2011) A hybrid outer approximation/benders decomposition algorithm for the single allocation hub location problem under congestion. Oper Res Lett 39:329-337 · Zbl 1235.90078 · doi:10.1016/j.orl.2011.06.015
[23] de Camargo RS, Miranda JRG (2012) Single allocation hub location problem under congestion: network owner and user perspectives. Expert Syst Appl 39:3385-3391 · doi:10.1016/j.eswa.2011.09.026
[24] de Camargo RS, Miranda JRG, Ferreira RPM, Luna HPL (2009) Multiple allocation hub-and-spoke network design under hub congestion. Comput Oper Res 36:3097-3106 · Zbl 1177.90064
[25] de Camargo RS, Miranda JRG, Luna HPL (2008) Benders decomposition for the uncapacitated multiple allocation hub location problem. Comput Oper Res 35:1047-1064 · Zbl 1180.90038 · doi:10.1016/j.cor.2006.07.002
[26] de Miranda Junior G, de Camargo RS, Pinto LR, Conceicao SV, Ferreira RPM (2011) Hub location under hub congestion and demand uncertainty: the Brazilian Case Study. Pesqui Oper 31: 319-349 · Zbl 1177.90201
[27] Ebery J (2001) Solving large single allocation p-hub problems with two or three hubs. Eur J Oper Res 128:447-458 · Zbl 0985.90064 · doi:10.1016/S0377-2217(99)00370-7
[28] Ebery J, Krishnamoorty M, Ernst A, Boland N (2000) The capacitated multiple allocation hub location problem: formulation and algorithms. Eur J Oper Res 120:614-631 · Zbl 0985.90063 · doi:10.1016/S0377-2217(98)00395-6
[29] Ernst AT, Krishnamoorthy M (1996) Efficient algorithms for the uncapaciterted single allocation P-hub median problem. Locat Sci 4:139-154 · Zbl 0927.90065 · doi:10.1016/S0966-8349(96)00011-3
[30] Ernst AT, Krishnamoorthy M (1998a) Exact and heuristic algorithms for the uncapacitated multiple allocation p-hub median problem. Eur J Oper Res 104:100-112 · Zbl 0955.90055 · doi:10.1016/S0377-2217(96)00340-2
[31] Ernst AT, Krishnamoorthy M (1998b) An exact solution approach based on shortest-paths for p-hub median problems. Inf J Comput 10:149-162 · Zbl 1034.90505 · doi:10.1287/ijoc.10.2.149
[32] Ernst AT, Krishnamoorthy M (1999) Solution algorithms for the capacitated single allocation hub location problem. Ann Oper Res 86:141-159 · Zbl 0918.90096 · doi:10.1023/A:1018994432663
[33] García S, Landete M, Marín A (2012) New formulation and a branch-and-cut algorithm for the multiple allocation p-hub median problem. Eur J Oper Res 220:48-57 · Zbl 1253.90135 · doi:10.1016/j.ejor.2012.01.042
[34] Hamacher HW, Labbé M, Nickel S, Sonneborn T (2004) Adapting polyhedral properties from facility to hub location problems. Discret Appl Math 145:104-116. http://www.shahed.ac.ir/bashiri/Lists/List13/Attachments/1/IAD(dataset).rar · Zbl 1058.90033
[35] Huang J, Wang Q (2009) Robust optimization of hub-and-spoke airline network design based on multi-objective genetic algorithm. J Transp Syst Eng Inf Technol 9:86-92
[36] Ilić A, Urošević D, Brimberg J, Mladenovic N (2010) A general variable neighborhood search for solving the uncapacitated single allocation p-hub median problem. Eur J Oper Res 206:289-300 · Zbl 1188.90142 · doi:10.1016/j.ejor.2010.02.022
[37] Iwasa M, Saito H, Matsui T (2009) Approximation algorithms for the single allocation problem in hub-and-spoke networks and related metric labeling problems. Discret Appl Math 157:2078-2088 · Zbl 1164.90019 · doi:10.1016/j.dam.2008.11.016
[38] Karimi H, Bashiri M (2011) Hub covering location problems with different coverage types. Scientia Iranica 18:1571-1578 · doi:10.1016/j.scient.2011.09.018
[39] Kratica J, Stanimirovic Z, Tosic D, Filipovic V (2007) Two genetic algorithms for solving the uncapacitated single allocation p-hub median problem. Eur J Oper Res 182:15-28 · Zbl 1128.90038 · doi:10.1016/j.ejor.2006.06.056
[40] Labbé M, Yaman H (2004) Projecting flow variables for hub location problems. Networks 44:84-93 · Zbl 1055.90045 · doi:10.1002/net.20019
[41] Labbé M, Yaman H, Gourdin E (2005) A branch and cut algorithm for the hub location problems with single assignment. Math Program 102:371-405 · Zbl 1079.90080 · doi:10.1007/s10107-004-0531-x
[42] Makui A, Rostami M, Jahani E, Nikui A (2012) A multi-objective robust optimization model for the capacitated P-hub location problem under uncertainty. Manag Sci Lett 2:525-534 · doi:10.5267/j.msl.2011.12.014
[43] Marianov V, Serra D (2003) Location models for airline hubs behaving as M/D/c queues. Comput Oper Res 30:983-1003 · Zbl 1039.90029 · doi:10.1016/S0305-0548(02)00052-7
[44] Marín A (2005a) Formulating and solving splittable capacitated multiple allocation hub location problems. Comput Oper Res 32:3093-3109 · Zbl 1146.90458 · doi:10.1016/j.cor.2004.04.008
[45] Marín A, Cánovas L, Landete M (2006) New formulations for the uncapacitated multiple allocation hub location problem. Eur J Oper Res 172:274-292 · Zbl 1116.90071 · doi:10.1016/j.ejor.2004.09.047
[46] Mayer G, Wagner B (2002) HubLocator: an exact solution method for the multiple allocation hub location problem. Comput Oper Res 29:715-739 · Zbl 1001.90044 · doi:10.1016/S0305-0548(01)00080-6
[47] Mohammadi M, Jolai F, Rostami H (2011) An M/M/c queue model for hub covering location problem. Math Comput Modell 54:2623-2638 · Zbl 1235.90077 · doi:10.1016/j.mcm.2011.06.038
[48] Mohammadi M, Torabi SA, Tavakkoli-Moghaddam R (2014) Sustainable hub location under mixed uncertainty. Transp Res Part E 62:89-115 · doi:10.1016/j.tre.2013.12.005
[49] Nickel S, Schobel A, Sonneborn T (2001) Chapter 1: Hub location problems in urban traffic networks. In: Niittymaki J, Pursula M (eds) Mathematics methods and optimization in transportation systems. Kluwer Academic Publishers, Dordrecht · Zbl 1005.90013
[50] O’Kelly ME (1986a) The location of interacting hub facilities. Transp Sci 20:92-105 · doi:10.1287/trsc.20.2.92
[51] O’Kelly ME (1986b) Activity levels at hub facilities in interacting networks. Geogr Anal 18:343-356 · doi:10.1111/j.1538-4632.1986.tb00106.x
[52] O’Kelly ME (1987) A quadratic integer program for the location of interacting hub facilities. Eur J Oper Res 32:393-404 · Zbl 0627.90030 · doi:10.1016/S0377-2217(87)80007-3
[53] O’Kelly ME, Bryan D, Skorin-Kapov D, Skorin-Kapov J (1996) Hub network design with single and multiple allocation: a computational study. Locat Sci 4:125-138 · Zbl 0927.90069 · doi:10.1016/S0966-8349(96)00015-0
[54] Pirkul H, Schilling DA (1998) An efficient procedure for designing single allocation hub and spoke systems. Manag Sci 44:235-242 · Zbl 0989.90537 · doi:10.1287/mnsc.44.12.S235
[55] Puerto J, Ramos AB, Rodriguez-Chia AM (2011) Single-allocation ordered median hub location problems. Comput Oper Res 38:559-570 · Zbl 1231.90271 · doi:10.1016/j.cor.2010.07.018
[56] Puerto J, Ramos AB, Rodríguez-Chía AM (2013) A specialized branch & bound & cut for Single-Allocation Ordered Median Hub Location problems. Discret Appl Math 161:2624-2646 · Zbl 1294.90034 · doi:10.1016/j.dam.2013.05.035
[57] Randall M (2008) Solution approaches for the capacitated single allocation hub location problem using ant colony optimization. Comput Optim Appl 39:239-261 · Zbl 1147.90421 · doi:10.1007/s10589-007-9069-1
[58] Sasaki M, Fukushima M (2003) On the hub-and-spoke model with arc capacity constraints. J Oper Res Soc Jpn 46:409-428 · Zbl 1137.90590
[59] Sender J, Clausen U (2013) Heuristics for solving a capacitated multiple allocation hub location problem with application in German wagonload traffic. Electron Notes Discret Math 41:13-20 · doi:10.1016/j.endm.2013.05.070
[60] Silva MR, Cunha CB (2009) New simple and efficient heuristics for the uncapacitated single allocation hub location problem. Comput Oper Res 36:3152-3165 · Zbl 1177.90255 · doi:10.1016/j.cor.2008.12.019
[61] Sim T, Lowe TJ, Thomas BW (2009) The stochastic p-hub center problem with service-level constraints. Comput Oper Res 36:3166-3177 · Zbl 1175.90073 · doi:10.1016/j.cor.2008.11.020
[62] Skorin-Kapov D, Skorin-Kapov J (1994) On tabu search for the location of interacting hub facilities. Eur J Oper Res 73:502-509 · Zbl 0806.90075 · doi:10.1016/0377-2217(94)90245-3
[63] Skorin-Kapov D, Skorin-Kapov J, O’Kelly M (1996) Tight linear programming relaxations of uncapacitated p-hub median problems. Eur J Oper Res 94:582-593 · Zbl 0947.90602 · doi:10.1016/0377-2217(95)00100-X
[64] Sohn J, Park S (2000) The single allocation problem in the interacting three-hub network. Networks 35:17-25 · Zbl 0938.90070 · doi:10.1002/(SICI)1097-0037(200001)35:1<17::AID-NET2>3.0.CO;2-N
[65] Yaman H, Kara BY, Tansel BC (2007) The latest arrival hub location problem for cargo delivery systems with stopovers. Transp Res Part B 41:906-919 · doi:10.1016/j.trb.2007.03.003
[66] Yang TH (2009) Stochastic air freight hub location and flight routes planning. Appl Math Modell 33:4424-4430 · Zbl 1171.90453 · doi:10.1016/j.apm.2009.03.018
[67] Yoon M, Current J (2008) The hub location and network design problem with fixed and variable arc costs. J Oper Res Soc 59:80-89 · Zbl 1166.90355 · doi:10.1057/palgrave.jors.2602307
[68] Zanjirani Farahani R, Hekmatfar RM, Nikbakhsh E (2013) Hub location problems: a review of models, classification, techniques and application. Comput Ind Eng 64:1096-1109 · doi:10.1016/j.cie.2013.01.012
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.