Abstract

Given an undirected graph G<span id="cke_bm_89S" style="display: none;"> </span><span id="cke_bm_86S" style="display: none;"> </span><span id="cke_bm_84S" style="display: none;"> </span>1<span id="cke_bm_89E" style="display: none;"> </span><span id="cke_bm_86E" style="display: none;"> </span><span id="cke_bm_84E" style="display: none;"> </span> = (V<span id="cke_bm_90S" style="display: none;"> </span><span id="cke_bm_87S" style="display: none;"> </span>_{1<span id="cke_bm_90E" style="display: none;"> </span><span id="cke_bm_87E" style="display: none;"> </span>}, E<span id="cke_bm_91S" style="display: none;"> </span>₁<span id="cke_bm_91E" style="display: none;"> </span>), a c<span id="cke_bm_88E" style="display: none;"> </span>omplete undirected <span id="cke_bm_85E" style="display: none;"> </span>and weighted graph G_{<span id="cke_bm_92S" style="display: none;"> </span>2<span id="cke_bm_92E" style="display: none;"> </span>} = (V₂, E₂, c) and a set of <span id="cke_bm_93E" style="display: none;"> </span>customers’ demands. The goal is to design connections based on customers’ demands with the smallest network cost to protect the network against all failures. This problem is NP-hard. This paper proposes a genetic algorithm for solving the Survivable Network Design Problem (SNDP). We experiment our proposed algorithm on random [12] and real world instances [1]. The experimental results are reported to show the efficiency of proposed algorithm comparing to the Branch and Price algorithm [1].