Optimizing a ring-based private line telecommunication network using Tabu Search

One of the private line network design problems in the telecommunications i ndustry is to interconnect a set of customer locations through a ring of en d offices so as to minimize the total tariff cost and provide reliability. We develop a Tabu Search method for the problem that incorporates long term memory, probabilistic move selections, hierarchical move evaluation, candi date list strategies and an elite solution recovery strategy. Computational results for test data show that the Tabu Search heuristic finds optimal so lutions for all test problems that can be solved exactly by a branch-and-cu t algorithm, while running about three orders of magnitude faster than the exact algorithm. In addition, for larger size problems that cannot be solve d exactly, the tabu search algorithm outperforms the best local search heur istic currently available. The performance gap favoring Tabu Search increas es significantly for more difficult problem instances.