Lagrangean relaxation for the capacitated hub location problem with single assignment. (English) Zbl 1163.90617

Summary: This article considers the capacitated hub location problem with single assignment. We propose a Lagrangean relaxation to obtain tight upper and lower bounds. The Lagrangean function that we formulate exploits the structure of the problem and can be decomposed into smaller subproblems that can be solved efficiently. In addition, we present some simple reduction tests, based on the Lagrangean relaxation bounds that allows us to reduce considerably the size of the formulation and thus, to reduce the computational effort. Computational experiments have been performed with both benchmark instances from literature and with some new larger instances. The obtained results are impressive. For all tested instances (ranging from 10 to 200 nodes), we obtain or improve the best known solution and the obtained duality gaps, between our upper and lower bounds, never exceed \(3.4\%\).


90B85 Continuous location
90C59 Approximation methods and heuristics in mathematical programming
Full Text: DOI


[1] Alumur S, Kara B (2008) Network hub location problems: the state of the art. Eur J Oper Res 190(1): 1–21 · Zbl 1146.90455
[2] Aykin T (1994) Lagrangian relaxation based approaches to capacitated hub-and-spoke network design problem. Eur J Oper Res 79: 501–523 · Zbl 0813.90074
[3] Aykin T (1995) Networking policies for hub-and-spoke systems with applications to the air transportation system. Transport Sci 3: 201–221 · Zbl 0857.90028
[4] Boland N, Ernst A, Krishnamoorthy M, Ebery J (2004) Preprocessing and cutting methods for multiple allocation hub location problems. Eur J Oper Res 155(3): 638–653 · Zbl 1049.90034
[5] Campbell J, Ernst A, Krishnamoorthy M (2002) Hub location problems. In: Hamacher H, Drezner Z (eds) Facility location: applications and theory. Springer, Berlin, pp 373–407 · Zbl 1061.90069
[6] Campbell JF (1994) Integer programming formulations of discrete hub location problems. Eur J Oper Res 72: 387–405 · Zbl 0790.90048
[7] Campbell JF, Ernst AT, Krishnamoorthy M (2005a) Hub arc location problems: Part i–introduction and results. Manag Sci 51(10): 1540–1555 · Zbl 1232.90258
[8] Campbell JF, Ernst AT, Krishnamoorthy M (2005b) Hub arc location problems: Part ii–formulations and optimal algorithms. Manag Sci 51(10): 1556–1571 · Zbl 1232.90259
[9] Costa M, Captivo M, Climaco J (2008) Capacitated sinlge allocation hub location problem–a bi-criteria approach. Comput Oper Res 35(11): 3671–3695 · Zbl 1171.90454
[10] Ebery J, Krishnamoorthy M, Ernst AT, Boland N (2000) The capacitated multiple allocation hub location problem: formulations and algorithms. Eur J Oper Res 120(3): 614–631 · Zbl 0985.90063
[11] Ernst A, Krishnamoorthy M (1996) Efficient algorithms for the uncapacitated single allocation p-hub median problem. Locat Sci 4(3): 139–154 · Zbl 0927.90065
[12] Ernst A, Krishnamoorthy M (1999) Solution algorithms for the capacitated single allocation hub location problem. Ann Oper Res 86: 141–159 · Zbl 0918.90096
[13] Guignard M (2003) Lagrangean relaxation. TOP 11: 151–228 · Zbl 1079.90087
[14] Labbé M, Yaman H, Gourdin E (2005) A branch and cut algorithm for hub location problems with single assignment. Math Progr 102(2): 371–405 · Zbl 1079.90080
[15] Marín A (2005) Formulating and solving splittable capacitated multiple allocation hub location problems. Comput Oper Res 32: 3093–3109 · Zbl 1146.90458
[16] Martello S, D DP, Toth P (2000) New trends in exact algorithms for the 0-1 knapsack problem. Eur J Oper Res 123: 325–332 · Zbl 0961.90090
[17] O’Kelly M (1986) Activity levels at hub facilities in interacting networks. Geogr Anal 18(4): 343–356
[18] O’Kelly M (1987) A quadratic integer program for the location of interacting hub facilities. Eur J Oper Res 32: 393–404 · Zbl 0627.90030
[19] O’Kelly ME, Bryan D (2002) Interfacility interaction in models of hub and spoke networks. J Reg Sci 42(1): 145–164
[20] Pirkul H, Schilling D (1998) An efficient procedure for designing single allocation hub and spoke systems. Manag Sci 44(12): 235–242 · Zbl 0989.90537
[21] Podnar H, Skorin-Kapov J, Skorin-Kapov D (2002) Network cost minimization using threshold-based dicounting. Eur J Oper Res 137: 371–386 · Zbl 1008.90004
[22] Rodríguez-Martín I, Salazar-González JJ (2008) Solving a capacitated hub location problem. Eur J Oper Res 184: 468–479 · Zbl 1149.90317
[23] Sasaki M, Fukushima M (2003) On the hub-and-spoke model with arc capacities constraints. J Oper Res Soc Jpn 46(4): 409–428 · Zbl 1137.90590
[24] Skorin-Kapov D, Skorin-Kapov J, O’Kelly M (1996) Tight linear programming relaxations of uncapacitated p-hub median problems. Eur J Oper Res 73: 501–508 · Zbl 0947.90602
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.