Using Metaheuristic Algorithms for Solving a Hub Location Problem: Application in Passive Optical Network Planning

Rabbani, Masoud; Ravanbakhsh, Mohammad; Farrokhi-Asl, Hamed; Taheri, Mahyar

doi:10.22034/2017.1.02

Using Metaheuristic Algorithms for Solving a Hub Location Problem: Application in Passive Optical Network Planning

Document Type : Research Paper

Authors

¹ School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran

² School of Industrial Engineering, Iran University of Science & Technology, Tehran, Iran

10.22034/2017.1.02

Abstract

Nowadays, fiber-optic due to having greater bandwidth and being more efficient compared with other similar technologies, are counted as one the most important tools for data transfer. In this article, an integrated mathematical model for a three-level fiber-optic distribution network with consideration of simultaneous backbone and local access networks is presented in which the backbone network is a ring and the access networks has a star-star topology. The aim of the model is to determine the location of the central offices and splitters, how connections are made between central offices, and allocation of each demand node to a splitter or central office in a way that the wiring cost of fiber optical and concentrator installation are minimized. Moreover, each user’s desired bandwidth should be provided efficiently. Then, the proposed model is validated by GAMS software in small-sized problems, afterwards the model is solved by two meta-heuristic methods including differential evolution (DE) and genetic algorithm (GA) in large-scaled problems and the results of two algorithms are compared with respect to computational time and objective function obtained value. Finally, a sensitivity analysis is provided.
Keyword: Fiber-optic, telecommunication network, hub-location, passive splitter, three-level network.

Keywords

Main Subjects

optimization in supply chain management

References

Abyazi-Sani, R., and Ghanbari, R. (2016). An efficient tabu search for solving the uncapacitated single allocation hub location problem. Computers & Industrial Engineering, Vol. 93, pp. 99-109.

Alumur, S., and Kara, B. Y. (2008). Network hub location problems: The state of the art. European journal of operational research, Vol. 190(1), pp. 1-21.

Balakrishnan, A., Magnanti, T. A., Shulman, A. and Wong, R. T. (1991), Models for planning capacity expansion in local access telecommunication networks. Annals of Operations Research, Vol. 33(4), pp. 239-284.

Bley, A., and Koch, T. (2008). Integer programming approaches to access and backbone IP network planning (pp. 87-110). Berlin Heidelberg: Springer.

Chardy, M., Costa, M. C., Faye, A., and Trampont, M. (2012). Optimizing splitter and fiber location in a multilevel optical FTTH network. European Journal of Operational Research, Vol. 222(3), pp. 430-440.

Chamberland, S. (2010). Global access network evolution. IEEE/ACM Transactions on Networking (TON), Vol. 18(1), pp. 136-149.

Chen, S., Ljubić, I., and Raghavan, S. (2010). The regenerator location problem.Networks, Vol. 55(3), pp. 205-220.

Chung, S. H., Myung, Y. S., and Tcha, D. W. (1992). Optimal design of a distributed network with a two-level hierarchical structure. European Journal of Operational Research, Vol. 62(1), pp. 105-115.

Din, D. R. (2008). Heuristic and Simulated Annealing Algorithms for Wireless ATM Backbone Network Design Problem. Journal of Information Science and Engineering, 24(2), pp. 483-501.

Duarte, A., Martí, R., Resende, M. G. C., and Silva, R. M. A. (2014). Improved heuristics for the regenerator location problem. International Transactions in Operational Research, Vol. 21(4), pp. 541-558.

Elmastaş, S. (2006). Hub location problem for air-ground transportation sistems with time restrictions (Doctoral dissertation, Bilkent University).

Farrokhi-Asl, H., Tavakkoli-Moghaddam, R., Asgarian, B., and Sangari, E. (2017). Metaheuristics for a bi-objective location-routing-problem in waste collection management. Journal of Industrial and Production Engineering, Vol. 34(4), 239-252.

Fortz, B. (2015). “Location Problems in Telecommunications. In Location Science (pp. 537-554). Springer International Publishing.

Gavish, B., Li, C. L., and Simchi-Levi, D. (1992). Analysis of heuristics for the design of tree networks. Annals of Operations Research, Vol. 36(1), pp.77-86.

Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning, 1989. Reading: Addison-Wesley.

Jadhav, R. A., & Shitole, D. S. (2013) FIBRE OPTICS COMMUNICATION AND APPLICATIONS. Intrenational Journal of Innovative Research in Engineering and Science.

Hosage, C. M., and Goodchild, M. F. (1986). Discrete space location-allocation solutions from genetic algorithms. Annals of Operations Research, Vol. 6(2), pp. 35-46.

Helme, M. P., and Magnanti, T. L. (1989). Designing satellite communication networks by zero—one quadratic programming. Networks, Vol. 19(4), pp. 427-450.

Holland, J. H. (1975). Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence.

Ho, K. S., Zhou, M., and Cheung, K. W. (2006, November). A New Approach for Designing the Next Generation Survivable Backbone Network. In Telecommunications Network Strategy and Planning Symposium, 2006. NETWORKS 2006. 12th International (pp. 1-6). IEEE.

Kim, Y., Lee, Y., and Han, J. (2011). A splitter location–allocation problem in designing fiber optic access networks. European Journal of Operational Research, Vol. 210(2), pp. 425-435.

Kim, J. G., and Tcha, D. W. (1992). Optimal design of a two-level hierarchical network with tree-star configuration. Computers & industrial engineering, Vol. 22(3), pp. 273-281.

Kokangul, A., and Ari, A. (2011). Optimization of passive optical network planning. Applied Mathematical Modelling, Vol. 35(7), pp. 3345-3354.

Labbé, M., Laporte, G., Martín, I. R., and Gonzalez, J. J. S. (2004). The ring star problem: Polyhedral analysis and exact algorithm. Networks, Vol. 43(3), pp. 177-189.

Li, J., and Shen, G. (2009). Cost minimization planning for green field passive optical networks. Journal of Optical Communications and Networking, Vol. 1(1), pp. 17-29.

Liefooghe, A., Jourdan, L., and Talbi, E. G. (2010). Meta-heuristics and cooperative approaches for the bi-objective ring star problem. Computers & Operations Research, Vol. 37(6), pp. 1033-1044.

Martins de Sá, E., Contreras, I., Cordeau, J. F., Saraiva de Camargo, R., and de Miranda, G. (2015). The hub line location problem. Transportation Science.

Ortiz-García, E. G., Martínez-Bernabeu, L., Salcedo-Sanz, S., Flórez-Revuelta, F., and Portilla-Figueras, A. (2009, May). A parallel evolutionary algorithm for the hub location problem with fully interconnected backbone and access networks. In Evolutionary Computation, 2009. CEC'09. IEEE Congress on (pp. 1501-1506). IEEE.

Rabbani, M., Farrokhi-Asl, H., and Heidari, R. (2017). Genetic Algorithm-Based Optimization Approach for an Uncapacitated Single Allocation P-hub Center Problem with more realistic cost structure. Journal of Industrial and Systems Engineering, Vol. 10, pp. 108-124.

Rabbani, M., Montazeri, M., Farrokhi-Asl, H., and Rafiei, H. (2016). A multi-objective genetic algorithm for a mixed-model assembly U-line balancing type-I problem considering human-related issues, training, and learning. Journal of Industrial Engineering International, Vol. 12(4), pp. 485-497.

Saboury, A., Ghaffari-Nasab, N., Barzinpour, F., and Jabalameli, M. S. (2013). Applying two efficient hybrid heuristics for hub location problem with fully interconnected backbone and access networks. Computers & Operations Research, Vol. 40(10), pp. 2493-2507.

Storn, R., & Price, K. (1997). Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces. Journal of global optimization, Vol. 11(4), pp. 341-359.

Thomadsen, T., and Stidsen, T. (2005). Hierarchical ring network design using branch-and-price. Telecommunication systems, Vol. 29(1), pp. 61-76.

Thomadsen, T., and Larsen, J. (2007). A hub location problem with fully interconnected backbone and access networks. Computers & operations research, Vol. 34(8), pp. 2520-2531.

Topcuoglu, H., Corut, F., Ermis, M., and Yilmaz, G. (2005). Solving the uncapacitated hub location problem using genetic algorithms. Computers & Operations Research, Vol. 32(4), pp. 967-984.

Yaman, H., and Carello, G. (2005). Solving the hub location problem with modular link capacities. Computers & operations research, Vol. 32(12), pp. 3227-3245.

Yaman, H. (2009). The hierarchical hub median problem with single assignment. Transportation Research Part B: Methodological, Vol. 43(6), pp. 643-658.

Yazar, B. (2013). FIBER OPTICAL NETWORK DESIGN PROBLEMS: CASE FOR TURKEY (Doctoral dissertation, BILKENT UNIVERSITY).

Yazar, B., Arslan, O., Karaşan, O. E., and Kara, B. Y. (2016). Fiber optical network design problems: A case for Turkey. Omega, Vol.63, pp. 23-40.

Yoon, M. G., and Current, J. (2008). The hub location and network design problem with fixed and variable arc costs: formulation and dual-basedansport values of time. Transport Policy, Vol. 11, pp 363–377.