Allocating nodes to hubs for minimizing the hubs processing resources: A case study

Balma, Ali; Mrad, Mehdi

RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 3, pp. 807-827.

Suite au passage du modèle économique de la revue en S20, le texte intégral des articles des années 2019 et 2020 est accessible uniquement sur le site de l'éditeur et est réservé aux abonnés.

This paper addresses the problem of allocating the terminal nodes to the hub nodes in a telecommunication network. Since the flow processing induces some undesirable delay, the objective is to minimize the total flow processed by the hubs. This study focuses on a real life network of the tunisian operator Tunisie Telecom whose operations managers are concerned by the quality of service. We provide three compact formulations that give optimal solutions for networks of large size. In particular, the last two are obtained by applying the Reformulation-Linearization Technique to a nonlinear formulation of the problem. The latter formulation derived within this approach is the most computationally effective, as pointed out by the computational experiments conducted on the real life network of Tunisie Telecom with 110 nodes and 5 hubs. Finally, we discuss and compare between the single allocation and double allocation configurations.

B. Addis, G. Carello and A. Ceselli, Exactly solving a two-level location problem with modular node capacities. Networks 59 (2012) 161–180. | DOI | MR | Zbl

A. Alumur Sibel, Y. Kara Bahar and E. Karasan Oya, Multimodal hub location and hub network design. Omega 40 (2012) 927–939. | DOI

S. Alumur and B.Y. Kara, Network hub location problems: The state of the art. Eur. J. Oper. Res. 190 (2008) 1–21. | DOI | MR | Zbl

A. Balma, A.B. Hadj–Alouane and N. Ben Hadj-Alouane, Optimizing voice processing resources of the Trunk Gateways in NGN networks. In: Proc. of International Multi-Conference on Complexity, Informatics and Cybernetics: IMCIC 2014 (2014) 152–155.

I. Contreras, J.F. Cordeau and G. Laporte, Benders Decomposition for Large-Scale Uncapacitated Hub Location. Oper. Res. 59 (2011) 1477–1490. | DOI | MR | Zbl

A.M. Campbell, T.J. Lowe and L. Zhang, The $p$-hub center allocation problem. Eur. J. Operat. Res. 176 (2007) 819–835, ISSN 0377–2217. | DOI | MR | Zbl

J.F. Campbell and M.E. Okelly, Twenty-Five Years of Hub Location Research. Trans. Sci. 46 (2012) 153–169. | DOI

Ch. Jeng–Fung, A hybrid heuristic for the uncapacitated single allocation hub location problem. Omega 35 (2007) 211–220. | DOI

I. Contreras and E. Fernandez, General network design: A unified view of combined location and network design problem. Eur. J. Operat. Res. 219 (2012) 680–697. | DOI | MR | Zbl

I. Correia, S. Nickel and F. Saldanha-Da-Gama, The capacitated single-allocation hub location problem revisited: A note on a classical formulation. Eur. J. Oper. Res. 207 (2010) 92–96. | DOI | MR | Zbl

I. Correia, S. Nickel and F. Saldanha-Da-Gama, Single-assignment hub location problems with multiple capacity levels. Transp. Res. Part B 44 (2010) 1047–1066. | DOI

M.G. Costa, M.E. Captivo and J. Climaco, Capacitated single allocation hub location problem: a bi-criteria approach. Comput. Oper. Res. 35 (2008) 3671–3695. | DOI | Zbl

A.T. Ernst and M. Krishnamoorthy, Solution algorithms for the capacitated single allocation hub location problem. Ann. Oper. Res. 86 (1999) 141–159. | DOI | MR | Zbl

A.T. Ernst, H. Hamacher, H. Jiang, M. Krishnamoorthy and G. Woeginger, Uncapacitated single and multiple allocation $p$-hub center problems. Comput. Oper. Res. 36 (2009) 2230–2241. | DOI | MR | Zbl

M. Haouari, N. Maculan and M. Mrad, Enhanced compact models for the connected subgraph problem and for the shortest path problem in digraphs with negative cycles. Comput. Oper. Res. 40 (2013) 2485–2492. | DOI | MR | Zbl

B. Haouari, S. Bhar Layeb and H.D. Sherali, Tight compact models and comparative analysis for the prize collecting Steiner tree problem. Discrete Appl. Math. 161 (2013) 618–632. | DOI | MR | Zbl

J.Q. Hu and B. Leida, Traffic Grooming, Routing, and Wavelength Assignment in Optical WDM Mesh Networks. Proceedings of the IEEE INFOCOM 2004 (2004) 495–501; Available at: DOI: https://doi.org/10.1109/INFCOM.2004.1354521.

B.Y. Kara and B. Tansel, On the single-assignment $p$-hub center problem. Eur. J. Oper. Res. 125 (2000) 648–655. | DOI | Zbl

F. Larumbe and B. Sanso, Optimal Location of Data Centers and Software Components in Cloud Computing Network Design. Proceedings of the 12th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGrid) (2012) 841–844.

I. Rodríguez–Martín and J.J. Salazar–González, Solving a capacitated hub location problem. Eur. J. Oper. Res. 184 (2008) 468–479. | DOI | MR | Zbl

S. Gelareh and S. Nickel, Hub location problems in transportation networks. Trans. Res. Part E: Logistics and Trans. Rev. 47 (2011) 1092–1111. | DOI

H.D. Sherali, Y. Lee and T. Park, New modeling approaches for the design of local access transport area networks. Eur. J. Oper. Res. 127 (2000) 94–108. | DOI | Zbl

H.D. Sherali and W.P. Adams, A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math. 3 (1990) 411–30. | DOI | MR | Zbl

H.D. Sherali and W.P. Adams, A hierarchy of relaxations and convex hull characteristics for mixed-integer zero-one programming problems. Discrete Appl. Math. 52 (1994) 83–106. | DOI | MR | Zbl

H.D. Sherali, S.C. Sarin and P. Tsai, A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints. Discrete Optimiz. 3 (2006) 20–32. | DOI | MR | Zbl

H. Yaman and G. Carello, Solving the hub location problem with modular link capacities. Comput. Oper. Res. 32 (2005) 3227–3245. | DOI | Zbl

Y. He, T. Wu, C. Zhang and Z. Liang, An improved MIP heuristic for the intermodal hub location problem. Omega 57 (2015) 203–211. | DOI