TABU SEARCH FOR DYNAMIC ROUTING COMMUNICATIONS NETWORK DESIGN

This paper presents a tabu search approach for optimizing the link cap acities in a dynamic routing telecommunications network. The traffic b etween any two nodes in the network is routed over a one-link direct p ath or, if no direct capacity is available, over a two-link alternate path. The alternate routing paths can be changed dynamically from hour to hour as the traffic between pairs of nodes may vary with the time of day. The problem is to determine the optimal capacity level for eac h link in the network to minimize cost while satisfying the grade-of-s ervice constraints. Although the problem can be formulated as a nonlin ear integer programming problem, no efficient solution procedures are available. In this paper, we develop a two-level tabu search heuristic for solving the problem that utilizes probabilistic move selection an d coordinated solution recovery strategies. The macro level of the alg orithm iteratively determines an hour for possible improvement and the n the micro level seeks to optimize the routing paths for that hour. O ur computational experience with both real and simulated problems indi cates that significant savings can be obtained by this approach over t he conventional network designs.