GRASP heuristics for Wide Area Network design

Abstract

A wide area network (WAN) can be considered as a set of sites and a set of communication lines that interconnect the sites. Topologically a WAN is organized in two levels: the backbone network and the access network composed of a certain number of local access networks. Each local access network usually has a tree-like structure, rooted at a single site of the backbone, and connects users (terminal sites) either directly to this backbone site or to a hierarchy of intermediate concentrator sites which are connected to the backbone site. The backbone network has usually a meshed topology, and its purpose is to allow efficient and reliable communication between the switch sites that act as connection points for the local access networks. In this thesis we tackled the problem of designing a WAN by breaking it down into two inter-related sub-problems: the Access Network Design Problem (ANDP) and the Backbone Network Design Problem (BNDP). In both models we considered only the construction costs, e.g. the costs of digging trenches and placing a fiber cable into service. We modeled the ANDP as a variant of the Steiner Problem in Graphs (SPG), and the BNDP on the basis of the Generalized Steiner Problem with Node-Connectivity Constraints (GSP-NC). In addition, we studied the specific case of BNDP when there exist 2-node-survivability requirements between pairs of backbone fixed nodes. We call it BNDP2NS and it is analogous to the Steiner 2-node-survivable network problem (STNSNP). ANDP, BNDP, and BNDP2NS are NP-Hard problems. Our goal was to attack the ANDP, BNDP, and BNDP2NS models heuristically. We opted for the GRASP (Greedy Randomized Adaptive Search Procedure) methodology for solving them. GRASP is a powerful method which has been used with success to find good quality solutions to many combinatorial optimization problems. We developed GRASP algorithms for these three problems, designing different alternative algorithms for the construction and local each phases