[Zurück]

P. Jahrmann, G. Raidl:
"Clique and independent set based grasp approaches for the regenerator location problem";
Vortrag: Metaheuristics International Conference (MIC), Singapore; 05.08.2013 - 08.08.2013; in: "Proceedings of the 10th Metaheuristics International Conference", (2013), S. 1 - 10.

We consider the Regenerator Location Problem (RLP) in optical fibre communication networks:
As optical signals deteriorate in dependence of the distance from the source, regenerator devices need
to be installed at a subset of the network nodes so that no segment of any communication path without
an intermediate regenerator exceeds an allowed maximum length. The objective is to place a smallest
possible number of regenerators in order to satisfy this condition. We propose two new construction
heuristics based on identifying and exploiting cliques and independent sets of the network graph.
These strategies are further extended to Greedy Randomized Adaptive Search Procedures (GRASP)
that also include new destroy and recreate local search phases. Excellent results are obtained in an
experimental comparison with a previously described GRASP.

http://publik.tuwien.ac.at/files/PubDat_225432.pdf