Tabu search for dynamic routing communications network design

This paper presents a tabu search approach for optimizing the link capacities in a dynamic routing telecommunications network. The traffic between any two nodes in the network is routed over a one-link direct path 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 each link in the network to minimize cost while satisfying the grade-of-service constraints. Although the problem can be formulated as a nonlinear 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 and coordinated solution recovery strategies. The macro level of the algorithm iteratively determines an hour for possible improvement and then the micro level seeks to optimize the routing paths for that hour. Our computational experience with both real and simulated problems indicates that significant savings can be obtained by this approach over the conventional network designs.