O.R. Applications
The network design problem with relays

https://doi.org/10.1016/j.ejor.2006.04.030Get rights and content

Abstract

The network design problem with relays (NDPR) is defined on an undirected graph G = (V, E, K), where V = {1,  , n} is a vertex set, E = {(i, j) : i, j  V, i < j} is an edge set. The set K = {(o(k), d(k))} is a set of communication pairs (or commodities): o(k)  V and d(k)  V denote the origin and the destination of the kth commodity, respectively. With each edge (i, j) are associated a cost cij and a length dij. With vertex i is associated a fixed cost fi of locating a relay at i. The NDPR consists of selecting a subset E¯ of edges of E and of locating relays at a subset V¯ of vertices of V in such a way that: (1) the sum Q of edge costs and relay costs is minimized; (2) there exists a path linking the origin and the destination of each commodity in which the length between the origin and the first relay, the last relay and the destination, or any two consecutive relays does not exceed a preset upper bound λ. This article develops a lower bound procedure and four heuristics for the NPDR. These are compared on several randomly generated instances with |V|  1002 and |E|  1930.

Introduction

The network design problem with relays (NDPR) is defined on an undirected graph G = (V, E, K), where V = {1,  , n} is a vertex set, E = {(i, j) : i, j  V, i < j} is an edge set. The set K = {(o(k), d(k))} is a set of communication pairs (or commodities): o(k)  V and d(k)  V denote the origin and the destination of the kth commodity, respectively. With each edge (i, j) are associated a cost cij and a length dij. With vertex i is associated a fixed cost fi of locating a relay at i. The NDPR consists of selecting a subset E¯ of edges of E and of locating relays at a subset V¯ of vertices of V in such a way that: (1) the sum Q of edge costs and relay costs is minimized; (2) there exists a path linking the origin and the destination of each commodity for which the length between the origin and the first relay, the last relay and the destination, or any two consecutive relays does not exceed a preset upper bound λ. This constraint distinguishes the NDPR from standard network design problems. We believe network design problems with relays have never previously been addressed, apart from two exceptions described below.

Fig. 1 depicts a graph where K = {(1,7), (1,8), (2,8), (3,9)} and λ = 5. The length of each edge is indicated. A feasible NDPR solution consists of selecting the bold edges (1,4), (1,5), (2,5), (3,6), (4,7), (5,8), and (6,9) and of locating a relay at vertex 5.

This study is motivated by a telecommunications network design project in which the aim is to connect 422 communities in Alberta. In this problem there is a single origin and several destinations, so that the solution is a tree. The relays are repeaters which regenerate the signal(s) entering a vertex, and the value of λ is equal to 70 km.

The most recent reviews in network design problems are provided by Balakrishnan et al., 1997, Raghavan and Magnanti, 1997. Costa (2005) focuses his survey on Benders decomposition applied to fixed-charge network design problems, providing important insights in network design problem decomposition. One can trace a weak parallel between the NDPR and the hop constrained network design problem (HCNDP), where the number of arcs between the origin and the destination must respect a given threshold. Gouveia (1998) provides a survey on tree topology network design with hop-constraints. Voss (1999) considers a variant of the Steiner tree problem where hop-constraints are present, and proposes a solution heuristic based on tabu search. Gouveia and Requejo (2001) solve the hop-constrained minimum spanning tree problem using Lagrangean relaxation. Soni (2001) considers the HCNDP with partial survivability. De Giovanni et al. (2004) present a study on how hop constraints can impact network design solutions.

Generally, network design problems focus on arc costs and do not take into account the cost of installing equipment at the nodes. Tcha and Yoon (1995) constitute an exception: they discuss fixed costs both along the edges and at the nodes and provide for signal bundling and switching. To model the problem, they assume that each region must have one hub assigned to it. This leads to a facility location model which is solved by a dual-based heuristic. Yoon et al. (1998) present an extension of this work. Examples of network design applications, but without optimization, are provided by Cosares et al., 1995, Cortes et al., 2001, Davis et al., 2001.

The NDPR generalizes the shortest path problem with relays (SPPR) (Cabral et al., 2005) and the weight constrained shortest path problem (WCSPP) (Dumitrescu and Boland, 2003), both of which are NP-hard. The SPPR is a special case of the NDPR with |K| = 1, while the WCSPP consists of determining on a network a least cost path of length not exceeding λ.

The aim of this article is to develop a lower bound and four heuristics for the NDPR. The lower and upper bounding procedures are described in Sections 2 Lower bounding procedure, 3 Heuristics, followed by computational results in Section 4 and conclusions in Section 5.

Section snippets

Lower bounding procedure

The lower bounding procedure we have developed for the NDPR is based on an integer linear programming formulation of the problem. As is often the case in combinatorial optimization, several formulations are available for the NDPR. We experimented with four different formulations (an undirected and a directed flow formulation; an undirected and a directed column generation formulation). After preliminary computational tests, we opted for a directed column generation formulation which seems

Heuristics

We developed four construction heuristics for the NDPR. The first heuristic, called construction heuristic 1 (CH1), consists of constructing the network by considering one commodity at a time. The second heuristic, called increasing order heuristics (IOH), consists of constructing the network one commodity at a time, ranking them in increasing cost of implementation. The third heuristic, called decreasing order heuristic (DOH), consists of constructing the network one commodity at a time,

Computational results

We carried out all computational tests out on a Sun Fire 480R station with four 900 MHz processors, 16 gigabytes of RAM and a Sun Solaris 5.7 operational system. We coded the algorithms in C++ and compiled them with a Sun Forte Developer 7 C++ compiler. We used CPLEX 8.0 to solve the linear programs in the column generation procedure.

The test graphs follow a grid structure, with a rows and b columns and randomly (uniformly) generated integer values for costs and lengths. Cost and edge length

Conclusions

We introduced the network design problem with relays and proposed a lower bound as well as four heuristics for its solution. The lower bound is obtained through column generation using the SPPR as a subproblem. The first heuristic is a modification of the construction heuristic by Takahashi and Matsuyama (1980) for the Steiner tree problem. The second and third heuristics check whether biasing the first construction heuristic could improve its solution. Finally, the fourth heuristic explores

Acknowledgments

This work was partially supported by the Canadian Natural Sciences and Engineering Research Council under Grants CRD 268431, OGP 25481 and OGP 39682. This support is gratefully acknowledged. Thanks are due to Fatma Gzara, Osman Alp and the referees for their valuable comments.

References (17)

  • A.M. Costa

    A survey on Benders decomposition applied to fixed-charge network design problems

    Computers & Operations Research

    (2005)
  • L. Gouveia et al.

    A new Lagrangean relaxation approach for the hop-constrained minimum spanning tree problem

    European Journal of Operational Research

    (2001)
  • A. Balakrishnan et al.

    Network design

  • Cabral, E.A., Erkut, E., Laporte, G., Tjandra, S.A., 2005. The shortest path problem with relays, Working...
  • P. Cortes et al.

    Decision support system for planning telecommunication networks: A case study applied to the Andalusian region

    Journal of the Operational Research Society

    (2001)
  • S. Cosares et al.

    Sonet toolkit: A decision support system for designing robust and cost-effective fiber-optic networks

    Interfaces

    (1995)
  • R.D. Davis et al.

    Spider: A simple and flexible tool for design and provisioning of protected lightpaths in optical networks

    Bell Labs Technical Journal

    (2001)
  • L. De Giovanni et al.

    On the impact of the solution representation for the internet protocol network design problem with max-hop constraints

    Networks

    (2004)
There are more references available in the full text version of this article.

Cited by (50)

  • Optimization of maritime support network with relays under uncertainty: A novel matheuristics method

    2023, Reliability Engineering and System Safety
    Citation Excerpt :

    Thus, the objective function is represented as the total weighted cost, which can be divided into fixed and variable costs according to economic theory [29], and is widely used in engineering and industrial research [30]. From the network design perspective [22], the total cost can be broadly defined as edge and relay costs. Consequently, the total weighted cost of the proposed optimization model consists of the weighted transportation cost for rescue missions under uncertainty (i.e., variable or edge cost) and the construction cost of relay stations (i.e., fixed or relay cost).

View all citing articles on Scopus
View full text