The telephonic switching centre network problem: Formalization and computational experience
type: Item
instance of: scholarly article
title: The telephonic switching centre network problem: Formalization and computational experience
zbMATH Open document ID: 0628.90087
DOI: 10.1016/0166-218X(87)90021-7
author: Nivio Ziviani
author: Regina Helena B. Cabral
author: Henrique Pacca Loureiro Luna
published in: Discrete Applied Mathematics
publication date: 1987-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 94C15
zbMATH DE Number: 4023053
zbMATH Keywords: switching centre network problem
zbMATH Keywords: urban street network
zbMATH Keywords: Steiner's problem on graphs
zbMATH Keywords: transhipment
zbMATH Keywords: minimum distance algorithm
zbMATH Keywords: heuristic
MaRDI profile type: Publication
cites work: A dual ascent approach for steiner tree problems on a directed graph
cites work: An integer linear programming approach to the steiner problem in graphs
cites work: On the shortest spanning subtree of a graph and the traveling salesman problem
cites work: A note on two problems in connexion with graphs
cites work: Q3844775
cites work: Optimal Facility Location with Concave Costs
cites work: An algorithm for the steiner problem in graphs
description: scientific article; zbMATH DE number 4023053