Abstract
隨著電信網路所提供的許多加值服務﹐電信網路已經成為人們生活中不可或缺的一部份﹐再加上電腦與電信網路的結合使得我們進入另一個嶄新的資訊時代。由於電信網路提供了許多重要的網路加值服務﹐使得電信網路的可靠度與存活度成為在電信網路設計與使用中一項重要的考量因素。也就是如何設計才能讓電信網路不容易發生錯誤､損壞或被破壞﹔再者﹐電信網路真正在運作而網路不幸有部份損毀時﹐如何補救才不會讓既有在網路上的資料流失並且可以迅速的繼續將資料傳送到目的地。電信網路備用容量 (spare capacity) 的設計就是提高網路可靠度與存活度中一種既經濟又有效的方法。當網路有損毀時﹐資料可經由原先設定之備用路線(restoration path) 在備用容量中傳送以達到資料的正確傳送。然而配置最佳的備用容量是一種複雜而困難的問題﹐因為每一個鍊路 (link) 的備用容量都可能與其他鍊路所共同分享。所以當一個備用容量的值改變時﹐就會造成原先設計的修復路線大幅更動而需重新安排。因此﹐這個問題到目前為止要求最佳解的時間是一個鍊路數的指數函數 (NP-hard)﹐也因此用數學規劃的方式求最佳解需要花費相當多的時間﹐所以本論文提出用塔布搜尋法在花不多的時間中尋求此問題的一個近似最佳解。由實驗結果中可以發現﹐利用塔布搜尋法所得到的結果穩定性很高﹐並且結果也與真正的最佳解差不多。可見塔布搜尋法確實提供了一個有效的方法來解決網路備用容量的配置問題。Telecommunication network plays an essential role in recentyears. More and more end users have an absolute dependency ontelecommunication today. The use and integration of computerswith telecommunication have created a new information age. Highbandwidths of services are provided in telecommunicationnetwork. Therefore, high survivable and reliable network shouldbe considered in network planning, network designing, andnetwork operations. Abundant spare capacity with the deploymentof reconfigurable DCS nodes greatly increase the survivabilityand reliability of network. However, finding an optimaldeployment of network spare capacity by the previous linearprogramming approach is well-known as NP-hard. In this thesisthe tabu search algorithm is proposed to get an approximateoptimal solution. Computational results show that the proposedtabu search algorithm provides an effective and efficient wayto handle this network restoration problem.