A genetic algorithm based heuristic for survivable networks design with p-Cycles

REMBERTO EMANUEL DELGADILLO; IRENE LOISEAU

Santiago

Congreso; XVIII CLAIO, Latin-Iberoamerican Conference on Operations Research; 2016

Pontificia Universidad Católica de Chile, en conjunto con ALIO e ICHIO.

p-Cycles are structures intended to providesurvivability to optical networks. Each p-Cycle providesone protection channel to each span it crosses, and twoprotection channels to each span that is not in the cyclebut its ending nodes are. The Spare Capacity Allocationproblem requires protecting all working demands againstany span failure with p-cycles at minimum cost. We proposehere a greedy heuristic that builds a solution for thisproblem iteratively. At each step, a Genetic Algorithmbuilds a cycle trying to maximize the Actual Eciency,which was dened in the literature for developing anothergreedy heuristic for this problem. To achieve this, wepropose to decode cycles from 0-1 genes representing fundamentalcycles of a basis of cycle space. We give twoalternatives for tness evaluation to treat disjoint cyclesor closed walks with repeated nodes. Several computationalexperiments were performed and promising resultswere obtained.