A tabu search algorithm for self-healing ring network design

[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

Publication date :

2003

Journal title :

European Journal of Operational Research

ISSN :

0377-2217

eISSN :

1872-6860

Volume :

151

Issue :

Pages :

280-295

Peer reviewed :

Peer Reviewed verified by ORBi

Additional URL :

https://www.scopus.com/inward/record.uri?eid=2-s2.0-0042522845&doi=10.1016%2fS0377-2217%2802%2900826-3&partnerID=40&md5=d26f849703c2680c3166cf99c7869b8c

Available on ORBi :

since 15 May 2024

Statistics

Number of views

6 (0 by ULiège)

Number of downloads

13 (0 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

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.