The telephonic switching centre network problem: Formalization and computational experience (Q1093558)

The switching centre network problem consists of looking for a topology on the urban street network that minimizes the total cost of cables and subterranean piping infrastructure necessary to link a telephonic centre and its subscribers. A simple version of the real model can be viewed as a mixture of Steiner's problem on graphs and a transhipment problem with a single source. We show that a very good initial solution for the problem can be obtained using Dijkstra's minimum distance algorithm. We discuss the theoretical background and the computational experience concerning a software for microcomputers that uses such an initialization strategy and that is running quite well in practice. We present the heuristic that looks for scale economies provenient from trajectory coincidences, a local optimum strategy, and also discuss global optimum strategies which should be tested following recent experience concerning Steiner's problem.