A ring network design problem and heuristics for generating a set of feasible rings
2003 (English)Report (Other academic)
We discuss the problem of designing a telecommunication network with the survivability requirement that the network should be composed of connected rings of links. The work design problem is then to choose links from a given network, and compose them into a number of rings. Furthermore, the rings should be connected at certain transit nodes. The traffic between rings may pass through other rings. Each ring is associated with a certain fixed cost depending on the length of the ring. We describe the problem, modeled as a linear integer programming problem. We find a feasible solution to the problem by first find good rings in the network using two heuristics, and then solve the optimization model using only these rings. Finally, we give some computational results for different networks.
Place, publisher, year, edition, pages
Linköping: Linköpings universitet , 2003. , 33 p.
LiTH-MAT-R, ISSN 0348-2960 ; 16
IdentifiersURN: urn:nbn:se:liu:diva-22367Local ID: 1575OAI: oai:DiVA.org:liu-22367DiVA: diva2:242680