Hybrid heuristic for Capacitated Network Design Problem

Abstract

This paper deals with the NP-hard Capacitated Network Design Problem (CNDP) with modular link capacity structure. We aim to optimize the underlying network, the allocation facilities and the transportation costs. It is assumed that for connecting two nodes, a fixed construction link cost is occurred or a specific unit transportation cost. There are several types of module facilities to allocate on links. In this paper, we propose a general model that combines design, allocation and routing problems. An hybrid approach is proposed which uses a greedy constructive and an iterative local search heuristics. Our proposition is tested on the Survivable fixed telecommunication Network Design Library (SNDlib) and a comparison of its performances against the best solution available in the literature is done. Computational tests show that our proposition is very efficient.

Keywords

Capacitated network design facility allocation modular capacity iterative local search greedy search SNDlib

1. Introduction

Network design models have a wide application in telecommunication and, transportation planning [14,16,17]. In these applications, it is required to send flows to satisfy demands given on arcs with limited capacities, or to allocate facilities in a discrete multiple of facilities. All these operations cost money, not only for routing flows, but also for opening an arc or installing facilities. The objective is, then, to determine the optimal quantities of flows to be routed and, the facilities to be used.

The CNDP is a particular case of the well known Multicommodity Network Design Problem (MNDP), in which we distinguish an important number of special cases and extensions [12]. The most studied are: the unsplittable variant where the flow of each commodity is required to follow one route between the origin and the destination, which increases the difficulty of the problem [33]. The expansion variant, where some edges already have an existing capacity. The fixed charge MNDP [12,30] in which the link capacities are known. Solving MNDP consists to determine the set of edges that should be opened in the final topology. The capacitated MNDP, where the number of modules to install on the edges are modeled by integers [12]. The Network Loading Problem (NLP), where the number of module types is limited, each one with given unit cost and capacity.

Various heuristics and exact approaches have been developed for designing capacitated networks. However, the heuristic approaches are more likely to be trapped in local optima, while the exact approaches are applied only to small or medium size problems. Due to the weaknesses of the two approaches, and the increasing popularity of metaheuristic approaches, we have witnessed many metaheuristics being applied to network optimization problems [8,11,28,31,32,34].

We will focus on designing low cost network, given point-to-point traffic demands, potential links and a set of module capacity with their corresponded costs. The objective is to define the minimal network topology, the different modules to allocate on links in order to route all demands at minimum cost. We propose a hybrid heuristic for CNDP with modular link capacity. We combine between a greedy constructive approach that search an initial feasible solution through an iterative routing of demands, then we improve the quality of the solution by an Iterative Local Search (ILS) which based on two moves that we define. The rest of this paper is structured as follow: the related works are given in Section 2. The notations of the addressed problem are formally stated and a proposed mixed integer programming formulation to model the problem are given in Section 3. Section 4 explains in details the proposed algorithm. Experimental results are discussed in Section 5. Conclusion is presented in Section 6. A nomenclature of all variables used in this paper is given.

2. Related work

Capacitated Network Design Problem is one of the major research area in network optimization. It is related to two issues: Network Design Problem (NDP) and Network Loading Problem (NLP). In the NDP, the goal is to identify the network topology by selecting routers and links that interconnect them. Thus, the objective function aims to minimize the total constructive cost under some topological constraints. In this class of problems, the flow is not modeled, consequently it is considered as uncapacitated. In the NLP, it is assumed that the topology is already established. Thus, solving NLP consists to search for the set of resources to allocate for the network components. These problems are complementary. Generally, NDP and NLP are solved separately though they are combined together in some cases.

One can say that most of network optimization problems can be seen as a kind of (1) NDP, (2) NLP or (3) a combination of both where the objective and the constraints may differ from one problem to another: connectivity [1,5], limited budget [29], hop limit [21,33], delay [19,20], reliability [19,21], survivability [20,27].

The NLP in capacitated or uncapacitated case and with both single or multiple facilities are a special case of the well known MNDP. Previous works on this problem can be classified as:

Uncapacitated network design problems where on each link of the network, it is only possible either to open the link with infinite capacity and a given fixed cost, or the cost is zero and no capacity is available [25].

Single facility capacitated network loading problem where, the capacity can be done by installing on each link an integer unit of a given basic facility [6].

Two facilities capacitated network loading problems where the capacity can be achieved by means of two types of modules, each capacity has a specific cost [18,24].

Recently, multi type facilities capacitated network loading problems where various types of capacities can be installed on each link, each facility has a specific cost [2,29].

The NLP has been widely study with approximate methods, the modular capacity version is initialized by [22]. The authors in [23,24] introduced the residual capacity inequalities. They considered the single-commodity problem of undirected link models and a modular capacity structure with up to three different modules. Then, introduced the cutset inequalities and strengthened the multicommodity flow formulation with integer cable installation variables with cutset, three-partition and arc residual capacity inequalities. [7] studied polyhedra based on bidirected problems with two divisible base capacities. They generalized the cutset inequalities that force the capacity on both edge sets of a bipartition of the cut edges to be integral. In [3] Atamturk generalized these flow cutset inequalities by expressing the coefficients with a subadditive function for the single commodity problem. Chopra et al. in [9] introduced general flow cutset inequalities for directed models with a single module and showed their validity. Atamturk in [4] given a detailed analysis for directed cutset polyhedra. The authors studied the flow cutset inequalities introduced in [9] and provided a complete description for single-commodity and single-module case. Further, Atamturk generalized directed flow cutset inequalities to an arbitrary number of modules. All these works consider that the underling network is established, they identifies only the facilities to allocate and how to accommodate demand flows. Their effectiveness depends on the size of the problem instance.

With the appearance of metaheuristics, both the NLP and the NDP have attracted some attention. The authors benefit from their efficiency to deal with more complex variants with real size instances. In [15], the author compared several neighborhood structures to solve the uncapacitated facility location problem. In [20], the authors proposed an evolutionary approach for capacitated network design considering cost, performances and survivability. The objective minimizes network cost and packet delay. Kleeman et al. [19] used an evolutionary algorithm to solve multicommodity capacitated network design problem with an objective function optimizing costs, delay, robustness, invulnerability and reliability. A tabu search heuristic algorithm with real costs on facilities is developed in [8]. A firefly algorithm is proposed by Rahmaniani and Ghaderi [29], they combined facility location and network design problem with multi type of capacitated link and limited budget on facilities. Contreras and Fernández [10] presented a unified framework of general network design problems which combine location decision and network design decision.

3. Problem formulation

Let be $G = (V, E)$ an undirected graph, where $V = {1, 2, \dots, n}$ is the set of nodes and $E = {(i, j), i, j \in V, i \neq j}$ is the set of potential links. K is the set of traffic demands on the network, representing node-to-node traffic demands. Each commodity $k \in K$ has a single source node $s (k)$ , a single destination node $d (k)$ and a traffic amount of $t (k)$ . The objective is to define the network topology with the necessary module facilities to route the demands flow with total minimal cost. Before describing the mathematical model of the CNDP, we define some preliminary notations:

P (k)

the set of elementary paths used to accommodate $t (k)$ flow from $s (k)$ to $d (k)$

the set of all paths, $T = ⋃_{k \in K} P (k)$

A_{i j}

the set of the paths that use $(i, j)$ or $(j, i)$

f_{p}

the flow on the path p

the existence link matrix with cardinality $(n, n)$

the fixed cost matrix with cardinality $(n, n)$

y_{i j}

the fixed cost of established link $(i, j)$

the routing cost matrix with cardinality $(n, n)$

r_{i j}

the unit routing cost on link $(i, j)$

the set of module types available to allocate on the network

the cardinality of L set

m_{l}

the capacity of module type l such that $l \in L$

c_{i j}^{l}

the installation cost of module type l on link $(i, j)$

the module capacity matrix

the working capacity matrix with cardinality $(n, n)$

the unused capacity matrix with cardinality $(n, n)$

The decision variables that we search to fix for (CNDP) are: the binary variable $x_{i j}$ , which express if the link $(i, j)$ is activated in the network topology or not, the integer decision variable $w_{i j}$ that correspond to the sum of flow routed on the link $(i, j)$ , and the integer decision variable $n_{i j}^{l}$ that represent the number of the modules type l allocated on the link $(i, j)$ .

The constraint expressed in (2) ensures that all traffic demands are satisfied in Normal Operating State (NOS). Constraint (3) ensures that the final topology contains only links witch are at least used by one path. Constraint expressed in (4) shows that the working flow on each link is able to route all traffic demands accommodated on it. Constraint expressed in (5) ensures that the number of modules allocated are enough to route the whole traffic demands. The trivial constraints are expressed in (6), (4), (8) and (9).

In the objective function, the value $f_{i j} \times x_{i j}$ represents the fixed installation link costs, $w_{i j} \times r_{i j}$ is the routing cost and $\sum_{l = 1}^{L} c_{i j}^{l} \times n_{i j}^{l}$ is the allocated capacity cost. The objective function of CNDP is to minimize the total design (fixed installation link costs) and operational costs (routing and allocation costs): $\begin{matrix} (1) & Min \sum_{(i, j) \in E} (y_{i j} \times x_{i j} + w_{i j} \times r_{i j} + \sum_{l = 1}^{w} c_{i j}^{l} \times n_{i j}^{l}) \end{matrix}$ subject to $\begin{array}{rcl} (2) & \sum_{p \in P (k)} f_{p} = t (k), \forall k \in K, \\ (3) & t (k) \times x_{i j} ⩾ f_{p}, \forall (i, j) \in p, p \in P (k), k \in K, \\ (4) & \sum_{p \in A_{i j}} f_{p} ⩽ w_{i j}, \forall (i, j) \in E, \\ (5) & \sum_{l = 1}^{w} m_{l} \times n_{i j}^{l} ⩾ w_{i j}, \forall (i, j) \in E, \\ (6) & x_{i j} \in {0, 1}, \forall (i, j) \in E, \\ (7) & w_{i j} ⩾ 0, \forall (i, j) \in E, \\ (8) & n_{i j}^{l} \in Z^{+}, \forall l \in L, \forall (i, j) \in E, \\ (9) & f_{p} ⩾ 0, \forall p \in T . \end{array}$

4. Proposed heuristic

We develop a hybrid heuristic approach combining greedy and ILS heuristics. The greedy algorithm generates the initial feasible solution by routing demands on shortest paths, It defines the network topology and allocates the module capacities. The ILS algorithm improve the initial solution through two types of moves that reduce the number of modules capacity.

4.1. Initial feasible solution

The constructive approach attempt to find a solution by starting with the problem graph, without any edges, and to construct the solution by adding edges one at a time. For the CNDP, it is easy to reach a feasible solution. We propose a Working Capacity Search ( $WCS$ ) algorithm, which is a constructive greedy heuristic. It provides an effective solution and accelerate the convergence of our heuristic. It starts with an empty graph, searches the best paths to route iteratively commodities. It defines the network topology and allocates the necessary capacities.

For each commodity k, $WCS$ applies Dijkstra’s algorithm to identify the shortest path to accommodate $t (k)$ flow from $s (k)$ to $d (k)$ . The found path is set as Working path of demand k, and noted as $W^{k}$ , which is the set of minimal edges that joint extremities of commodity k. It may be defined as a sequential links $(i, j) \in E$ , the path cost is the sum of costs on the individual links.

Let $l \in L$ be the smallest module that verifies the conditions in inequalities (10) and (11). To route a $t (k)$ flow, enough capacities must exist on each link $(i, j) \in W^{k}$ . Otherwise, we allocate another module type l. $\begin{array}{rcl} (10) & t (k) ⩽ m_{l}, \\ (11) & ∄ l^{'} \in L; t (k) ⩽ m_{l} ⩽ m_{l^{'}} . \end{array}$ We note that, In Fig. 2, $ChooseModule$ procedure identifies the most appropriate module l according to inequalities (10) and (11). $Djikstra$ procedure searches the minimal working path $W^{k}$ for routing $t (k)$ flow. $WCS$ algorithm routes demands and updates network links as follow:

For each link $(i, j) \in W P (k)$ we distinguish two cases:

The link is not activated in the previous topology ( $x_{i j} = 0$ ), so we activate it, we install module l and we update working and unused capacities.

If the link is activated ( $x_{i j} = 1$ ), one of the following cases is verified

the link have enough unused capacities to route $t (k)$ flow. So, we do not require allocating module l, just we update working and unused capacities.

the unused capacities are not sufficient. We allocate module l and we do the necessary updates.

We iterate all previous steps for each demand

k \in K

Let be $c_{i j}^{x}$ the installation cost of module type $x \in L$ on $(i, j)$ with $m_{x}$ unit. Installing module type $y \in L$ with $2 \times m_{x}$ unit, does not induce automatically a cost $c_{i j}^{y}$ equal to $2 \times c_{i j}^{x}$ . Thus, the module cost is not a strict incremental increasing function.

To reduce cost of previous modules installed, we verify in each routing iteration the possibility of substituting α installed modules type x with a new module type z, ${x, z} \in L$ , that verifies inequalities (12), (13).

The cost of module type z does not exceed the cost of α modules type x $\begin{matrix} (12) & \sum_{j = 1}^{α} c_{i j}^{x} ⩾ c_{i j}^{z} . \end{matrix}$

The total capacity of α modules type x does not exceed capacity module type z $\begin{matrix} (13) & \sum_{j = 1}^{α} m_{x} ⩽ m_{z} . \end{matrix}$

This verification process is expressed by the $ImproveModule$ procedure in the WCS algorithm (Fig. 1). At each iteration $k \in K$ , $WCS$ algorithm searches the appropriate working path to route a demand k, updates the network topology with the necessary links, and allocates facilities to route the flow. Thus, we obtain a network that is able to route all demands simultaneously. So, the $WCS$ heuristic generates feasible solution of CNDP.

Fig. 1.

Algorithm that construct initial solution S. K is the demand set. W is the working capacity matrix where $w_{i j}$ is the working capacity on link $(i, j)$ . U is the unused capacity matrix where $u_{i j}$ is the unused capacity on $(i, j)$ . X is the link existence matrix where $x_{i j}$ indicates if the link is activated in the topology or not. N is the installed module matrix where $n_{i j}^{l}$ indicates the number of module type l allocated on $(i, j)$ . l is the module that will probably allocated with capacity $m_{l}$ . P is the set of all elementary paths used to route the demands. $ChooseModule$ procedure returns the appropriate module to allocate with its capacity. $W^{k}$ is the shortest path to route demand k identified by $Dijkstra (k)$ procedure.

The inequalities (12), (13) aim to substitute α installed modules of type x with a new module type z, that provides the same capacity or the higher one with at most the same cost. This optimization process is based on capacity reduction cost, and results on the following consequences:

Consequence 1.

We benefit a decrease in total constructive cost.

Consequence 2.

Extra capacities that can be used to accommodate next demands to be routed on this link. Then, the obtained network at this step has too much unused capacities. Moreover, in the routing process, each demand takes a single path to join their extremities. So, there is no diversification of demands.

4.2. Improvement process

As a second stage of our framework, consists in the Maximum Unused Capacity algorithm ( $MUC$ ). The improvement is achieved by exploring changes on working paths (routes) based on allocated facilities. At each iteration, we select a neighbor to the current solution which allows to reduce the cost inside feasible search space. The procedure terminates when a stopping criteria is reached. The local search starts with a given initial solution as the current solution and checks its neighborhood for a better solution. If such a solution exists, then, it designates the best solution found in the neighborhood as the current solution and repeats the process. In case where the neighborhood of the current solution does not contains any better solution, local search returns the current solution and terminates. MUC algorithm is a local search that use two categories of moves, the DeleteModule move and the Demand move. These moves work together to reduce the allocated modules number. The algorithm is iterated ${Iter}_{max}$ . In each $Iter$ , It apply the ILS procedure, which consists in iterative routine that selects the most promising link $(u, v)$ , then it searches a second route between their extremities that satisfy the constraints of the current $Iter$ . If no route exist, the link is put in the list of visited arcs and a new promising link is checked, else, we delete a module facility on this link (DeleteModule move) and we re-route demand(s) (Demand move) to maintain the feasibility of the solution. The ILS is iterated until reach its local stopping criteria (Stop). Then, $MUC$ execute new iteration $(Iter + 1)$ . All these steps will be explained in details in the next sections.

4.2.1. Promising link

We have mentioned that one of WCS drawbacks is the extra unused capacities. Obviously, the improvement process is guided by links which disposed a great amount of unused capacities. These links appear as the most promising to contribute in the neighborhood search. They are determined according to the procedure defined in Fig. 4.

Let $(u, v)$ be the promising link. To delete module type l on this link, we must ensure that the flow initially carried within this module can be rerouted on a second route R. Therefore, the links on R must have a sufficient residual capacities able to route this flow without allocating additional modules.

Let be $Flow . TR (u, v)$ the flow to re-route defined by equality (14). Each link on R must dispose an unused capacity at least equal to the flow to re-route (inequalities (15)). $\begin{array}{rcl} (14) & Flow . TR (u, v) = m_{l} - u_{u v}, \\ (15) & u_{i j} ⩾ Flow . TR (u, v), \forall (i, j) \in R . \end{array}$

Fig. 2.

PromisingLink procedure that identifies the link $(u, v)$ with the current maximum unused capacity which is not checked in previous iterations. S is the current solution. E is the set of links. $u_{i j}$ is the unused capacity on link $(i, j)$ . $n_{i j}^{l}$ is the number of module type l on the link $(i, j)$ . $VL . Arc$ is the set of previously visited links.

4.2.2. Re-route flow

After identifying the promising link, we search the route R that joint their extremities to re-route $Flow . TR$ . There is a large number of routes that joint the extremities of this promising link, which of them we choose? Our proposition have two constraints in the search of R; The efficient residual capacity constraint (inequality (15)), which means that the links on R route have an amount of unused capacity able to route the $Flow . TR (u, v)$ . The path length constraint that limits the length of the route R searched depends on the $Iter$ th step of the algorithm. During the $Iter$ th step, we allow only routes with maximum length equal to $(Iter + 1)$ .

The Re-Route procedure defined in Fig. 4 allows to find the best path between extremities of promising link, where $R \neq {(u, v)}$ . It identifies also the minimum amount ( $Min$ ) of unused flow available on the R links. Then, it returns R, if the both previous constraints are verified.

We favorite shortest paths to decrease the additional capacities used to route flows initially accommodated on optimal paths. We deduce that the length of R routes influences the amount of working capacities and facilities allocated. In the MUC steps the length constraint is relaxed from one iteration to another, until we reach the stopping criteria.

Figure 3 gives an example of an execution of the Re-Route procedure on a small network composed of 6 nodes and 8 links. Figure 3(a) and (c) correspond to the input networks, Fig. 3(b) and (d) are the resulting networks for the two cases $Iter = 1$ and $Iter = 2$ respectively. All capacities allocated on the network are a multiple of the capacity modules ${l, l^{'}}$ , where $m_{l} = 5$ unit and $m_{l^{'} = 15}$ .

$Iter = 1$ . In this iteration, we search route R with length $L (R) = Iter + 1 = 2$ to re-route flow between extremities of promising link $(E, B)$ . As the unused capacity on $(E, B)$ is equal to 2, we deduce that the flow to reroute is $Flow . TR (E, B) = 3$ . Only, one route $R 1 = {(E, D), (D, B)}$ satisfies the length constraint. Unfortunately, the unused capacity on $R 1$ ’s links do not satisfy the residual capacity constraint since $Min (u_{E D}, u_{D B}) = Min (1, 2) = 1 < Flow . TR (E, B) = 3$ . So, we can not accept this route and we add link $(E, B)$ to the visited arc list.

$Iter = 2$ . We search routes with $L (R) ⩽ 3$ . For the link $(E, B)$ two routes $(R 1, R 2)$ satisfy the length constraint. $R 1 = {(A, B), (A, F), (E, F)}$ and $R 2 = {(B, C), (C, D), (D, E)}$ . Only $R 1$ has a sufficient residual capacity. So, we route the flow on this route and we update the unused and working capacities as shown in Fig. 3(d).

Fig. 3.

Example on the Re-Route procedure. Three values are mentioned for each link representing respectively $w_{i j}$ , $u_{i j}$ and a Boolean value (T: true or F:false, T if $(i, j)$ is in the visited arc list $VL . Arc$ ). The set of modules contains two types of modules with respectively 5 and 15 unit of capacities. The smallest module is l with capacity $m_{l} = 5$ unit. The promising link is $(E, B)$ . (a) Input network $Iter = 1$ . (b) Result network $Iter = 1$ . (c) Input network $Iter = 2$ . (d) Result network $Iter = 2$ .

Fig. 4.

Procedure that searches a route R between the extremities of promising link $(u, v)$ . $u_{i j}$ is the unused capacities on link $(i, j)$ . $Iter$ is the current $MUC$ iteration and $Iter + 1$ is the maximum route’s length allowed. $Flow . TR (u, v)$ is the flow to reroute on R.

4.2.3. The Maximum Unused Capacity algorithm

MUC algorithm is an ILS, essentially based on the promising links and the re-route of flows to decrease the cost. This section show how our algorithm use the last two procedures to search neighborhoods and improve the WCS solution.

Fig. 5.

S is the initial solution returned by $WCS$ algorithm. ${Iter}_{max}$ is the maximum number of iterations where $Iter$ is the current iteration. $VL . Arc$ and $VL . Demand$ are the link and demand lists of the visited solutions. $(u, v)$ is the promising link. $Flow . TR$ is the flow to re-route on the route R searched by $ReRoute$ procedure. $S^{'}$ is the perturbed solution by DeleteModule procedure. $S^{″}$ is a feasible solution established by DemandMove procedure. $Fitness (S)$ returns the cost of solution S.

In the basic version of $ILS$ , there are four components to consider [13]: Initial Solution, Local Search, Perturbation and Acceptance Criterion. In our case, the local search consists on the selection of the promising link $(u, v)$ , then searching a route to re-route the $Flow . TR (u, v)$ with the current Iter constraints. If this route exists, we perturb solution S by the $DeleteModule$ move that deletes one module facility from link $(u, v)$ . We equilibrate solution $S^{'}$ by the $Demand$ move which searches the demand(s) that corresponds to $Flow . TR (u, v)$ and updates their working paths in the new solution $S^{″}$ . For the acceptance criterion, we accept a solution $S^{″}$ if it is better than the current best one. $ILS$ includes memory about the previous reached solution. In our case, we memorize links and demands explored previously. We maintain two types of lists: $VL . Arc$ and $VL . Demand$ which represents respectively list of links previously used to perturb solution S and list of demands which their working paths are moved in previous $MUC$ iterations.

In Fig. 5, solution S reached by WCS algorithm that corresponds to a network configuration that includes $(X, W, U, N)$ matrices and P set. The stopping criterion is the element ${Iter}_{max}$ which refers to the number of $MUC$ iterations. Each iteration ( $Iter$ ) defines the limits of the neighborhood and, execute iteratively a local search until a local stopping criterion is reached ( $Stop$ ), we refer to this routine as the $ILS$ . It is applied on S to obtain locally optimal solution $S^{'}$ . If $S^{'}$ is better than the current solution S, then replace S by $S^{'}$ , reinitialize $VL . Arc$ list and start again with $Iter = Iter + 1$ for the new solution. Otherwise the current solution S is not modified. After we delete the module capacity from the promising link $(u, v)$ . The DemandMove procedure identifies witch demand(s) correspond(es) to the $Flow . TR (u, v)$ and makes changes on its (their) working path(s). The demand(s) is (are) selected from $k_{(u, v)}$ which is the set of demands that use link $(u, v)$ on their working paths (equality (16)), and must has (have) at least an amount equals to $Flow . TR (u, v)$ (inequality (17)). $\begin{array}{rcl} (16) & k_{(u, v)} = {demands k; k \in K, (u, v) \in W^{k}}, \\ (17) & t (k) ⩾ Flow . TR (s, e) . \end{array}$ The working path(s) $W^{k}$ of demand(s) k associated to $Flow . TR (u, v)$ is (are) updated by the new paths ( $W^{' k}$ ) (equality (18)). $\begin{matrix} (18) & W^{' k} = {(i, j); (i, j) \in {W^{k} ∖ (u, v) \cup R}} . \end{matrix}$

The $MUC$ algorithm defines the search space in the $Iter$ th iteration and the $ILS$ searches for the local optima. The perturbation applied which is the DeleteModule move is applied on links that have a second route between their extremities. Once the $MUC$ stopping criterion is reached, we relax the route length constraint and we re-execute the algorithm. We report the result obtained at this iteration by ${MUC}^{+}$ . ${MUC}^{+}$ searches routes without any length constraint. So, the $Flow . TR (u, v)$ is rerouted on paths that may not satisfy the residual capacity constraint. Therefore, the DemandMove allocates additional modules to equilibrate the solution. The $ILS$ explores all links and accepts a new solution if it is better than to the current one.

4.2.4. Iteration number and stopping criteria

Generally neighborhood search algorithm stops after certain number of iterations. This one depends on the problem nature and the moving strategy. Our $MUC$ is iterated ${Iter}_{max}$ times, where ${Iter}_{max}$ is the maximum length of working WCS paths. It is fixed within the network instance. During the $Iter$ th step, the $ILS$ stops the execution if the maximum unused flow $Max (u_{i j}, (i, j) \in E ∖ {(u, v)})$ on the network is less than the $Flow . TR (u, v)$ . Automatically, we deduce that no route R exists with an efficient residual capacity. $\begin{matrix} (19) & u_{i j} ⩽ Flow . TR (u, v) . \end{matrix}$ The route R may exist if and only if inequality (19) is verified. Consequently, $ILS$ does not need an unimproved iteration series to stop execution, only a simple test confirms the local stopping criteria of the current iteration.

5. Results

In our experiments, we use five real networks including Polska, Atlanta, France, Pioro40 and Germany50 topologies. All can be downloaded from http://sndlib.zib.net [26]. We follow the model filter specified in Table 1.

Table 1
The model filter

Demand model	Undirected demand (U)
Link model	Undirected links (U)
Link capacity model	Modular link capacities (M)
Fixed-charge model	No fixed-charge cost (N)
Routing model	Continuous (C)
Admissible path model	All paths (A)
Hop limit model	No hop-limits (N)
Survivability model	No survivability (N)

Each instance is characterized by the number of nodes

| V |

, the number of potential links

| E |

and the number of traffic demands

| K |

. Table 2 summarizes the instances details specification. We can classified them on two categories; instances with Single Facility allocation (SF) and instances with Two Facilities allocation (TF). The set of capacity modules (L) differs from one network instance to another. The allocation cost (Mcost) is variant on links, whereas it is fixed in the France instance. Atlanta instance assumes a Pre-installed capacities (P) on theirs potential links with a unit Routing cost (Rcost). For more details on the setting parameters and the model filter see [26].

Table 2

The instance setting parameters

Problem instance	\|V\|	\|E\|	\|K\|	Nbr	L	Mcost	P	Rcost
Polska	12	18	66	TF	$155$ , $622$	Variant	No	No
Atlanta	15	22	210	TF	$1000$ , $4000$	Variant	Yes	Yes
France	25	45	300	SF	$2500$	Fixed	No	No
Pioro40	40	89	780	TF	$155$ , $622$	Variant	No	No
Germany50	50	88	662	SF	$40$	Variant	No	No

Table 3

The $WCS$ , $MUC$ and ${MUC}^{+}$ solutions

Instance	$BS$	$WCS$	$Gap %$	$MUC$	$Gap %$	${MUC}^{+}$	$Gap %$
Polska	23,619	23,900	1.18	23,692	0.30	23,533	−0.36
Atlanta	86,492,550	93,690,816	8.32	92,904,547	7.41	92,226,817	6.62
France	20,200	23,400	15.84	21,400	5.94	–	–
Pioro40	414,440	428,039	3.28	426,636	2.74	–	–
Germany50	645,520	764,560	18.44	687,730	6.53	–	–

Table 4

The evolution of MUC algorithm during the ${Iter}_{\max}$ iterations

		Polska	Atlanta	France	Pioro40	Germany50
$WCS$		23,900	93,690,816	23,400	428,039	764,560
$MUC$	$Iter = 1$	23,692	92,904,547	21,800	428,039	722,350
	$Iter = 2$	23,692	92,904,547	21,800	426,636	722,350
	$Iter = 3$	23,692	92,904,547	21,600	426,636	719,060
	$Iter = 4$	23,692	92,904,547	21,400	426,636	719,060
	$Iter = 5$	–	–	21,400	426,636	687,730
	$Iter = 6$	–	–	–	–	687,730
	$Iter = 7$	–	–	–	–	687,730
	$Iter = 8$	–	–	–	–	687,730
$MUC +$		23,533	92,226,817	–	–	–

In Table 3, WCS and the MUC are respectively the solutions obtained by WCS and MUC algorithms. We examine the optimality gap (see equality (20)), which is defined by the difference between WCS cost ( $MUC$ / ${MUC}^{+}$ ) and the best solution cost ( $BS$ ) published in [26]. The ${MUC}^{+}$ results are reported only for instances where an improvement is made. $\begin{matrix} (20) & GAP = {Cost (WCS) - Cost (BS)} / Cost (BS) * 100 . \end{matrix}$

As we can see, WCS generates solutions close to the optimality for Polska and Pioro40 networks. SF instances (France and Germany50) results are worse compared to the TF ones. This behavior is due to the fact that ImproveModule procedure can not be applied. Therefore, no improvement is done during the constructive stage which is clearly appreciable for TF instances.

The MUC algorithm proves its effectiveness. It starts with an average gaps of 17.14% and 4.26% for SF and TF instances respectively. Then, it reduces the gaps to 6.23% and 3.22%. Contrarily to $MUC$ , ${MUC}^{+}$ can only reduce costs in Polska and Atlanta.

Fig. 6.

The evolution of MUC algorithm during the ${Iter}_{max}$ iterations. (a) Polska; (b) Atlanta; (c) France; (d) Pioro40; (e) Germany50. (Colors are visible in the online version of the article; https://dx-doi-org.web.bisu.edu.cn/10.3233/JHS-150528.)

Table 4 and Fig. 6 show respectively the values and the corresponded curves of MUC algorithm convergence. We collect the objective function values during the MUC iterations.

For all instances, we remark that the first iteration ( $Iter = 1$ ) provides an important reduction in cost. After that, there is a stagnation in Polska and Atlanta curves. For the instances represented by Fig. 6(c) and (e), the reduction continues until the last iteration. We can say that the behavior of MUC algorithm depends on the problem instance (SF, TF).

The number of iterations ${Iter}_{max}$ has not a unique value for all instances, it is relative to the problem instance. We affect to ${Iter}_{max}$ the value of maximum path length reached in WCS solution (see Table 5). It means that we can not accept paths whose lengths exceed Max Normal Operation State (NOS) path length. Note that, MUC algorithm can stop it’s execution even before we reach ${Iter}_{max}$ iteration if no improvement is made during three consecutive iterations.

The SNDlib library uses many parameters to evaluate solutions in details. It classifies them in two sets; the general statistics and the routing statistics that are respectively presented in Table 5 and Table 6. The general statistics summarize the details information about the generated topology (nodes, links and capacities) with theirs corresponded costs. The routing statistics provide length and number of working paths used to accommodate demands.

In Table 5, the total number of installed links, Min, Max and Average node degrees parameters confirm that both WCS and MUC solutions generate graphs with the same BS topologies except for the Pioro40 instance which constructs a graph with 89 links whereas BS has only 86 links.

We remark that France and Germany50 topology instances are densest in WCS, this density has been reduced by MUC up to BS values. Although our improvement process is only based on capacities, it can deal with the topology improvement. The MUC algorithm based on capacities reduction, this later is clearly appreciable when comparing WCS and MUC total installed link capacities.

Figure 7 shows the allocated capacities and their usage in the five network instances. For each network, we compare the total installed link capacities, the total working capacities and the total unused capacities. It is notable that total installed link capacities in WCS and MUC solutions are more than BS ones, which justify the cost gap. Although Polska and Pioro40 networks allocate low capacities, the gap cost persists. This later is related to allocation module costs that differ from link to another.

The working and the unused capacities show the detailed usage of the allocated capacities. In WCS, we route demands on single shortest paths, which results in working capacity flow lower than the BS ones. Even with demand diversification introduced in MUC, it remains reduced. The results obtained confirm the expected WCS’s drawbacks and the gap is due to the unused capacities. Even after improvement reached by MUC, the unused capacities are still important.

Table 5

The general statistics

	Polska				Atlanta				France			Pioro40			Germany50

	$BS$	$WCS$	$MUC$	${MUC}^{+}$	$BS$	$WCS$	$MUC$	${MUC}^{+}$	$BS$	$WCS$	$MUC$	$BS$	$WCS$	$MUC$	$BS$	$WCS$	$MUC$
Total cost	23, 619	23, 900	23, 692	23, 533	86, 492, 550	93, 690, 816	92, 904, 547	92, 226, 817	20, 200	23, 400	21, 400	414, 440	428, 039	426, 636	645, 520	764, 560	687, 730
Total link capacity cost	23,619	23,900	23,692	23,533	67,350,000	74,670,000	73,840,000	72,835,000	20,200	23,400	21,400	414,440	428,039	426,636	645,520	764,560	687,730
Preinstalled capacity cost	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
Additional module capacity cost	23,619	23,900	23,692	23,533	67,350,000	74,670,000	73,840,000	72,835,000	20,200	234,000	21,400	414,440	428,039	426,636	645,520	764,560	687,730
Routing cost	0	0	0	0	19,142,550	19,020,815	19,142,550	19,391,817	0	0	0	0	0	0	0	0	0
Min node degree	2	2	2	2	2	2	2	2	2	2	2	3	4	4	1	1	1
Max node degree	5	5	5	5	4	4	4	4	10	10	10	5	6	6	5	5	5
Average node degree	3	3	3	3	2.93	2.93	2.93	2.93	3.28	3.6	3.28	4.30	4.45	4.45	3.36	3.44	3.36
Total number of installed links	18	18	18	18	1822	22	22	22	41	45	41	86	89	89	84	86	84
Total installed link capacities	22,080	20,824	20,669	20,669	294,000	308,000	307,000	309,000	252,500	292,500	270,000	416,732	351,052	349,657	7200	8480	7640
Min link capacity usage in NOS	95.34	85.58	85.58	82.75	64	31	40	45	30.08	3.08	20.16	94.69	54	85.80	52.50	10	20
Max link capacity usage in NOS	100	99.59	100	100	99	100	100	99.92	100	100	100	100	100	100	100	100	100

Table 6

The routing statistics

	Polska				Atlanta				France			Pioro40			Germany50

	$BS$	$WCS$	$MUC$	${MUC}^{+}$	$BS$	$WCS$	$MUC$	${MUC}^{+}$	$BS$	$WCS$	$MUC$	$BS$	$WCS$	$MUC$	$BS$	$WCS$	$MUC$
Total working flow	21, 810	19, 835	19, 878	19, 964	282, 338.50	280, 543	281, 188	286, 015	243, 248	235, 596	237, 952	416, 383	344, 906	345, 060	7140	6730	6954
Total unused flow	892	989	791	705	11,662	27,457	25,812	22,985	5562	56,904	32,048	349	6146	4733	60	1750	966
Min NOS path length	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
Max NOS path length	5	5	5	5	6	5	6	6	6	5	5	8	7	7	10	9	9
Average NOS path length	2.38	2.15	2.17	2.27	2.63	2.50	2.58	2.60	3.78	3.40	3.44	3.65	3.31	3.32	3.78	3.40	3.44
Total number of NOS paths	77	66	67	70	219	210	215	217	322	300	305	855	780	782	724	662	683
Min number of NOS paths per demand	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
Max number of NOS paths per demand	3	1	2	2	2	1	2	2	3	1	3	1	2	3	1	3	3
Average number of NOS paths per demand	1.17	1	1.01	1.06	1.04	1	1.02	1.03	1.07	1	1.01	1.10	1	1.01	1.09	1	1.03

Fig. 7.

Comparison between $BS$ , $WCS$ , $MUC$ and ${MUC}^{+}$ solutions in total installed link capacities, working and unused capacities. (a) Polska; (b) Atlanta; (c) France; (d) Pioro40; (e) Germany50. (Colors are visible in the online version of the article; https://dx-doi-org.web.bisu.edu.cn/10.3233/JHS-150528.)

Fig. 8.

The average path length in NOS. (Colors are visible in the online version of the article; https://dx-doi-org.web.bisu.edu.cn/10.3233/JHS-150528.)

The usage of capacities is expressed with min, max and average link capacity usage in normal operation state. We remark that the initial solution does not allow a best capacity usage, which is ameliorated later by MUC solution.

The average path length is defined as the fraction between the sum of all the path lengths and the total number of NOS paths. The exact values of all the network instances are reported in the routing statistics (see Table 6). In Fig. 8, we can see that our average NOS path length in WCS is the lowest. This behavior is due to the fact that we route demands on single shortest paths. MUC allows diversification demand and accepts longer paths in the move strategy which induces a little increase.

Despite BS is less expensive, the details of the general statistics and the routing statistics prove that our solution is better in total working capacity. BS aims only the reduction of network cost, which is done by favoring the routing of demands in longer paths to avoid additional allocated facilities.

6. Conclusion

In this paper we have proposed a hybrid heuristic for Capacitated Network Design Problem, which is NP hard. It combines greedy heuristic (WCS) and iterative local search heuristic (MUC) to construct an initial solution and improve it. The WCS algorithm generates an initial feasible solution by iterating routing demand process. At each iteration, it searches the shortest path to route commodity, allocates the necessary facilities and updates the network topology. The constructive phase is followed by MUC algorithm which reduces the total constructive cost by decreasing the allocated capacities. In fact, it defines DeleteModule move and Demand move that explore unused capacities on links.

The proposed algorithms are simple and easy to implement, the effectiveness of their combination is proved by simulation. Our proposition produces near optimal solutions compared to the best ones presented in the SNDlib library.

Nomenclature

the set of nodes

cardinality of the nodes set

the set of potential links

the cardinality of the set of links E

undirected graph corresponds to sets V and E that model the network topology

the set of demands

cardinality of demands set

a demand

s (k)

the source of demand k

d (k)

the destination of demand k

t (k)

the traffic amount of demand k

the set of all elementary path used to accommodate demands

P (k)

the set of elementary path used to accommodate the flow of demand k between the extremities $s (k)$ and $d (k)$

f_{p}^{k}

the flow belonging to the traffic demand k and passing on the path p

the existence matrix with cardinality $(n, n)$

x_{i j}

a binary decision variable indicating whether the link $(i, j)$ is activated in the network topology

the working capacity matrix with cardinality $(n, n)$

w_{i j}

the working capacity on the link $(i, j)$

the unused capacity matrix with cardinality $(n, n)$

u_{i j}

the unused capacity on the link $(i, j)$

the fixed cost matrix with cardinality $(n, n)$

y_{i j}

the fixed cost of establishing link $(i, j)$

the routing cost matrix with cardinality $(n, n)$

r_{i j}

the unit routing cost on link $(i, j)$

the set of modules type to allocate on the network

a module capacity type l, $l \in L$

m_{l}

the capacity of module type l

the module matrix

c_{i j}^{l}

the installation cost of a module type l on link $(i, j)$

n_{i j}^{l}

the number of modules type l installed on link $(i, j)$

(u, v)

the link witch have the maximum unused capacity on the network (the promising link)

the route that joint the extremities of link $(u, v)$

L (R)

the length of route R (number of links on R)

Flow . TR (u, v)

the flow to reroute between extremities of link $(u, v)$

W^{k}

the working path of demand k

W^{' k}

the second route of demand k

VL . Arc

the list of previous promising links

VL . Demand

the demands list that theirs working paths are moved

{Iter}_{max}

the maximum iteration numbers of MUC algorithm

Iter

current iteration of MUC algorithm

References

[1]

Abd-El-Barr, Topological network design: A survey, Journal of Network and Computer Applications 32(3) (2009), 501–509.

[2]

Y.K.

Agarwal, Design of capacitated multicommodity networks with multiple facilities, Operations Research 50(2) (2002), 333–344.

[3]

Atamtürk, On capacitated network design cut-set polyhedra, Mathematical Programming 92(3) (2002), 425–437.

[4]

Atamtürk and

Rajan, On splittable and unsplittable flow capacitated network design arc-set polyhedra, Mathematical Programming 92(2) (2002), 315–333.

[5]

Balakrishnan,

Banciu,

Glowacka and

Mirchandani, Hierarchical approach for survivable network design, European Journal of Operational Research 225(2) (2013), 223–235.

[6]

Barahona, Network design using cut inequalities, SIAM Journal on Optimization 6(3) (1996), 823–837.

[7]

Bienstock and

Günlük, Capacitated network design-polyhedral structure and computation, Informs Journal on Computing 8(3) (1996), 243–259.

[8]

Brun,

Garcia et al., A tabu search heuristic for capacitated network design, in: IEEE Symposium on Computers and Communications, ISCC, 2009, pp. 461–467.

[9]

Chopra,

Gilboa and

Sastry, Source sink flows with capacity installation in batches, Discrete Applied Mathematics 85(3) (1998), 165–192.

10.

[10]

Contreras and

Fernández, General network design: A unified view of combined location and network design problems, European Journal of Operational Research 219(3) (2012), 680–697.

11.

[11]

J.-F.

Cordeau,

Laporte and

Pasin, An iterated local search heuristic for the logistics network design problem with single assignment, International Journal of Production Economics 113(2) (2008), 626–640.

12.

[12]

Frangioni and

Gendron, 0–1 reformulations of the multicommodity capacitated network design problem, Discrete Applied Mathematics 157(6) (2009), 1229–1241.

13.

[13]

Gendreau and

Potvin, Handbook of Metaheuristics, Vol. 2, Springer, Berlin, 2010.

14.

[14]

Gendron,

T.G.

Crainic and

Frangioni, Multicommodity Capacitated Network Design, Springer, Berlin, 1999.

15.

[15]

Ghosh, Neighborhood search heuristics for the uncapacitated facility location problem, European Journal of Operational Research 150(1) (2003), 150–162.

16.

[16]

Gupta and

Könemann, Approximation algorithms for network design: A survey, Surveys in Operations Research and Management Science 16(1) (2011), 3–20.

17.

[17]

Kerivin and

A.R.

Mahjoub, Design of survivable networks: A survey, Networks 46(1) (2005), 1–21.

18.

[18]

Kerivin,

Nace and

T.-T.-L.

Pham, Design of capacitated survivable networks with a single facility, IEEE/ACM Transactions on Networking 13(2) (2005), 248–261.

19.

[19]

Kleeman,

Lamont,

Hopkinson and

Graham, Solving multicommodity capacitated network design problems using a multiobjective evolutionary algorithm, in: IEEE Symposium on Computational Intelligence in Security and Defense Applications, 2007, pp. 33–41.

20.

[20]

Konak and

Smith, Capacitated network design considering survivability: An evolutionary approach, Engineering Optimization 36(2) (2004), 189–205.

21.

[21]

Liu,

Yang and

Huang, Reliable network design problem under node failure with benders decomposition, Applied Mathematics 5 (2014), 241.

22.

[22]

Magnanti and

Mirchandani, Shortest paths, single origin-destination network design, and associated polyhedra, Journal of Networks 23(2) (1993), 103–121.

23.

[23]

Magnanti,

Mirchandani and

Vachani, The convex hull of two core capacitated network design problems, Mathematical Programming 60(1–3) (1993), 233–250.

24.

[24]

Magnanti,

Mirchandani and

Vachani, Modeling and solving the two-facility capacitated network loading problem, Journal of Operations Research 43(1) (1995), 142–157.

25.

[25]

Magnanti,

Mireault and

Wong, Tailoring Benders Decomposition for Uncapacitated Network Design, Springer, Berlin, 1986.

26.

[26]

Orlowski,

Wessäly,

Pióro and

Tomaszewski, Sndlib 1.0 survivable network design library, Networks 55(3) (2010), 276–286.

27.

[27]

Palmieri and

Fiore, A low cost and effective link protection approach for enhanced survivability in optical transport networks, in: Frontiers of High Performance Computing and Networking – ISPA 2006 Workshops, Springer, Berlin, 2006, pp. 368–376.

28.

[28]

Premprayoon and

Wardkein, Topological communication network design using ant colony optimization, in: ICACT 2005. The 7th IEEE International Conference on Advanced Communication Technology, Vol. 2, 2005, pp. 1147–1151.

29.

[29]

Rahmaniani and

Ghaderi, A combined facility location and network design problem with multi-type of capacitated links, Applied Mathematical Modelling 37(9) (2013), 6400–6414.

30.

[30]

Rodríguez-Martín and

J.J.

Salazar-González, A local branching heuristic for the capacitated fixed-charge network design problem, Computers & Operations Research 37(3) (2010), 575–581.

31.

[31]

Shen,

Xu and

Zheng, A tabu search algorithm for the routing and capacity assignment problem in computer networks, Computers & Operations Research 32(11) (2005), 2785–2800.

32.

[32]

Taheri and

Zomaya, A simulated annealing approach for mobile location management, Computer Communications 30(4) (2007), 714–730.

33.

[33]

Thiongane,

J.-F.

Cordeau and

Gendron, Formulations for the nonbifurcated hop-constrained multicommodity capacitated fixed-charge network design problem, Computers & Operations Research 53 (2015), 1–8.

34.

[34]

Yaghini,

Momeni and

Sarmadi, A simplex-based simulated annealing algorithm for node-arc capacitated multicommodity network design, Applied Soft Computing 12(9) (2012), 2997–3003.

Hybrid heuristic for Capacitated Network Design Problem

Abstract

Keywords

1. Introduction

2. Related work

3. Problem formulation

4. Proposed heuristic

4.1. Initial feasible solution

4.2.1. Promising link

5. Results

Table 1 The model filter

Nomenclature

References

Table 1
The model filter