Notice
This item was automatically migrated from a legacy system. It's data has not been checked and might not meet the quality criteria of the present system.
Jahrmann, P., & Raidl, G. (2013). Clique and independent set based grasp approaches for the regenerator location problem. In Proceedings of the 10th Metaheuristics International Conference (pp. 1–10). http://hdl.handle.net/20.500.12708/55032
E192-01 - Forschungsbereich Algorithms and Complexity
-
Published in:
Proceedings of the 10th Metaheuristics International Conference
-
Date (published):
2013
-
Event name:
Metaheuristics International Conference (MIC)
-
Event date:
25-Jul-2011 - 28-Jul-2011
-
Event place:
Udine, Italy, EU
-
Number of Pages:
10
-
Peer reviewed:
Yes
-
Abstract:
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
...
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.
