A Constraint-based Local Search for Designing Tree Networks with Distance and Disjoint Constraints
Refereed Conference Meeting Proceeding
In many network design problems clients are re- quired to be connected to a facility under path-length constraints and budget limits. Each facility is associated with a tree network where the root is the facility itself and the remaining nodes of the tree are its clients. An inherent feature of these networks is that they are vulnerable to a failure. Therefore, it is often important to provide some resiliency in the network. We focus on a problem where we want to ensure that all clients are connected to two facilities so that if one facility fails then all clients can still be served by another facility. Optionally, one might require that each client is resilient to a single link or node failure by enforcing that the paths used to connect a client to its two facilities are either edge-disjoint or node-disjoint respectively. In this paper we use local search to evaluate the trade-off between cost versus resiliency and coverage versus resiliency for a real-world problem in the field of optical networks.
7th International Workshop on Reliable Network Design and Modelling (RNDM 2015)
Digital Object Identifer (DOI):
National University of Ireland, Cork (UCC)
Open access repository: