[en] We consider the problem of designing self-healing rings in order to protect the transmission of telecommunication demands in a zonal network. This problem stems from a real application with operational constraints such as dual homing and hop limit per ring. A modeling approach taking into account ring interactions is proposed as well as a tabu search heuristic for solving it. Computational results for a comprehensive set of real and randomly generated instances are presented.
Disciplines :
Quantitative methods in economics & management
Author, co-author :
Fortz, Bernard ; Université de Liège - ULiège > HEC Liège Research > HEC Liège Research: Business Analytics & Supply Chain Mgmt
Soriano, P.
Wynants, C.
Language :
English
Title :
A tabu search algorithm for self-healing ring network design
scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.
Bibliography
Altinkemer K. Topological design of ring networks. Computers and Operations Research. 21:1994;421-431.
K. Altinkemer, B. Kim, Heuristics for ring network design, Working paper, Krannert Graduate School of Management, Purdue University, 1994.
Armony M., Klincewicz J.G., Luss H., Rosenwein M.B. Design of stacked self-healing rings using a genetic algorithm. Journal of Heuristics. 6(1):2000;85-106.
J. Baudron, A. Khadr, F. Kocsis, Availability and survivability of SDH networks. Alcatel Electrical Communications, 1993, 4th Quarter, pp. 339-348.
Cosares S., Saniee I. An optimization problem related to balancing loads on SONET rings. Telecommunication Systems. 3:1994;165-181.
Cosares S., Deutsch D.N., Saniee I., Wasem O.J. SONET toolkit: A decision support system for designing robust and cost-effective fiber-optic networks. Interfaces. 25:1995;20-40.
Dell'Amico M., Labbé M., Maffioli F. Exact solution for the sonet ring loading problem. Operations Research Letters. 25:1999;119-129.
M. Di Lascio, A. Gambaro, U. Mocci. Protection Strategies for SDH Networks. Proceedings of the 6th International Network Planning Symposium - Networks'94, Budapest, Hungary, 1994, 4-9 September, pp. 387-392.
Glover F. Future paths for integer programming and links to artificial intelligence. Computers and Operations Research. 5:1986;533-549.
Glover F., Taillard E., de Werra D. A user's guide to tabu search. Annals of Operations Research. 41:1993;3-28.
Glover F., Laguna M. Tabu Search. 1997;Kluwer, Norwell, MA.
O. Goldschmidt, A. Laugier, E.V. Olinick, SONET/SDH ring assignment with capacity constraints. INFORMS Meeting, Montreal, Canada, 1998, 26-29 April (also working paper, Department of IE and OR, University of California, Berkeley).
Gomory R.E., Hu T.C. Multi-terminal network flows. SIAM Journal on Applied Mathematics. 9:1961;551-570.
P. Hansen, The steepest ascent mildest descent heuristic for combinatorial programming. Congress on Numerical Methods in Combinatorial Optimization, Capri, Italy, 1986.
J.L. Kennington, V.S.S. Nair, M.H. Rahman, Optimization based algorithms for finding minimal cost ring covers in survivable networks. Report 97-CSE-12, Department of Computer Science and Engineering, Southern Methodist University, 1997.
Klincewicz J.G., Luss H., Yan D.C.K. Designing tributary networks with multiple ring families. Working paper AT&T Labs, Holmdel, NJ 07733. Computers and Operations Research. 25(12):1997;1145-1157.
Labbé M., Laporte G., Soriano P. Covering a graph with cycles. Computers and Operations Research. 25:1998;499-504.
Laguna M. Clustering for the design of SONET rings in interoffice telecommunications. Management Science. 40:1994;1533-1541.
Luss H., Rosenwein M.B., Wong R.T. Topology network design for SONET ring architecture. IEEE Transactions on Systems, Man and Cybernetics. 28(06):1998;780-790.
Myung Y.-S., Kim H.-G., Tcha D.-W. Optimal load balancing on SONET bidirectional rings. Operations Research. 45:1997;148-152.
G. Pesant, P. Soriano, An optimal strategy for the constrained cycle cover problem. Research report CRT 98-51, Centre de recherche sur les transports, Université de Montréal, Annals of Mathematics and Artificial Intelligence, in press.
P. Semal, K. Wirl, Optimal clustering and ring creation in the network planning system PHANET. Proceedings of the 6th International Network Planning Symposium-Networks'94. Budapest, Hungary, 4-9 September 1994, pp. 303-308.
Schrijver A., Seymour P.D., Winkler P. The ring loading problem. SIAM Journal of Discrete Mathematics. 11(1):1998;1-14.
J.B. Slewinsky, W.D. Grover, M.H. MacGregor, An algorithm for survivable network design employing multiple self-healing rings, Proceedings of IEEE GLOBECOM'93, 1993, pp. 1568-1573.
Soriano P., Gendreau M. Diversification strategies in tabu search algorithms for the maximum clique problem. Annals of Operations Research. 63:1996;189-207.
Soriano P., Gendreau M. Fondements et applications des méthodes de recherche avec tabous. RAIRO. 31(2):1997;133-159.
Soriano P., Wynants C., Séguin S., Labbé M., Gendreau M., Fortz B. Design and dimensioning of survivable SDK networks. Sansò B., Soriano P. Telecommunications Network Planning. 1998;149-169 Kluwer, Norwell, MA.
Sosnosky J., Wu T.H. SONET ring applications for survivable fiber loop networks. IEEE Communications Magazine. (June):1991;51-58.
A. Sutter, J.L. Fullsack. SDH network planning in a changing environment, Proceedings of the 6th International Network Planning Symposium-Networks'94. Budapest, Hungary, 4-9 September 1994, pp. 149-154.
Sutter A., Vanderbeck F., Wolsey L.A. Optimal placement of add/drop multiplexers: Heuristic and exact algorithms. Operations Research. 46(5):1998;719-728.
Wasem O.J. An algorithm for designing rings for survivable fiber networks. IEEE Transactions on Reliability. 40:1991;428-432.
O.J. Wasem, R.H. Cardwell, T.H. Wu. Software for designing survivable sonet networks using self-healing rings. Proceedings of IEEE International Conference on Communication (ICC'92), 1992, pp. 425-431.
Wasem O.J., Wu T.H., Cardwell R.H. Survivable SONET networks - design methodologies. IEEE Journal on Selected Areas in Communications. 12:1994;205-212.
Wu T.H., Kolar D.J., Cardwell R.H. Survivable network architectures for broad-band fiber optic networks: Models and performance comparison. IEEE Journal of Lightwave Technology. 6:1988;1698-1709.
Wu T.H. Fiber Network Service Survivability. 1992;Artech House, Boston, MA.
Similar publications
Sorry the service is unavailable at the moment. Please try again later.
This website uses cookies to improve user experience. Read more
Save & Close
Accept all
Decline all
Show detailsHide details
Cookie declaration
About cookies
Strictly necessary
Performance
Strictly necessary cookies allow core website functionality such as user login and account management. The website cannot be used properly without strictly necessary cookies.
This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.
Performance cookies are used to see how visitors use the website, eg. analytics cookies. Those cookies cannot be used to directly identify a certain visitor.
Used to store the attribution information, the referrer initially used to visit the website
Cookies are small text files that are placed on your computer by websites that you visit. Websites use cookies to help users navigate efficiently and perform certain functions. Cookies that are required for the website to operate properly are allowed to be set without your permission. All other cookies need to be approved before they can be set in the browser.
You can change your consent to cookie usage at any time on our Privacy Policy page.
