A ring generation problem based on the traveling salesman subtour problem
2003 (English)Report (Other academic)
Survivability and high redundancy are two critical issues in field of telecommunications. If a telecommunication network is built up by rings, high redundancy can be established, since the traffic can be sent in either direction. Traffic is usually sent using one direction, and if a failure occurs, the opposite direction is used. There is often a number of requirements on a ring, such as a limit on the number of connected nodes. This means that the network will include a number of rings, and traffic between rings must be possible. Therefore, a network must include a number of transit nodes, where it is possible to send traffic between the rings. We focus on the case where network includes two transit nodes and each ring must include at least one transit node. Since the number of rings is enormous one needs to generate rings.
This paper discusses how to generate new rings, given that each node has a reward for connecting the node to the ring. The problem that occurs is a modification of a traveling salesman subtour problem with a additional constraint on the number of nodes connected. A problem formulation is given and some solution approaches are suggested. Two different scenarios are discussed, one where the aim is to modify an already existing ring, and one where the aim is to build a complete new ring. Some computational results are given for a real data network.
Place, publisher, year, edition, pages
Linköping: Linköpings universitet , 2003. , 27 p.
LiTH-MAT-R, ISSN 0348-2960 ; 19
traveling salesman subtour problem, orienteering problem, prize collecting travelling salesman problem, ring generation
IdentifiersURN: urn:nbn:se:liu:diva-22369Local ID: 1577OAI: oai:DiVA.org:liu-22369DiVA: diva2:242682