Optimizing the system of virtual paths by tabu search

In an asynchronous transfer mode (ATM) network, given the network topology and traffic demands, the establishment of the system of virtual paths (VPs), and the assignment of connections to them so that the network performance is optimized, entails a number of computationally hard subproblems. The optimization problem discussed here focuses on finding a system of VP routes for a given set of VP terminators and VP capacity demands. Although it has been proven that the existing random path algorithm yields the worst case time bound, the solution performance still depends highly on the number of iterations. In this paper, an exact solution procedure and a heuristic method based on a simple tabu search have been developed for optimizing the system of VPs. Computational results show that the proposed tabu search algorithm is effective in obtaining high quality solutions, and the performance of the proposed algorithm is increasingly attractive as the problem size becomes larger.