Robust optimization approach to capacitated single and multiple allocation hub location problems
Tóm tắt
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 Karimi and Bashiri (Scientia Iranica 18: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.
Tài liệu tham khảo
Abdinnour-Helm S (1998) A hybrid heuristic for the uncapacitated hub location problem. Eur J Oper Res 106:489–499
Alumur SA, Kara BY, Karasan OE (2009) The design of single allocation incomplete hub networks. Transp Res Part B 43:936–951
Alumur SA, Nickel S, Saldanha-da-Gama F (2012) Hub location under uncertainty. Transp Res Part B 46:529–543
Alumur S, Kara BY (2008) Network hub location problems: the state of the art. Eur J Oper Res 190:1–21
Aykin T (1994) Lagrangean relaxation based approaches to capacitated hub-and-spoke network design problem. Eur J Oper Res 79:501–523
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
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
Campbell JF (1994a) A survey of network hub location. Stud Locat Anal 6:31–49
Campbell JF (1994b) Integer programming formulations of discrete hub location problems. Eur J Oper Res 72:387–405
Campbell JF (1996) Hub location and the p-hub median problem. Oper Res 44:1–13
Campbell JF, Ernst AT, Krishnamoorthy M (2005a) Hub arc location problems: part I-introduction and results. Manag Sci 51:1540–1555
Campbell JF, Ernst AT, Krishnamoorthy M (2005b) Hub arc location problems: part II-formulations and optimal algorithms. Manag Sci 51:1556–1571
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
Chen JF (2007) A hybrid heuristic for the uncapacitated single allocation hub location problem. Omega 35:211–220
Contreras I, Cordeau J-F, Laporte G (2011) Stochastic uncapacitated hub location. Eur J Oper Res 212:518–528
Contreras I, Cordeau J-F, Laporte G (2012) Benders decomposition for large-scale uncapacitated hub location. Oper Res. doi:10.1287/opre.1110.0965
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
Contreras I, Fernández E, Marín A (2010) The tree of hubs location problem. Eur J Oper Res 202:390–400
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
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
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
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
de Camargo RS, Miranda JRG (2012) Single allocation hub location problem under congestion: network owner and user perspectives. Expert Syst Appl 39:3385–3391
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
de Camargo RS, Miranda JRG, Luna HPL (2008) Benders decomposition for the uncapacitated multiple allocation hub location problem. Comput Oper Res 35:1047–1064
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
Ebery J (2001) Solving large single allocation p-hub problems with two or three hubs. Eur J Oper Res 128:447–458
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
Ernst AT, Krishnamoorthy M (1996) Efficient algorithms for the uncapaciterted single allocation P-hub median problem. Locat Sci 4:139–154
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
Ernst AT, Krishnamoorthy M (1998b) An exact solution approach based on shortest-paths for p-hub median problems. Inf J Comput 10:149–162
Ernst AT, Krishnamoorthy M (1999) Solution algorithms for the capacitated single allocation hub location problem. Ann Oper Res 86:141–159
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
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
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
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
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
Karimi H, Bashiri M (2011) Hub covering location problems with different coverage types. Scientia Iranica 18:1571–1578
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
Labbé M, Yaman H (2004) Projecting flow variables for hub location problems. Networks 44:84–93
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
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
Marianov V, Serra D (2003) Location models for airline hubs behaving as M/D/c queues. Comput Oper Res 30:983–1003
Marín A (2005a) Formulating and solving splittable capacitated multiple allocation hub location problems. Comput Oper Res 32:3093–3109
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
Mayer G, Wagner B (2002) HubLocator: an exact solution method for the multiple allocation hub location problem. Comput Oper Res 29:715–739
Mohammadi M, Jolai F, Rostami H (2011) An M/M/c queue model for hub covering location problem. Math Comput Modell 54:2623–2638
Mohammadi M, Torabi SA, Tavakkoli-Moghaddam R (2014) Sustainable hub location under mixed uncertainty. Transp Res Part E 62:89–115
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
O’Kelly ME (1986a) The location of interacting hub facilities. Transp Sci 20:92–105
O’Kelly ME (1986b) Activity levels at hub facilities in interacting networks. Geogr Anal 18:343–356
O’Kelly ME (1987) A quadratic integer program for the location of interacting hub facilities. Eur J Oper Res 32:393–404
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
Pirkul H, Schilling DA (1998) An efficient procedure for designing single allocation hub and spoke systems. Manag Sci 44:235–242
Puerto J, Ramos AB, Rodriguez-Chia AM (2011) Single-allocation ordered median hub location problems. Comput Oper Res 38:559–570
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
Randall M (2008) Solution approaches for the capacitated single allocation hub location problem using ant colony optimization. Comput Optim Appl 39:239–261
Sasaki M, Fukushima M (2003) On the hub-and-spoke model with arc capacity constraints. J Oper Res Soc Jpn 46:409–428
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
Silva MR, Cunha CB (2009) New simple and efficient heuristics for the uncapacitated single allocation hub location problem. Comput Oper Res 36:3152–3165
Sim T, Lowe TJ, Thomas BW (2009) The stochastic p-hub center problem with service-level constraints. Comput Oper Res 36:3166–3177
Skorin-Kapov D, Skorin-Kapov J (1994) On tabu search for the location of interacting hub facilities. Eur J Oper Res 73:502–509
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
Sohn J, Park S (2000) The single allocation problem in the interacting three-hub network. Networks 35:17–25
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
Yang TH (2009) Stochastic air freight hub location and flight routes planning. Appl Math Modell 33:4424–4430
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
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