liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A ring network design problem and heuristics for generating a set of feasible rings
Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.ORCID iD: 0000-0001-5907-0087
Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
Linköping University, Department of Science and Technology. Linköping University, The Institute of Technology.
2003 (English)Report (Other academic)
Abstract [en]

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. , p. 33
Series
LiTH-MAT-R, ISSN 0348-2960 ; 16
National Category
Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-22367Local ID: 1575OAI: oai:DiVA.org:liu-22367DiVA, id: diva2:242680
Available from: 2009-10-07 Created: 2009-10-07 Last updated: 2013-08-29
In thesis
1. Ring network design in telecommunications: optimization based solution approaches
Open this publication in new window or tab >>Ring network design in telecommunications: optimization based solution approaches
2003 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

When designing a telecommunication network, one often wish to include some kind of survivability requirement, for example that the network should be two-connected. A two-connected network fulfills the requirement that there should be at least two paths with no links in common between all pairs of nodes. One form of design model is to prescribe that the network should be composed of connected rings of links. The network design problem is then to choose links from a given network, and compose them into a number of rings. A ring is reliable in the sense that there always exist two ways of sending traffic, clockwise or counter-clockwise, which means that a ring fulfills the two-connectivity requirement. There is often a number of requirements on a ring, such as a limited length and limited number of nodes connected to the ring. This means that a ring network will include a number of rings, and traffic between rings must be possible. The traffic between rings is usually made at certain nodes, called transit nodes. Therefore all rings should be connected to at least one of the transit nodes. We focus on the case where we have two transit nodes in the network.

Each possible ring is associated with a certain fixed cost, and all links in a certain ring are given the same capacity. Reserve capacity is allocated according to certain principles. The number of possible rings in a network is an exponential function of the number of nodes in the network, so for larger networks is it impossible to a priori generate all possible rings.

We describe the problem, and model it as a linear integer programming problem, where a set of rings are assumed to be known. The usage of rings, i.e., the allocation of demand to rings, is determined. In practice, too many rings can not be included in the model. Instead we must be able to generate useful rings. A Lagrangean relaxation of the model is formulated, and the dual solution is used in order to derive reduced costs which can be used to generate new better rings. The information generated describes only the physical structure of the ring, not the usage of it. The ring generation problem is a modified traveling salesman subtour problem, which is known to be difficult to solve. Therefore, we focus on heuristic solution methods for this problem.

We also presents a column generation approach where the problem is modeled as a set covering problem. Here, a column describes both the topology of the ring and the exact usage of it. A similar ring generation problem appears as a subproblem, in order to generate new rings.

All methods are computationally tested on both real life data and randomly generated data, similar to real life problems.

Place, publisher, year, edition, pages
Linköping: Linköpings universitet, 2003. p. 14
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 829
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-22357 (URN)1563 (Local ID)91-7373-668-6 (ISBN)1563 (Archive number)1563 (OAI)
Public defence
2003-05-28, Glashuset, Hus B, Linköpings Universitet, Linköping, 10:15 (Swedish)
Opponent
Available from: 2009-10-07 Created: 2009-10-07 Last updated: 2013-01-14

Open Access in DiVA

No full text in DiVA

Authority records

Henningsson, MathiasHolmberg, KajRönnqvist, MikaelVärbrand, Peter

Search in DiVA

By author/editor
Henningsson, MathiasHolmberg, KajRönnqvist, MikaelVärbrand, Peter
By organisation
Department of MathematicsThe Institute of TechnologyDepartment of Science and Technology
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 521 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf