Applying tabu search to spare capacity planning for network restoration

• Published in: Computers & operations research 1999-10, Vol.26 (12), p.1175-1194
• Main Authors: Shyur, Ching-Chir, Lu, Ta-Chien, Wen, Ue-Pyng
• Format: Article
• Language: English
• Subjects: Applied sciences; Capacity; Capacity planning; Computer programming; Exact sciences and technology; Job shops; Network management systems; Operations research; Studies; Systems, networks and services of telecommunications; Tabu search; Telecommunication network; Telecommunications; Telecommunications and information theory
• ISSN: 0305-0548; 1873-765X; 0305-0548
• DOI: 10.1016/S0305-0548(98)00102-6

This paper employs tabu search to solve the network spare capacity planning problem. Our study involves the determination of the necessary spare capacity on each link of a network required to achieve a certain desired level of restoration at minimum cost during network failure. We have developed here a procedure based on tabu search. The computational results show that the proposed tabu search algorithm offers an effective and efficient way for handling this network restoration problem. Scope and purpose Telecommunication network plays a crucial role in modern communication. An ever increasing number of end users are completely relying on telecommunication in their business activities today. The use and integration of computers with telecommunication have created a new information era. In order to provide the much desired broadband services, high capacity transport systems are widely adopted in the transmission network. While these systems offer great economic advantages through multiplexing and sharing of transmission facilities, they also increase the vulnerability of the telecommunication services dependent on them. If a failure occurs on a high speed facility of such a network, all the related services get affected. Network survivability has, therefore, become a major concern in broadband network planning. One of the methods to improve network survivability is to keep redundant or spare capacity for Digital Cross-Connect System (DCS) to restore failed services. However, the problem of spare capacity deployment on the links of a restorable network is NP-hard, implying exponential growth in execution time with network size for an exact solution. In this paper, an algorithm based on tabu search is proposed to find an approximate optimal solution for this problem.