Tabu search for a network loading problem with multiple facilities

This paper examines a network design problem that arises in the telecommuni cations industry. In this problem, communication between a gateway vertex a nd a number of demand vertices is achieved through a network of fiber optic cables. Since each cable has an associated capacity (bandwidth), enough ca pacity must be installed on the links of the network to satisfy the demand, using possibly different types of cables. Starting with a network with no capacity or some capacity already installed, a tabu search heuristic is des igned to find a solution that minimizes the cost of installing any addition al capacity on the network. This tabu search applies a k-shortest path algo rithm to find alternative paths from the gateway to the demand vertices. Nu merical results are presented on different types of networks with up to 200 vertices and 100 demand vertices.