The object of this work is to present an exact solution for the capacitated multiple allocation hub location problem. In order to accelerate the search for solutions, the Local Branching (LB) technique was employed. This technique is based on branch-and-cut methods and it also incorporates some ideas present in local search and metaheuristics.

Local Branching, location, hubs, metaheuristics, computational mathematics.

[1] Alumur, S. and Kara, B. Y.: Network hub location problems: The state of the art. European Journal of Operational Research 190, 1–21 (2008)

[2] Campbell, J.E.: Integer programming formulations of discrete hub location problems. European Journal of Operational Research 72, 387–405 (1994).

[3] Cunha, C.B.; Silva, M.R.: A genetic algorithm for the problem of configuring a hub-and-spoke network for a LTL trucking company in Brazil. European Journal of Operational Research 179, 747–758 (2007).

[4] Ebery, J; Krishnamoorthy, M; Ernst, A; Boland, N.: The Capacitated multiple allocation hub location problem: Formulations and algorithms. European Journal of Operational Research 120, 614–631 (2000).

[5] Ernst, A.T. and Krishinamoorthy, M.: Efficient algorithms for the uncapacited single allocation p-hub median problem. Location Science 4(3), 139–154 (1996).

[6] Ernst, A.T and Krishnamoorthy, M.: Exact and heuristic algorithms for the uncapacitated multiple allocation p-hub median problem. European Journal of Operational Research 104(1), 100–112 (1998).

[7] Fischetti, M. and Lodi, A.: Local branching. Mathematical Programming 98 (1-3), 23-47 (2003).

[8] Garey, M. R. and Johnson, D. S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W.H. Freeman (1979).

[9] Mladenovic, N. and Hansen, P.: Variable neighborhood search. Comps. & Opns 24(11), 1097-1100 (1997).

[10] O’Kelly, M.: A quadratic integer program for the location of interacting hub facilities. European Journal of Operational Research 32, 393-404 (1987).