[Zurück]

M. Leitner, I. Ljubic, M. Riedler, M. Ruthmair:
"Exact Approaches for Network Design Problems with Relays";
Informs Journal on Computing, 31 (2019), 1; 23 S.

In this article we consider the network design problem with relays (NDPR),
which gives answers to some important strategic design questions in telecommunication
network design. Given a family of origin-destination pairs and a set of existing links these
questions are as follows: (1) What are the optimal locations for signal regeneration devices
(relays) and how many of them are needed? (2) Could the available infrastructure be
enhanced by installing additional links in order to reduce the travel distance and therefore
reduce the number of necessary relays?
In contrast to previous work on the NDPR, which mainly focused on heuristic approaches,
we discuss exact methods based on different mixed-integer linear programming
formulations for the problem. We develop branch-and-price and branch-price-andcut
algorithms that build upon models with an exponential number of variables (and
constraints). In an extensive computational study, we analyze the performance of these
approaches for instances that reflect different real-world settings. Finally, we also point
out the relevance of the NDPR in the context of electric mobility.

http://dx.doi.org/10.1287/ijoc.2018.0820

https://publik.tuwien.ac.at/files/publik_280650.pdf