Geoscience Reference
In-Depth Information
Clearly, these different decision making levels are not completely independent
and should be integrated as much as possible. However, due to complexity and
scalability issues, these levels are often treated separately.
Location problems in the telecommunications context appear mostly for deci-
sions related to the placement of specific equipments into nodes of the network.
These problems are closely related to hub location problems (Alumur and Kara
2008
). Note that common decisions that appear in most hub location and telecom-
munication optimization problems are routing decisions for demands between pairs
of nodes (while other location problems usually have demands associated to a single
node).
In this chapter, we focus on problems that have emerged recently (over the last 5
years) in the literature, that combine network design and equipment location in the
context of wired networks (typically fiber optic networks). For surveys of previous
work, see, e.g., Skorin-Kapov et al. (
2006
). To dig further, a unified view on location
and network design problems was recently proposed by Contreras and Fernández
(
2012
). The most basic application of equipment location is the Concentrator
Location Problem that we study in Sect.
20.2
. Using this model as building block,
we cover in Sect.
20.3
several variants of the Connected Facility Location Problem,
which received much attention recently as operators are trying to bring high-
capacity fiber-optic technologies closer to the customers. The Regenerator Location
Problem presented in Sect.
20.4
is an example of a problem that emerged only
recently as fiber optic cables have almost unlimited capacity, therefore allowing for
very sparse designs, but suffer from the degradation of the signal when it travels too
long distances. As its name suggests, the problem is concerned with the location of
equipments that allow to regenerate the signal to ensure transmission without loss
over long distances. Section
20.5
covers problems where some degree of resilience
to failures is provided by the usage of rings in the topology of the network. Multi-
period and network expansion problems are briefly discussed in Sect.
20.6
.Thelast
section concludes the chapter by describing some perspectives for future research
on the topic.
20.2
The Concentrator Location Problem
The (capacitated) Concentrator Location Problem is probably the most basic appli-
cation of equipment placement, and has received much attention in the literature,
see, e.g., Pirkul (
1987
), Boffey (
1989
), Balakrishnan et al. (
1991
), and Klincewicz
(
1998
). For a detailed survey of early work on the subject, see Chapter 2 in Yaman
(
2005
). The problem is to determine the number and location of concentrators that
are used to aggregate end-user demands before sending them on the backbone
network. In addition, the allocation of end-users network nodes to the concentrators
has to be determined, without violating the capacities of concentrators.
In this problem, the resulting network has a star-star topology, i.e., the subgraph
connecting a given concentrator to its assigned end-users is a star—end-users are
