Abstract
Nowadays the Synchronous Optical NETworking (SONET) standard is widely used in telecommunications. In this paper we consider three problems that arise in SONET networks: (1) Weighted Ring Edge-Loading Problem (WRELP), (2) SONET Ring Assignment Problem (SRAP) and, (3) Intraring Synchronous Optical Network Design Problem (IDP), known to be NP-hard. WRELP asks for a routing scheme such that the maximum load on the edges of a ring will be minimum. In SRAP the objective is to minimise the number of rings (i.e., DXCs). In IDP the objective is to minimise the number of ADMs. The last two problems are subject to a ring capacity constraint. We study these three problems without demand splitting and for solving them we propose a Hybrid Scatter Search (HSS) algorithm. Coupled with the Scatter Search algorithm, we use a Tabu Search algorithm to locate the global minimum. We show that HSS is able to achieve feasible solutions, improving the results obtained by previous approaches.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Goralski, W.J.: SONET. McGraw-Hill Professional (2002)
Cosares, S., Saniee, I.: An optimistion problem related to balancing loads on SONET rings. Telecommunication Systems 3(2), 165–181 (1994)
Dell’Amico, M., Labbé, M., Maffioli, F.: Exact solution of the SONET Ring Loading Problem. Oper. Res. Lett. 25(3), 119–129 (1999)
Schrijver, A., Seymour, P., Winkler, P.: The ring loading problem. SIAM Journal of Discrete Mathematics 11, 1–14 (1998)
Goldschmidt, O., Laugier, A., Olinick, E.V.: SONET/SDH Ring Assignment with Capacity Constraints Discrete. Appl. Math. 129, 99–128 (2003)
Aringhieri, R., Dell’Amico, M.: Comparing Metaheuristic Algorithms for Sonet Network Design Problems. Journal of Heuristics 11, 35–57 (2005)
Pelleau, M., Van Hentenryck, P., Truchet, C.: Sonet Network Design Problems. In: EPTCS 5, LSCS 2009, pp. 81–95 (2009)
Lee, Y., Sherali, H.D., Han, J., Kim, S.: A Branch-and-Cut Algorithm for Solving an Intraring Synchronous Optical Network Design Problem. Networks 35, 223–232 (2000)
Goldschmidt, O., Hochbaum, D.S., Levin, A., Olinick, E.V.: The Sonet Edge-Partition Problem. Networks 41, 3–23 (2003)
Glover, F.: Heuristics for integer programming using surrogate constraints. Decision Sciences 8, 156–166 (1977)
Laguna, M.: Scatter search. In: Pardalos, P.M., Resende, M.G.C. (eds.) Handbook of Applied Optimistion, pp. 183–193. Oxford University Press (2002)
Myung, Y.S., Kim, H.G.: On the ring loading problem with demand splitting. Operations Research Letters 32(2), 167–173 (2004)
Wang, B.F.: Linear time algorithms for the ring loading problem with demand splitting. Journal of Algorithms 54(1), 45–57 (2005)
Kim, S.-S., Kim, I.-H., Mani, V., Kim, H.J.: Ant Colony Optimistion for SONET Ring Loading Problem. International Journal of Innovative Computing, Information and Control 4(7), 1617–1626 (2008)
Bernardino, A.M., Bernardino, E.M., Sánchez-Pérez, J.M., Vega-Rodríguez, M.A., Gómez-Pulido, J.A.: Solving ring loading problems using Bio-inspired algorithms. Journal of Network and Computer Applications 34(2), 668–685 (2011)
Bernardino, A.M., Bernardino, E.M., Sánchez-Pérez, J.M., Vega-Rodríguez, M.A., Gómez-Pulido, J.A.: Solving the ring arc-loading problem using a Hybrid Scatter Search Algorithm. In: International Conference on Evolutionary Computation (2010)
Aringhieri, R., Dell’Amico, M., Grasselli, L.: Solution of the sonet ring assignment problem with capacity constraints. Technical Report 12, DISMI. University of Modena and Reggio Emilia (2001)
Macambira, E.M., Meneses, C.N., Pardalos, P.M., Resende, M.G.C.: A novel integer programming formulation for the K-SONET ring assignment problem. AT&T Labs Research Technical Report TD-6HLLNR (2005)
Macambira, E.M., Maculan, N., Souza, C.C.: A column generation approach for SONET ring assignment. Networks 47(3), 157–171 (2006)
Bastos, L.O., Ochi, L.S., Macambira, E.M.: A relative neighbourhood GRASP for the SONET ring assignment problem. In: Proceedings of the International Network Optimization Conference, pp. 833–838 (2005)
Bastos, L.O., Ochi, L.S., Macambira, E.M.: GRASP with Path-Relinking for the SONET Ring Assignment Problem. In: Proc. Fifth International Conference on Hybrid Intelligent Systems (HIS 2005), pp. 239–244 (2005)
Bastos, L.O., Ochi, L.S.: A genetic algorithm with evolutionary path-relinking for the Sonet Ring Assignment Problem. In: International Conference on Engineering Optimization - EngOpt 2008, RJ. Proc. of the EngOpt 2008 - Sponsoring Societies: Mathematical Programming Society (MPS), ISSMO, EUROPT, ABCM. RJ : EngOpt, v. 1 (2008)
Laguna, M.: Clustering for the design of sonet rings in interoffice telecomunications. Management Sciennce 40(11), 1533–1541 (1994)
Glover, F., Laguna, M., Marti, R.: Scatter Search and Path Relinking: Advances and Applications. In: Handbook of Metaheuristics, vol. 57, pp. 1–35. Springer, Heidelberg (2003)
Bernardino, A.M., Bernardino, E.M., Sánchez-Pérez, J.M., Vega-Rodríguez, M.A., Gómez-Pulido, J.A.: A Hybrid Scatter Search Algorithm to Assign Terminals to Concentrators. In: IEEE Congress on Evolutionary Computation (CEC 2010), pp. 329–336. IEEE Computer Society, IEEE press, Los Alamitos (2010)
Glover, F., Laguna, M.: Tabu Search. Kluwer Academic Publishers (1997)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag GmbH Berlin Heidelberg
About this paper
Cite this paper
Bernardino, A.M., Bernardino, E.M., Sánchez-Pérez, J.M., Gómez-Pulido, J.A., Vega-Rodríguez, M.A. (2012). Solving SONET Problems Using a Hybrid Scatter Search Algorithm. In: Madani, K., Dourado Correia, A., Rosa, A., Filipe, J. (eds) Computational Intelligence. IJCCI 2010. Studies in Computational Intelligence, vol 399. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-27534-0_6
Download citation
DOI: https://doi.org/10.1007/978-3-642-27534-0_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-27533-3
Online ISBN: 978-3-642-27534-0
eBook Packages: EngineeringEngineering (R0)