Geoscience Reference
In-Depth Information
of our knowledge, no heuristic algorithm has been proposed to tackle large-size
instances of the problem.
20.6
Network Expansion and Multi-Period Problems
Models covered so far in this chapter consider telecommunications networks that are
built from scratch. This static (single-step) setting is not realistic in all situations, and
network operators are sometimes faced to the upgrading of an existing network. As
stated in the introduction of this chapter, a network is often composed of a backbone
network, for the transfer of large volumes of data, and local access networks that
connect terminals to an access node of the backbone network. Network capacity
expansion problems for backbone networks have been studied since the pioneering
work of Balakrishnan et al. (
1991
).
For local access networks, a basic model, in which growing demand can
be satisfied by expanding cable capacities and/or installing concentrators in the
network, was introduced by Balakrishnan et al. (
1995
). They showed that the
problem is NP-hard and proposed a Lagrangian-based decomposition heuristic to
solve it. Flippo et al. (
2000
) later showed that the problem is weakly NP-hard
and presented a pseudo-polynomial dynamic programming algorithm. A multi-
period expansion problem for the particular case of a local access network that
has a tree topology was solved heuristically by Gendreau et al. (
2006
). Gourdin
and Klopfenstein (
2008
) studied a multi-period capacitated problem with modular
concentrators and link capacities. They proposed an integer linear model, and after
a polyhedral analysis of the problem, presented some facet-defining inequalities.
20.7
Conclusions
This chapter described some applications of location problems in telecommunica-
tions. Some of these problems have been studied only recently, and advances in
understanding their structure to provide better exact algorithms are still necessary.
Furthermore, these problems have been mostly studied in their uncapacitated
versions. Since capacitated versions are usually much harder to solve, it is expected
that they will attract more interest in the near future. Additionally, demands in
the telecommunications industry fluctuate a lot, and the development of robust
optimization approaches has emerged as a hot topic. The development of robust
counterparts for the problems presented in this chapter is therefore another impor-
tant trend for future research. If probability distributions can be associated to
demand and/or failure scenarios, stochastic programming approaches might be used,
although the literature on the subject is currently very limited. Finally, advances in
heuristics are still expected for some of these problems, in order to tackle very large
scale instances.
