Heuristic Algorithms for Solving Survivability Problem in the Design of Last Mile Communication Networks

摘要

Given a connected, weighted, undirected graph G = (V, E), a set infrastructure nodes and a set customers C includes two customer types where by customers C1 require a single connection (type-1) and customers C2 need to be redundantly connected (type-2). Survivable Network Design Problem (SNDP) seeks sub-graph of G with smallest weight in which all customers are connected to infrastructure nodes. This problem is NP-hard and has application in the design of the last mile of the real-world communication networks. This paper proposes a new heuristic algorithm for solving SNDP. Results of computational experiments are reported to show the efficiency of proposed algorithm.