Tailoring Neighborhood Search for the Internet Protocol Network Design Problem with Reliability and Routing Constraints

The Internet Protocol Network Design Problem with Reliability and Routing Constraints (IPRR) can be shortly stated as follows. A telecommunication network is given in terms of a set of nodes and a set of traffic demands; we want to define the minimum cost capacity reservation such that all the traffic is routed even under fault scenarios. Capacity is provided by reserving some already installed devices of a given capacity between pairs of nodes and traffic must be loaded on the network according to the OSPF-ECM (Open Shortest Path First-Equal Commodity Multipath) protocol, with additional constraints on the maximum number of hops. The problem is NP-Hard and literature proposes neighborhood search heuristics that do not take the reliability and max-hop requirements into account, or assume a simplified OSPF routing. The design and the implementation of the components of any neighborhood search algorithms are strongly conditioned by the reliability and routing constraints, which imply a huge amount of hop-constrained shortest paths to be taken into account. This work shows how the components of these heuristics can be implemented, with particular emphasis to the setting up of an efficient neighborhood evaluation procedure, the discussion of its incremental version, and the introduction of effective reduced-size neighborhoods. Computational experiments on instances derived from real networks are also presented, and they show the proposed components make the neighborhood search a viable approach for IPRR.