A tabu search procedure is developed to solve fiber optic communication network design problems with survivability constraints. Two systematic improving heuristics: delete-add and delete-link procedures are presented. The conditions for the candidate links to be added and deleted in the two procedures are examined by considering the feasible structures of survivable network. A local improvement procedure is considered by combining the two heuristics for the downhill move in the tabu search. The tabu search is proved to avoid the local optima effectively. Computational results are discussed by comparing with a well-known heuristic procedure.
생존도를 고려한 광통신망 설계 문제에 대하여 Tabu Search 기법이 적용되었다. 망의 생존도로서 이중연결성(Two-Connectivity)이 요구되고, 두 개의 체계적인 개선 휴리스틱 Delete-Add 및 Delete-Link 알고리즘이 개발되었다. 두 개의 알고리즘에서 첨가하거나 삭제될 후보링크에 대한 조건이 망에 대한 구조적인 분석을 통해 얻어졌다.
두 개의 알고리즘과 기존의 Two-Optimal 휴리스틱을 혼합하여 Local Improvement 알고리즘이 개발되었고, 이는 기존의 알고리즘보다 더 효율적인 결과를 보여 준다. Tabu Search는 Local Improvement를 사용하는 Downhill Move와 새로운 해의 도출을 위한 Uphill Move로 이루어지고, 부분 최적해(Local Optima)를 효과적으로 극복하는 것으로 나타났다. 계산결과를 통한 비교에서 Tabu Search는 기존 알고리즘보다 3 - 7%의 비용절감효과를 얻었다.
