Network design using Genetic Algorithm

Abstract

Network Design Problems are becoming increasingly critical & complex as telecommunication networks (and others) are expanded & upgraded in response to consumer’s information needs. Network design is used extensively in practice in an ever expanding spectrum of applications. Network optimization models such as shortest path, assignment, maxflow, transportation, transshipment, spanning tree, matching, traveling salesman, generalized assignment, vehicle routing, and multicommodity flow constitute the most common class of practical network optimization problems. In this research work, a generalized network design problems (NDPs) is focused in the form of a large scale backbone network which belong to the family of NP-hard combinatorial optimization problems. The purpose of the backbone is to connect regional distribution networks and, in some instances, to provide connectivity to other peer networks. The primary objective of this research work is to develop a robust method based on genetic algorithm to solve NP-hard network design problem with minimum cost subject to a reliability constraint which meets the customer requirement. One fundamental problem in this area is the minimum spanning tree (MST) problem where all nodes in a graph have to be linked together in a circle-free structure in the cheapest possible way. The MST problem itself is easy to solve by polynomial-time algorithms like those of Prim or Kruskal, but adding additional constraints often make the corresponding optimization problem a hard one. One of these related problems is the degree-constrained MST problem, in which degree of each node is restricted with in a given range which is very important for the reliability and priority of the connecting node. Other possible constraints are path failure, node failure and connectivity which are requirement of the current network system. By adding this constraint, this network design problem becomes one of the hardest problems in NP-hard category. Due to the complexity of the problem these approaches are limited to relatively small instances with clearly less than 100 nodes when considering complete graphs. Therefore, in this research work methods have been developed to solve instances with up to 1000 and are applicable for more than 1000 nodes.