Finding edge-disjoint paths with artificial ant colonies

Finding edge-disjoint paths with artificial ant colonies Maria J. Blesa Christian Blum Report LSI–05–15–R 18th April 2005 1 Finding edge-disjoint paths with artificial ant colonies ∗† Maria J. Blesa ‡Christian Blum ALBCOM research group § Dept. Llenguatges i Sistemes Inform`atics Universitat Polit`ecnica de Catalunya Jordi Girona 1–3 (Ω) Campus Nord, E-08034 Barcelona (Spain) {mjblesa,cblum}@lsi.upc.edu Abstract One of the basic operations in communication networks consists in establishing routes for connection requests between physically separated network nodes. In many situations, either due to technical constraints or to quality-of-service and survivability requirements, it is required that no two routes interfere with each other. These requirements apply in particular to routing and admission control in large-scale, high-speed and optical networks. The same requirements also arise in a multitude of other applications such as real-time communications, vlsi design, scheduling, bin packing, and load balancing. This problem can be modeled as a combinatorial optimization problem as follows. Given a graph Grepresenting a network topology, and a collection T={(s1, t1)...(sk, tk)}of pairs of vertices in Grepresenting connection request, the maximum edge-disjoint paths problem is an NP-hard problem that consists in determining the maximum number of pairs in Tthat can be routed in Gby mutually edge-disjoint si−tipaths. We propose an ant colony optimization (aco) algorithm to solve this problem. aco algorithms are approximate algorithms that are inspired by the foraging behavior of real ants. The decentralized nature of these algorithms makes them suitable for the application to problems arising in large-scale environments. First, we propose a basic version of our algorithm in order to outline its main features. In a subsequent step we propose several extensions of the basic algorithm and we conduct an extensive parameter tuning in order to show the usefulness of those extensions. In comparison to a multi-start greedy approach, our algorithm generates in general solutions of higher quality in a shorter amount of time. In particular the run-time behaviour of our algorithm is one of its important advantages. Keywords: Ant Colony Optimization; Maximum edge-disjoint paths problem ∗M. Blesa acknowledges support by the FET Programme of the EU under contract number IST-2001-33116 (flags) and from the Spanish cicyt project tic-2001-4917-e. C. Blum acknowledges support by the “Juan de la Cierva” postdoctoral program of the Spanish Ministry of Science and Technology, of which he is a research fellow. Both authors acknowledge support by the Spanish cicyt project tic-2002-04498-c05-03 (tracer). †A preliminary version of this work was presented at the 1st European Workshop on Evolutionary Computation in Communications, Networks, and Connected Systems (Evocomnet’04), in Applications of Evolutionary Computing (evoworkshops’04), Coimbra, Portugal. April 2004. LNCS 3005:160–169, Springer-Verlag. ‡Corresponding author. Tel.: (+34)934137868, Fax: (+34)934137833. §Research group on ALgorithms, Bioinformatics, COmplexity and Formal Methods, see albcom.lsi.upc.edu. 2 1 Introduction One of the basic operations in communication networks consists in establishing routes for connection requests between physically separated network endpoints that wish to establish a connection for information exchange. Many connection requests occur simultaneously in a network, and it is desirable to establish routes for as many requests as possible. In many situations, either due to technical constraints or just to improve the communication, it is required that no two routes interfere with each other, which implies not to share network resources such as links or switches. This scenario can be modeled as follows. Let G= (V, E) be an edge-weighted undirected graph representing a network in which the nodes represent the hosts and switches, and the edges represent the links. The weight w(e)∈R+of an edge e∈Ecorresponds to the distance between its endpoints. Let T={(sj, tj)|j= 1,...,|T|;sj6=tj∈V}be a list of commodities, i.e., pairs of nodes in G, representing endpoints demanding to be connected by a path in G.Tis said to be realizable in Gif there exist mutually edge-disjoint (respectively vertex-disjoint) paths from sj to tjin G, for every j= 1,...,|T|. Deciding whether a given set of pairs is realizable in a given graph is one of Karp’s original NP-complete problems [25] (other references on the computational complexity of the problem are [34, 43]). The problem remains NP-complete for various graph types such as, for example, two-dimensional meshes. The combinatorial optimization version of this problem consists in satisfying as many of the requests as possible, which is equivalent to finding a realizable subset of Tof maximum cardinality. An EDP solution Sto the combinatorial optimization problem is a set of disjoint paths, in which each path satisfies the connection request for a different commodity. The objective function value f(S) of a solution Sis defined as f(S) = |S|.(1) In general, the “disjointness” of paths may refer to nodes or to edges. We decided to consider the latter case, because it seems of higher importance in practical applications. We henceforth refer to our problem as the maximum edge-disjoint paths (EDP) problem. In the extreme case in which the list of commodities is composed by repetitions of the same pair (s, t), the problem is known as edge-disjoint Menger problem. The EDP problem is a simpler version of the more general unsplittable flow problem, in which demands, profits, and capacities are considered to be one. The EDP problem is interesting for different research fields such as combinatorial optimization, algorithmic graph theory and operations research. It has a multitude of applications in areas such as real-time communications, vlsi-design, scheduling, bin packing, load balancing, and it has recently been brought into focus in works discussing applications to routing and admission control in modern networks, namely large-scale, high-speed and optical networks [5, 37, 1, 3]. Concerning real-time communications, the EDP problem is very much related to survivability and information dissemination. Concerning survivability, having several disjoint paths available may avoid the negative effects of possible failures occurring in the base network. Furthermore, to communicate via multiple disjoint paths can increase the effective bandwidth between pairs of nodes, reduce congestion in the network and increase the velocity and the probability of receiving the information [24, 39]. This becomes especially important nowadays due to the type of information that circulates over networks (e.g., media files), which requires fast, qualified and reliable connections. To the best of our knowledge, there is a lack of efficient algorithms for tackling the EDP problem. Except for greedy approaches (which we will mention in Section 3), our preliminary ant colony optimization (ACO) approach presented in [8] is the only existing method1.aco [16, 18] is a recent metaheuristic for solving hard combinatorial optimization problems. Except for the application to combinatorial optimization problems (see [19] for an extensive overview) the method has also gained recognition for the applications to adaptive routing in static and dynamic communication 1In [36], a multi-colony ACO approach for the EDP problem was presented. However, the aim of this paper was not to solve the EDP problem but rather to explore the feasibility of multi-colony systems. Therefore, only toy examples of graphs of up to 20 nodes with 2 or 3 commodities were considered. 3 networks [14, 15]. aco algorithms are composed by independently operating computational units that generate a global perspective without the necessity of direct interaction. They provide several advantageous features—such as, for example, the usage of only local information—that are useful when applications in large-scale environments are concerned in which the computation of global information is often too costly. Organization. The paper is organized as follows. In Section 2 we deal with the complexity of the EDP problem, including an overview on approximability results. Existing results show that the EDP problem is not only NP-complete, but it is also hard to obtain good approximation schemes for it. In Section 3, we outline a (multi-start) greedy approach for the purpose of benchmarking our aco algorithm. Section 4 is devoted to the detailed introduction of our aco approach. The algorithm is developed incrementally; starting from a basic aco approach, we introduce features that, as we show in the experimental part, help greatly on solving the EDP problem. The experimental evaluation of our approach is presented in Section 5. Besides the creation of a benchmark set of instances, we conducted an extensive tuning of the considerable number of algorithm parameters. The details on the parameter tuning process are reported on in Appendix A. In Section 6, we conclude and point out possible lines for future research. 2 Understanding the complexity of the problem The decisional version of the EDP problem was early known to be NP-complete [25] in arbitrary graphs. The problem remains NP-complete for specific types of graphs such as planar graphs [34, 43], series-parallel graphs (a.k.a. partial 2-trees) [35], and grid graphs [30, 32]. A more detailed classification of the complexity of the optimization version of the problem can be obtained with the help of approximation algorithms. Approximation algorithms tackle optimization problems in polynomial time (w.r.t. the length of the input) and output a solution that is guaranteed to be at some bounded quality difference to the optimal solution. “Close” has some well-defined sense called the approximation ratio (or performance guarantee). Definition 1 (ρ-approximation algorithm for a problem P)Given an approximation ratio ρ > 1and any problem instance xof P, a ρ-approximation algorithm for an optimization problem Poutputs, in polynomial time, a solution to xof cost at most ρtimes the optimum. NP-hard problems vary greatly in their approximability; some can be approximated to arbitrary factors while some can essentially not be approximated at all. The problems which are approximable within a ρ > 1 belong to the complexity class APX. The class PTAS is a particular subclass of APX 2which includes problems that admit a polynomial-time approximation scheme. Definition 2 (Polynomial-time approximation scheme –PTAS– for a problem P)Given any fixed 1>  > 0, a polynomial-time approximation scheme for an optimization problem Pis a (1 + )-approximation algorithm for P. These algorithms are desirable because one can get arbitrarily close to an optimal solution. A problem is said to be APX-hard (w.r.t. the PTAS-reducibility) if there exists some constant  > 0 such that it is NP-hard to obtain a (1 + )-approximation algorithm, i.e., it is NP-hard to obtain a PTAS. This means that those problems are even hard to approximate, since no PTAS can be obtained efficiently unless P=NP [2]. For several types of graphs, the EDP problem belongs to the class of APX-hard problems [22, 31, 20, 23]. This fact explains the notorious hardness of the EDP problem in terms of approximation, despite the attention and effort that researchers have put on it. Interestingly, for the specific case of complete graphs, we are not aware of any inapproximability results. In particular, it is not even known whether the problem in complete graphs is APX-hard. 2Unless P=NP, the approximability class PTAS is strictly contained in the class APX. 4 Algorithm 1 Simple greedy algorithm (sga) for the EDP problem input: a problem instance (G, T ), consisting of a graph Gand a commodity list T S← ∅,ˆ E←E for j= 1,...,|T|do if sjand tjcan be connected by a path in G= (V, ˆ E)then Pj←shortest path from sjto tjin G= (V, ˆ E) S←S∪Pj,ˆ E←ˆ E\ {e|e∈Pj} end if end for output: the solution S The approximability of the EDP problem has been tackled by greedy algorithms, LP relaxations, and rounding. In directed arbitrary graphs, the approximability was seemingly settled for some time by the Ω(|E|1/2−)-hardness results in [23] and the O(p|E|) approximation results in [26, 40, 7, 29, 27]. Those approximation bounds were recently applied in [12] to arbitrary dense graphs and improved down to sub-linear. The recent work in [42] trims slightly these bounds via LP rounding and a deeper analysis of a greedy algorithm. However, better approximation ratios have been achieved for some specific types of graphs, such as (sub-)classes of planar graphs (e.g., grid graphs, trees, rings, densely-embedded, plane switch, etc.), complete graphs, random graphs, and expander graphs. Also better performance guarantees are obtained for commodity-restricted versions of the problem, for example for the edge-disjoint Menger problem [45, 38, 11]. We address the reader to [27, 13] for recent summaries of the successive achievements concerning the approximation ratios. 3 The simple greedy algorithm and its multi-start version A greedy heuristic is a constructive algorithm that builds a solution step-by-step starting from an empty solution. At each construction step, an element from a finite set of solution components is added to the current partial solution. The element to be added is chosen at each step according to some greedy function, which lends the name to the algorithm. Advantages of greedy heuristics are that they are usually easy to implement and that they are fast in execution. The disadvantage is that the quality of the solutions provided by greedy algorithms can be quite far from optimal. Due to the fact that the EDP problem usually has to be solved in rather large graphs, research has focused on the development of greedy algorithms. Many of the approximation ratios cited in Section 2 have been calculated when analyzing greedy algorithms. Examples are the simple greedy algorithm (sga) [26] (see Section 3), its constrained variant the bounded-length greedy algorithm [26, 28], and the greedy path algorithm [27, 12]. Due to its lower time complexity when compared to the other greedy approaches we decided to implement the simple greedy algorithm (henceforth denoted by sga) and a multi-start version, which we both outline in the following. The sga algorithm (see Algorithm 1) is a natural way of approximating the EDP problem that works as follows. It starts with an empty solution S. Then, it proceeds through the commodities in the order that is given as input. For routing each commodity Tj∈T, it considers the graph G without the edges that are already in the paths of the solution Sunder construction. The shortest path between sjand tj(with respect to the edge-weights) is assigned as path for the commodity Tj= (sj, tj). Note that the algorithm is deterministic and that the quality of the solutions it provides depends heavily on the order in which the commodities are treated. In addition to its simplicity, the sga algorithm can be naturally considered an on-line algorithm and then, the lower bounds of [4] would imply that it does not achieve a good performance ratio on graphs such as trees and two-dimensional meshes. However, it works well for some other types of graphs. A simple way of obtaining a multi-start version of the sga is to permute—for each restart—the 5 Algorithm 2 Multi-start simple greedy algorithm (msga) for the EDP problem input: a problem instance (G, T, Nperm), where Nperm is the number of restarts Sbest ← ∅ T1←T for i= 1 to Nperm do Si←Simple Greedy Algorithm SGA(G,Ti){See Algorithm 1} if f(Si)> f(Sbest)then Sbest ←Si end if if i < Nperm then π←random permutation of |T| Ti+1 ←(π(1), π(2),...,π(|T| − 1), π(|T|)) end if end for output: Sbest order of the commodities. This approach is pseudo-coded in Algorithm 2, in which Nperm denotes the number of restarts, Sidenotes the solution under construction in the embedded sga, and Sbest denotes the best solution found so far. In the following, we refer to this algorithm as multi-start greedy algorithm (msga). 4 An ant colony optimization approach Ant colony optimization (aco) [19] is inspired by the foraging behavior of real ants. This behavior enables an ant colony to find shortest paths between food sources and their nest. While walking from food sources to the nest and vice versa, ants deposit a chemical substance called pheromone on the ground. When they decide about a direction to go, they choose probabilistically paths marked by strong pheromone concentrations. This behavior is the basis for a cooperative interaction which leads to the emergence of shortest paths. In aco algorithms, artificial ants incrementally construct a solution by adding appropriately defined solution components to the current partial solution. Each of the construction steps is a probabilistic decision based on local information, which is represented by the pheromone information. The exclusive use of local information is certainly a desirable property for algorithms that are aimed for the application to problems for which the computation of global information is costly. This property makes aco algorithms a natural choice for the application to the EDP problem. 4.1 The basic ACO algorithm In the following we outline our aco approach, which is based on a decomposition of the EDP problem. Each problem instance P= (G, T ) of the EDP problem can be naturally decomposed into |T|subproblems Pj= (G, Tj), with j∈ {1,...,|T|}, by regarding the task of finding a path for a commodity Tj∈Tas a problem itself. With respect to this problem decomposition, we use a number of |T|ants each of which is assigned to exactly one of the subproblems. Therefore, the construction of a solution consists of each ant building a path Pjbetween the two endpoints of her commodity Tj. Obviously, the subproblems are not independent as the set of |T|paths constructed by the ants should be mutually edge-disjoint. 4.1.1 Ant solutions A solution Sconstructed by the |T|ants is a set of not necessarily edge-disjoint paths that contains a path for each commodity. We henceforth refer to them as ant solutions. From each ant solution 6 a valid EDP solution can be produced by iteratively removing the path which has most edges in common with other paths, until all remaining paths are mutually edge-disjoint. The objective function f(·) of the problem (see Equation 1) is characterized by having many plateaus when it is applied to ant solutions. This is because many ant solutions will have the same number of disjoint paths. Thus, a consequence of decomposing the EDP problem is the need to define a more fine-grained objective function fa(·) for ant solutions. Therefore, referring to f(S) as a first criterion, we introduce a second criterion C(S), which is defined as follows: C(S) =  e∈E  max    0,   Pj∈S δj(S, e)  −1     , where δj(S, e) =  1 : e∈Pj∈S 0 : otherwise. This second criterion quantifies the degree of non-disjointness of an ant solution. If all the paths in a solution Sare edge-disjoint, C(S) is zero. In general, C(S) increases when increasing the usage of common edges in S. Therefore, based on the idea that “the fewer edges are shared in a solution, the closer the solution is to disjointness”, a function fa(·) that differentiates between ant solutions can be defined as follows. For two ant solutions Sand S0, it holds that fa(S)> fa(S0)⇔(f(S)> f(S0)) |{z } 1st criterion or ((f(S) = f(S0) and (C(S)< C(S0)) | {z } 2nd criterion .(2) 4.1.2 Pheromone models The problem decomposition as described above implies that we use a pheromone model τjfor each subproblem Pj. Each pheromone model τjconsists of a pheromone value τj efor each edge e∈E. The set of |T|pheromone models is henceforth denoted by τ={τ1, . . . , τ|T|}. Our aco algorithm is implemented in the hyper-cube framework (HCF) [9], which is a way of implementing aco algorithms such that the pheromone values are bounded between 0 and 1. Furthermore, we borrow an idea from so-called MAX -MIN Ant Systems (MMASs) [41] and introduce pheromone value limits τmin = 0.001 and τmax = 0.999 in order to prevent that the algorithm converges to a solution. 4.1.3 Algorithm framework and components Algorithm 3 is a high level description of our aco algorithm. Two different ant solutions are kept in the algorithm: Sibest is the iteration-best solution, i.e., the best ant solution generated in the current iteration, and Sgbest is the best-so-far solution, i.e., the best ant solution found since the start of the algorithm. In the following, we give a high-level description of the algorithm. The main procedures used by the algorithm are explained in detail in the following of the section. First, all the variables are initialized. In particular, the pheromone values are set to their initial value τmin by the procedure InitializePheromoneValues(τ). Second, Nsols ant solutions are constructed per iteration. To construct a solution, each ant applies the function ConstructFullPath(sπ(j), tπ(j)), where πis a permutation of T. At each iteration, the first of those Nsols ant solutions is constructed by sending the ants in the order in which the commodities are given in T. For each further ant solution construction in the same iteration, the order πin which the ants construct a path for their commodity is randomly generated by the function GenerateRandomPermutation(|T|). Third, the value of the variables Sibest and Sgbest is updated. Finally, the pheromone values are updated depending on the edges included in Sgbest. The algorithm is iterated until some opportunely defined termination conditions are satisfied, and it returns the EDP solution generated from the ant solution Sgbest. The main procedures of our algorithm are outlined more in detail in the following. ·InitializePheromoneValues(τ)initializes all the pheromone values τj e∈τj∈τto the value τmin. (see Section 4.1.2.) 7 Algorithm 3 Basic ACO algorithm for the EDP problem input: a problem instance (G, T ) Sgbest ← ∅ InitializePheromoneValues(τ) while termination conditions not met do π←(1,2,...,|T| − 1,|T|) for i= 1 to Nsols do Si← ∅ for j= 1 to |T|do Pπ(j)←ConstructFullPath(sπ(j), tπ(j)) Si←Si∪ {Pπ(j)} end for if i < Nsols then π←GenerateRandomPermutation(|T|) end for Choose Sibest ∈ {Si|i= 1,...,Nsols}s.t. fa(Sibest)≥fa(S),∀S∈ {Si|i= 1, . . . , Nsols} if f(Sibest)> f(Sgbest)then Sgbest ←Sibest UpdatePheromoneValues(τ,Spbest) end while output: the EDP solution generated from the best solution Sgbest ·ConstructFullPath(sπ(j), tπ(j)).For constructing a path between the endpoints of the commodity (sπ(j), tπ(j)), an ant first chooses randomly to start either from the source sπ(j)or the target tπ(j). Then, the ant iteratively moves from node to node using available edges that are not already in the path Pπ(j)under construction, and that are not labelled forbidden by a backtracking move. Backtracking is done in case the ant finds itself in a node in which all the incident edges have been used, or if all the incident edges are labelled forbidden. Note, that with this strategy the ant will find a path between source and target, if there exists one. Otherwise, the ant returns an empty path and the iterative process is also stopped. In the following the current node is denoted by vc, the goal node is denoted by vg, and the set of allowed edges in G(i.e., those incident to vcwhich were not used yet in the path and not labelled as forbidden) is denoted by I? vc. At each construction step, the choice of where to move to has a certain probability to be done deterministically. This is a feature we adopt from a particularly effective aco variant called Ant Colony System (acs) which was proposed by Dorigo and Gambardella in [17]. We draw a random number drate between 0 and 1. If drate ≤0.75 (where 0.75 was chosen by parameter tuning as outlined in Section 4 and Appendix A), the next edge to join path Pπ(j)under construction is chosen deterministically: e∗={vc, u} ← argmax {τj e·p(De)β·p(Ue)γ|e∈ I? vc},(3) where p(De) is a value that determines the influence of the distance from vcvia uto the goal vertex vg, and p(Ue) is a value that determines the influence of the overall usage of edge e, which is the information whether eis already used in the path of another ant for the same solution. The parameters β > 0 and γ > 0 weight the influence of these two terms. The length of the shortest path between two vertices uand vin Gis henceforth denoted by σ(u, v). The terms p(De) and p(Ue) are defined as follows: p(De={vc,u})←(σ(u,vg)+w(e))−1  e0={vc,u0}∈I? vc (σ(u0,vg)+w(e0))−1 p(Ue)←U(e)−1  e0∈I? vc U(e0)−1,in which U(e) = 2 : ealready used in Si 1 : otherwise 8 If drate >0.75, the next edge e∗is chosen according to the following transition probabilities: p(e| I? vc) = τj e·p(De)β·p(Ue)γ  e0∈I? vc τj e0·p(De0)β·p(Ue0)γ,∀e∈ I? vc(4) If the probability of doing a deterministic construction step is too high, there is the danger that the algorithm gets stuck in low quality regions of the search space. On the other side, doing deterministic construction steps bears the potential of leading the algorithm quite quickly to good areas of the search space. In our experiments (see Section 4 and Appendix A) we found 0.75 to be a good trade-off. Concerning the composition of the transition probabilities, the use of the pheromone information τj eensures the flexibility of the algorithm, whereas the use of p(De)βensures a bias towards short paths, and p(Ue)γ ensures a bias towards disjointness of the |T|paths constituting a solution. After every ant has constructed its path and the solution Sis completed, we apply another feature of acs, namely the evaporation of some amount of pheromone from the edges that were used by the ants. Given a solution S, the evaporation is done as follows: τj e←(1 −erate)·τj e:e∈Pπ(j)∈S, j = 1,...,|T| τj e: otherwise .(5) The reason for this pheromone evaporation is the desire to diversify the search in each iteration. After parameter tuning we chose a setting of erate = 0.10. ·UpdatePheromoneValues(τ,Supdate).As it is usual in acs algorithms, in our basic aco algorithm only the ant solution Sgbest is used for updating the pheromone values for all j∈ {1, . . . , |T|} as follows: τj e←max τj e+ρ·1−τj e, τmax∀e∈Pj,(6) where ρ∈(0,1] is a constant value which is called learning rate in algorithms that are implemented in the hyper-cube framework. For all our experiments we have set ρto 0.1. 4.2 Motivation for additional algorithmic features The direct application of a basic aco scheme to a problem achieves sometimes quite good results. However, the algorithms’ performance can often be improved by applying some additional features to the search process, especially when a rather unusual problem such as the EDP is tackled. In this section, we describe how the basic aco approach introduced in Section 4.1 may be enriched with different strategies that modify the way the algorithm explores the solution space. In the following we propose four additional features, explaining why these features might lead to an improvement, before we outline the implementation of these features more in detail in the subsequent section. Sequential versus parallel solution construction. For constructing a solution, method ConstructFullPath(sπ(j), tπ(j))as applied in the basic aco algorithm (see Algorithm 3) considers one commodity after the other, and constructs for each commodity a path between its endpoints before the next commodity is considered. In the following we refer to this way of constructing solutions as the sequential way. As an alternative we propose to construct paths for all the commodities in parallel. Hereby, at each constructing step each ant changes its partial path by either adding exactly one edge, or by doing a backtracking move. Note that there is a considerable difference in the influence of the edge-usage information between sequential and parallel construction. This changes the dynamics of the search process and might lead to different results. 9 5.2 Tuning of the algorithm parameters Due to the relatively high number of algorithm parameters it was not feasible to tune all the parameter values together. In order to ease the task of parameter tuning we first divided the set of parameters into two subsets. The first subset consists of parameters which are in our opinion not critical, in the sense that appropriate values can easily be found. These parameters are τmin and τmax for limiting the pheromone values, Nsols (the number of solution constructions per iteration), the learning rate ρ, and the maximum number of non-improving iterations for the first and second algorithm phase, namely c1max, and c2max respectively. For these parameters we chose values that we found to be well-working after preliminary tests. The remaining parameters, which define our extended aco approach in terms of its added features, are the following ones: drate is the proportion of deterministic construction steps; β and γbalance the influence of the distance to the goal vertex and the overall usage of edges, respectively; erate determines how much pheromone is evaporated from the edges belonging to the current best solution; constructiontype specifies the strategy followed for constructing the paths of a solution; candidatesListsize specifies the size of the candidate lists; distinguishphase1indicates if to use the two search phases based on the improvement of the two criteria of the objective function; destructionrate and destructiontype indicate how much of the current best solution must be destroyed and how this destruction should be performed. For the purpose of tuning the remaining parameters we used all the instances derived from graph AS-BA.R-Wax.v100e190.4First, we applied the extended aco approach with all possible combinations of parameter value settings to all the 60 instances. Then, we progressively fixed parameter values in the following way. At each step i, we chose the parameter pi(from the ones that still needed a value) for which we could see a clearer result than for the rest. Note that this process was rather based on personal judgment than on mathematical rigor. Hereby, the i-th parameter piis decided according to the experimental results obtained for those experiments in which the previously treated parameters p1,...,pi−1have their fixed value, and the rest of parameters pi+1, pi+2,..., etc. can have any allowed value. In those cases in which the analysis of only one parameter did not provide enough information to decide for a value, we studied the combined influence of two or more parameters with respect to the rest. The complete tuning process is documented in Appendix A. Here we only show some illustrating examples. The first parameter for which we chose a value was parameter distinguishphase1, which has settings {yes,no}. Some results of our experiments are shown in Figure 3 in the form of box-plots. When analyzing the box-plots it becomes clear that both in terms of solution quality and computation time better results are obtained when setting distinguishphase1to yes. We use this setting for deciding a value for all the remaining parameters. Thus only the results of experiments for which distinguishphase1is set to yes are considered in the following. Second, we decided for a value for parameter drate. This parameter has five possible settings: {0,0.25,0.5,0.75,1}. Figure 4 depicts results of the experiments obtained for the tuning of this parameter. The results show that determinism is needed, although not too much. There is no difference between the quality of the solutions obtained for values 0.25, 0.5, and 0.75. However, the setting of drate to 0.75 needs less computational time in order to reach the same solution quality (see Sub-figure 4(b)). After fixing parameter values for βand γto 1, it still remained to fix a parameter value for the candidate list size, the destruction rate, the destruction type and the solution construction mechanism. An initial separate study of them was not conclusive, since these parameters seemed to be strongly related. Furthermore, the experiments for the instances derived from graph ASBA.R-Wax.v100e190 did not provide much information. We used graph4 for continuing the tuning, since this graph proved to be difficult for a preliminary version of our aco approach [8], which lacked most of the additional features of the extended aco. Figure 5 shows results (under different destruction rates) concerning the joined analysis of the candidate list size, the destruction type and the solution construction strategies, for the 20 instances composed by graph4 and 173 commodities. First, the results displayed in this figure show that parallel solution construction seems to have 4Note that the computation time limits are the same as described in Table 4. 16 YES NO 8 10 12 14 16 18 Considering 1st phase (AS−BA.R−Wax.v100e190, 25 pairs) 1st PHASE size (nb. disjoint paths) (a) Costs of the best solutions found YES NO 0 2 4 6 8 10 Considering 1st phase (AS−BA.R−Wax.v100e190, 25 pairs) 1st PHASE time to find the best (seconds) (b) Times needed to find the best solutions Figure 3: Results concerning the setting of parameter distinguishphase1∈ {yes,no}. The boxplots show results of all experiments concerning the instances with 25 commodities derived from graph AS-BA.R-Wax.v100e190 in terms of the best found solutions, respectively the times at which these solutions were found, of the extended aco algorithm. In each graphic, the left box-plot (labelled as yes) shows the case in which only the disjoint paths of the ant solution contribute to the update of the pheromone (1st phase); the right box-plots (labelled as no) show the case in which the whole ant solution is used for updating the pheromone. 0% 25% 50% 75% 100% 8 10 12 14 16 18 Considering the determinism rate (AS−BA.R−Wax.v100e190, 25 pairs, 1st phase YES) Determinism rate (%) size (nb. disjoint paths) (a) Costs of the best solutions found 0% 25% 50% 75% 100% 0 2 4 6 8 10 Considering the determinism rate (AS−BA.R−Wax.v100e190, 25 pairs, 1st phase YES) Determinism rate (%) time to find the best (seconds) (b) Times needed to find the best solutions Figure 4: Results concerning the setting of parameter drate when having fixed distinguishphase1to yes. The box-plots show results of all experiments concerning the instances with 25 commodities derived from graph AS-BA.R-Wax.v100e190 in terms of the best found solutions, respectively the times at which these solutions were found, of the extended aco algorithm. In each graphic, the five box-plots show the results when considering 0%, 25%, 50%, 75% and 100% determinism, respectively. advantages over the sequential construction, independently of the destruction rate. It can also be observed that, the higher the number of considered candidates is, the lower is the quality of the solutions obtained. Concerning the destruction type, to destroy the longest paths in the solution generally provides slightly better results than destroying some paths chosen at random. The final parameter setting is summarized in Table 3. 17 SEQ 2 candidates SEQ 50% candidates SEQ all candidates 75 80 85 90 Considering the candidates list strategy (graph4, 173 pairs, 1st phase YES, beta 1, gamma 1, drate 0.75, erate 0.10, destrate 0) Candidates considered size (nb. disjoint paths) PAR PAR PAR 75 80 85 90 (a) Destruction rate 0% SR 2 candidates SR 50% candidates SR all candidates 75 80 85 90 Considering the candidates list strategy (graph4, 173 pairs, 1st phase YES, beta 1, gamma 1, drate 0.75, erate 0.10, destrate 0.25) Candidates considered size (nb. disjoint paths) SL SL SL 75 80 85 90 PR PR PR 75 80 85 90 PL PL PL 75 80 85 90 (b) Destruction rate 25% SR 2 candidates SR 50% candidates SR all candidates 75 80 85 90 Considering the candidates list strategy (graph4, 173 pairs, 1st phase YES, beta 1, gamma 1, drate 0.75, erate 0.10, destrate 0.5) Candidates considered size (nb. disjoint paths) SL SL SL 75 80 85 90 PR PR PR 75 80 85 90 PL PL PL 75 80 85 90 (c) Destruction rate 50% Figure 5: Results concerning the joined analysis of the candidate list size, the destruction type and the sequential/parallel solution construction strategies, under different destruction rates. The box-plots show results of all experiments concerning the instances with 173 commodities derived from graph graph4. The x-axis shows different sizes for the candidate lists (i.e., 2 candidates, 50% of the candidates, and all the candidates), together with the different solution construction strategies and the destruction criteria. Hereby we use the abbreviations SR, SL, PR, and PL, where S stands for sequential, P for parallel, L for longest path destruction, and R for random path destruction. Table 3: Final parameter setting for the extended aco algorithm. Note that for the simple aco we chose the same values for parameters τmin,τmax,Nsols,ρ,c1max,c2max,drate,β,γ, and erate as for the extended aco. Parameter/property Tuning domain Chosen value τmin – 0.001 τmax – 0.999 Nsols – 10 ρ– 0.1 c1max,c2max – 20 for both drate {0,0.25,0.50,0.75,1}0.75 β,γ{0.1,1,10}for both 1 for both erate {0.01,0.05,0.10}0.10 constructiontype {sequential,parallel}parallel candidatesListsize {2,50%,all}2 distinguishphase1{yes,no}yes destructionrate {0,0.25,0.50}0.25 destructiontype {random,longest}longest 5.3 Experiments and results We applied the algorithms presented in this work (namely sga,msga, the simple aco, and the extended aco) to all 300 instances exactly once. First, we applied msga with 50 restarts (i.e., Nperm = 50) to each of the 300 instances. The computation time of msga was used as a maximum CPU time limit for both versions of the aco algorithm. We present the results as averages over the 20 instances of each combination of graph and commodity number in Table 4. The layout of this table is explained in its caption. Concerning the comparison between sga and msga, we observe a clear advantage of msga. This means that the order in which the commodities are treated is crucial in achieving a good 18 Table 4: Comparison of the results obtained by the sga, the msga, and both versions of the aco algorithm. The table layout is as follows. The first column gives the name of the graph and the second column the number of the commodities, which are obtained as the 10%, 25%, and 40% of the number of nodes of the graphs. For each algorithm there are three columns reporting on the average results obtained for the 20 instances of each combination of graph topology and number of commodities. The first of these three columns (headed by q) shows the average of the values of the best solutions found for the 20 instances. Such an average is in boldface when the result is the best in the comparison. In case of ties the computation time decides. The second column provides the standard deviation of the 20 values used to compute q, and the third column (headed by treports on the average time (in seconds) needed to find the best solution values for the 20 instances. Finally, the last column shows the computation time of msga, which was used as computation time limit for both versions of the aco approach. number of SGA MSGA Simple ACO Extended ACO Graph commodities q σ t q σ t q σ t q σ t max CPU time graph3 16 15.30 0.781 0.566 15.70 0.557 0.960 15.65 0.572 1.321 15.70 0.557 0.457 30.582 graph3 41 29.00 2.864 1.298 32.00 2.302 25.235 30.55 2.109 41.153 31.80 1.990 27.953 79.619 graph3 65 33.70 2.777 2.156 37.60 2.577 49.267 36.80 2.502 82.578 40.30 2.571 57.899 126.945 graph4 43 40.50 1.628 12.121 42.05 1.024 95.744 40.05 1.396 244.458 41.45 1.284 168.871 237.52 graph4 108 58.10 4.194 31.138 64.10 3.064 697.456 60.85 2.762 1231.099 68.15 2.725 730.436 1656.475 graph4 173 66.75 4.846 49.281 73.95 3.542 974.350 73.40 4.005 1940.110 85.10 3.534 1111.982 2603.872 bl-wr2-wht2.10-50 50 19.70 2.238 17.926 22.55 2.397 318.518 23.85 2.128 171.857 24.10 1.947 155.899 971.488 bl-wr2-wht2.10-50 125 34.15 4.464 46.387 38.10 4.369 1004.462 41.80 4.545 594.902 42.30 4.540 344.092 2425.090 bl-wr2-wht2.10-50 200 46.70 4.961 62.158 50.85 4.892 1151.197 54.50 4.955 1101.917 56.30 5.245 847.415 3124.550 AS-BA.R-Wax.v100e190 10 8.75 0.942 0.114 9.10 0.943 0.579 8.80 0.980 0.549 8.95 0.973 0.611 6.665 AS-BA.R-Wax.v100e190 25 12.30 1.900 0.280 14.25 1.374 4.809 14.05 1.117 4.921 14.85 1.195 3.718 16.740 AS-BA.R-Wax.v100e190 40 15.45 2.500 0.443 17.95 1.624 7.796 18.80 1.913 8.608 19.45 1.936 4.121 26.850 AS-BA.R-Wax.v100e217 10 7.00 1.225 0.103 8.05 0.921 0.427 7.70 1.005 0.480 7.88 0.927 0.164 6.892 AS-BA.R-Wax.v100e217 25 11.40 1.882 0.300 13.60 1.463 4.330 13.70 1.646 3.127 13.83 1.579 1.816 17.622 AS-BA.R-Wax.v100e217 40 14.60 1.685 0.497 17.00 1.949 9.833 17.35 1.711 6.433 17.80 1.646 2.212 28.318 19 performance. However, as there is no obvious way of determining a good commodity order beforehand, the only way of exploiting this knowledge is by randomly permuting the commodity list and running msga. The prize we have to pay for exploiting this knowledge is the increased computation time. Concerning the comparison of the two aco approaches, we can observe that the features that distinguish the extended aco from the simple aco approach are of great benefit. The extended aco approach consistently obtains better solution qualities in less computational time. When comparing the simple aco approach with the msga greedy algorithm, we can observe that the former, although being more sophisticated, does not achieve a better performance. For the graphs representing Internet topologies, both the msga and the simple aco approach perform very similar. For the other graphs, the msga is often faster. More in detail, we can observe that in 11 out of 15 cases the extended aco approach beats all the other algorithms. The extended aco approach is on average 4.69% better than msga, and in one case (e.g., for graph4, 173 commodities) it is even 15.07% better. Additionally, the extended aco approach needs in general lesser computation time than the other approaches. The advantage in computation time increases with increasing number of commodities. Exceptions are some of the results for small number of commodities, namely for 10% of the number of nodes of the graphs. For this combination msga has often slight advantages over the extended aco approach. Therefore, we recommend to use a greedy approach when easy problem instances are concerned. However, the average results for instances with a higher number of commodities show a clear advantage of the extended aco in contrast to msga, both in quality and time. An interesting observation concerns the results of the extended aco algorithm in comparison to the results of our preliminary aco approach from [8], for which we noticed considerable difficulties when applied to instances derived from graph4. In [8] we conjectured that these difficulties result from the fact that graph4 has some nodes with a very high degree. This is because, first, these nodes are important connectivity points and are often in the shortest paths between two vertices of the graph, and second, because the higher the degree of a vertex, the lesser the probability of choosing a particular outgoing edge in the construction mechanism. More precisely, when constructing a path and being in one of these vertices, in order to choose a good outgoing edge the algorithm has possibly to be lucky, especially in early stages of the search process when the pheromone values are similar. We can observe that our extended aco algorithm does not show this behaviour. The additional features added to the simple aco approach, in particular the usage of candidate lists, have helped on overcoming these difficulties concerning graph4. In general, the additional features of our extended aco approach proved to be useful for the problem resolution. An example for the usefulness of the solution destruction mechanism is shown in Figure 6. Finally, an additional analysis concerns the run-time behaviour of our algorithms. Figure 7 shows that both aco approaches find relatively good solutions already after a very short computation time. In general, already the first solutions produced by the aco are quite good, whereas the greedy approaches reach a comparable solution quality only much later in time. This property of our aco approach is a desirable feature in the context of communication networks since the (already good) quality of the solutions that are found after a short execution time might be often sufficient in practice. 6 Conclusions and further work In this paper we have proposed an ant colony optimization (aco) approach to tackle the maximum edge-disjoint paths problem. To the best of our knowledge this is—except for our own preliminary approach from [8]—the first application of ant colony optimization, and more in general of any any metaheuristic, to this problem. Our approach is based on a decomposition of the maximum edgedisjoint paths problem into subproblems. We have compared our algorithm to a multi-start greedy approach which is based on a greedy approach that was developed for approximation purposes. First, we introduced a basic aco approach in order to be able to focus on important algorithmic features such as the solution construction and the pheromone update. Then, we proposed several extensions and additional features: concerning the solution construction process, we proposed (1) 20 55 60 65 70 75 80 85 90 0 200 400 600 800 1000 1200 1400 solution size |S| (nb.disjoint paths) iterations Solutions Current best solution Best so far solution 500 550 600 650 700 750 800 850 0 200 400 600 800 1000 1200 1400 number edges shared iterations 2nd Criteria nb.edges shared (a) Example of the evolution of the quality of the current best solution Spbest and the best-so-far solution Sgbest during the search (left), and the number of shared edges (2nd criterion) of the solution Spbest (right). The behavior shown here corresponds to the application to one of the 20 instances composed by graph4 and a list of 173 commodities. All the curves are smoothed with gnuplots’ sbezier function. 55 60 65 70 75 80 85 0 100 200 300 400 500 600 700 solution size |S| (nb.disjoint paths) iterations Solutions Current best solution Best so far solution 60 65 70 75 80 85 90 95 700 800 900 1000 1100 1200 1300 1400 solution size |S| (nb.disjoint paths) iterations Solutions Current best solution Best so far solution (b) Zoom on the 700 first (left) and the 700 last (right) iterations of Figure 6(a). On the left, the best solution found is quickly improved. At about iteration 250, the algorithm destroys part of the Spbest solution, which produces an instantaneous worsening in the quality (left); another solution destruction takes places around iteration 550, which helps in achieving an improvement soon afterwards (left). Analogous effects can be observed around iteration 950 and 1250 (right). When contrasting with Figure 6(a)(right), we can observe that there exists an (inverted) relation between the number of edges shared and the quality of the solutions obtained. Thus validating our choice of the 2nd criterion as a part of the objective function. Figure 6: A representative example of the behavior of the extended aco algorithm. The effect of the mechanism for the partial destruction of the current best solution can be clearly observed. It is also interesting to observe the evolution of the second criterion as a measure for disjointness. the parallel construction of all paths (in contrast to their sequential construction), and (2) the use of candidate list strategies for the exploitation of the promising choices at each construction step. Concerning the search dynamics, we proposed (1) the use of two search phases that aim at the improvement of the two different criteria of the objective function, and (2) the partial destruction of the currently best solution as an escape mechanism. We have shown that these features help on improving the performance of the algorithm without spending more computation time. Rather on the contrary, the extended aco approach needs less computation time than the simple version in order to reach its best solutions. The results showed that our extended aco approach has in general advantages over the multi-start greedy approach in terms of solution quality as well as in terms of computation time. Furthermore, the results indicate that also in the run-time behavior 21 0 10 20 30 40 50 60 70 80 90 100 0 200 400 600 800 1000 1200 1400 1600 solution size |S| (nb.disjoint paths) time (seconds) Algorithms SGA MSGA simple ACO extended ACO (a) Example of the evolution in time of the quality of the solution Sgbest. The behavior shown here corresponds to the application to one of the 20 instances composed by graph4 and a list of 173 commodities. 0 10 20 30 40 50 60 70 80 90 5 10 15 20 25 solution size |S| (nb.disjoint paths) time (seconds) Algorithms SGA MSGA simple ACO extended ACO (b) Zoom on the first 25 seconds of Figure 7(a). The time needed to obtain good solutions is clearly smaller for the aco approaches. Note that in the first seconds the performance of the sga and the msga are identical due to dealing with the same permutation of the commodities. Figure 7: A representative example of the run-time behavior of the algorithms presented in this work. All the curves are smoothed with gnuplots’ sbezier function. the aco approach is superior to the multi-start greedy approach. Already in early stages of a run, the aco algorithm provides relatively good solutions. This might prove beneficial for an online-version of our algorithm, in which speed is an issue. The fact that our algorithm only uses local information for building paths, is another advantage, because the computation of shortest path information is costly. There are many possible directions for future work. From the algorithmic point of view, it would be interesting to study other possible greedy approaches including, for example, length restrictions on the routes. As observed in Kleinberg [26], length constraints can transform tractable disjoint paths problems into NP-hard variants (e.g., even the source-single sink case is NP-hard.) Furthermore, the relatively high degree of determinism used in our aco approach might suggest ideas for new greedy approaches. Concerning nature-inspired metaheuristics, it would be of high interest to explore the potential advantages of having multiple ant colonies or particle swarms. A first attempt on using more than one ant colony was recently done in [36]. However, the aim in [36] was not to solve the EDP problem but rather to explore the feasibility of multi-colony systems. Therefore, only toy examples of graphs of up to 20 nodes with 2 or 3 commodities were considered there. One of the drawbacks of having multiple colonies is the increase of the computational requirements of the algorithm, which may not be affordable when time matters. Further improvements should be tried also in order to tackle generalizations of the problem based on real-life features of nowadays networks (e.g., congestion, free bandwidth, adversarial traffic, etc.), which are specially interesting and challenging. To be tackled via ant colony optimization, this will require some changes to the aco approach, since ants will require a whole range of other types of locally available information. It will also be interesting to observe the behavior of our aco approach when applied in dynamically changing networks in which the adaptation to a changing environment is required. The nature of aco makes it a promising candidate for these conditions. Acknowledgements The authors would like to thank Martin Oellrich from the Combinatorial Optimization & Graph Algorithms group of the Technische Universit¨at Berlin for providing them with graph3 and graph4. 22 References [1] A. Aggarwal, A. Bar-Noy, D. Coppersmith, R. Ramaswami, B. Schieber, and M. Sudan. Efficient routing and scheduling algorithms for optical networks. In 5th. ACM-SIAM Symposium on Discrete Algorithms (soda’94), pages 412–423. Society for Industrial and Applied Mathematics, 1994. [2] S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM, 45(3):501–555, 1998. [3] Y. Aumann and Y. Rabani. Improved bounds for all-optical routing. In 6th. ACM-SIAM Symposium on Discrete Algorithms (soda’95), pages 567–576. Society for Industrial and Applied Mathematics, 1995. [4] B. Awerbuch, Y. Azar, and S. Plotkin. Throughput-competitive online routing. In 34th Annual IEEE Symposium on Foundations of Computer Science (focs’93), pages 32–40. IEEE Computer Society Press, 1993. [5] B. Awerbuch, R. Gawlick, F. Leighton, and Y. Rabani. On-line admission control and circuit routing for high performance computing and communication. In 35th. IEEE Symposium on Foundations of Computer Science (focs’94), pages 412–423. IEEE Computer Society Press, 1994. [6] A. Barab´asi and R. Albert. Emergence of scaling in random networks. Science, pages 509–512, 1999. [7] A. Baveja and A. Srinivasan. Approximation algorithms for disjoint paths and related routing and packing problems. Mathematics of Operations Research, 25(2):255–280, 2000. [8] M. Blesa and C. Blum. Ant colony optimization for the maximum edge-disjoint paths problem. In 1st European Workshop on Evolutionary Computation in Communications, Networks, and Connected Systems (Evocomnet’04), volume 3005 of Lecture Notes in Computer Science, pages 160–169. Springer-Verlag, 2004. [9] C. Blum and M. Dorigo. The hyper-cube framework for ant colony optimization. IEEE Transactions on Systems, Man, and Cybernetics–B, 34(2):1161–1172, 2004. [10] C. Blum and A. Roli. Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys, 35(3):268–308, 2003. [11] U. Brandes and D. Wagner. A linear time algorithm for the arc disjoint menger problem in planar directed graphs. Algorithmica, 28(1):16–36, 2000. [12] C. Chekuri and S. Khanna. Edge disjoint paths revisited. In 14th annual ACM-SIAM Symposium on Discrete algorithms (soda’03), pages 628–637. Society for Industrial and Applied Mathematics, 2003. [13] M.-C. Costa, L. L´etocart, and F. Roupin. Multicut and integral multiflow: a survey. European Journal of Operational Research, 162(1):55–69, 2005. [14] G. Di Caro and M. Dorigo. AntNet: Distributed stigmergetic control for communications networks. Journal of Artificial Intelligence Research, 9:317–365, 1998. [15] G. Di Caro, F. Ducatelle, and L. M. Gambardella. AntHocNet: An adaptive nature-inspired algorithm for routing in mobile ad hoc networks. European Transactions on Telecommunications, 16(2), 2005. [16] M. Dorigo. Ottimizzazione, Apprendimento Automatico, ed Algoritmi basati su Metafora Naturale. PhD thesis, DEI, Politecnico di Milano, Milan, Italy, 1992. 23 [17] M. Dorigo and L. Gambardella. Ant Colony System: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1):53–66, 1997. [18] M. Dorigo, V. Maniezzo, and A. Colorni. Ant System: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics–B, 26(1):29–41, 1996. [19] M. Dorigo and T. St¨utzle. Ant Colony Optimization. MIT Press, 2004. [20] T. Erlebach. Approximation algorithms and complexity results for path problems in trees of rings. In 26th International Symposium on Mathematical Foundations of Computer Science (mfcs’01), volume 2136 of Lecture Notes in Computer Science, pages 351–362. Springer- Verlag, 2001. [21] L. Gambardella and M. Dorigo. Solving symmetric and asymmetric TSPs by ant colonies. In IEEE International Conference on Evolutionary Computation (icec’96), pages 622–627. IEEE Computer Society Press, 1996. [22] N. Garg, V. Vazirani, and M. Yannakakis. Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica, 18(1):3–20, 1997. [23] V. Guruswami, S. Khanna, R. Rajaraman, B. Shepherd, and M. Yannakakis. Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. Journal of Computer and System Sciences, 67(3):473–496, 2003. [24] J. Hromkoviˇc, R. Klasing, E. St¨ohr, and H. Wagener. Gossiping in vertex-disjoing paths mode in d-dimensional grids and planar graphs. In 1st Annual European Symposium on Algorithms (esa’93), volume 726 of Lecture Notes in Computer Science, pages 200–211. Springer-Verlag, 1993. [25] R. Karp. Compexity of Computer Computations, chapter Reducibility among combinatorial problems, pages 85–103. Plenum Press, 1972. [26] J. Kleinberg. Approximation algorithms for disjoint paths problems. PhD thesis, MIT, Cambridge, USA, 1996. [27] S. Kolliopoulos and C. Stein. Approximating disjoint-path problems using packing integer programs. Mathematical Programming, 99(1):63–87, 2004. [28] P. Kolman and C. Scheideler. Simple on-line algorithms for the maximum disjoint paths problem. In 13th ACM Symposium on Parallel Algorithms and Architectures (spaa’01), pages 38–47. ACM Press, 2001. [29] P. Kolman and C. Scheideler. Improved bounds for the unsplittable flow problem. In 13th annual ACM-SIAM symposium on Discrete algorithms (soda’02), pages 184–193. Society for Industrial and Applied Mathematics, 2002. [30] M. Kramer and J. van Leeuwen. Advances in computing research, volume 2: VLSI theory, chapter The complexity of wire-routing and finding minimum area layouts for arbitrary VLSI circuits, pages 129–146. JAI Press, 1984. [31] B. Ma and L. Wang. On the inapproximability of disjoint paths and minimum steiner forest with bandwidth constraints. Journal of Computer and System Sciences, 60(1):1–12, 2000. [32] D. Marx. Eulerian disjoint paths problem in grid graphs is NP-complete. Discrete Applied Mathematics, 143(1–3):336–341, 2004. [33] A. Medina, A. Lakhina, I. Matta, and J. Byers. BRITE: Boston University Representative Internet Topoloy Generator. http://cs-pub.bu.edu/brite/index.htm, 2001. 24 [34] M. Middendorf and F. Pfeiffer. On the complexity of the disjoint path problem. Combinatorica, 13(1):97–107, 1993. [35] T. Nishizeki, J. Vygen, and X. Zhou. The edge-disjoint paths problem is np-complete for series-parallel graphs. Discrete Applied Mathematics, 115(1–3):177–186, 2001. [36] A. Now´e, K. Verbeeck, and P. Vrancx. Multi-type ant colony: The edge disjoint paths problem. In 4th International Workshop on Ant Colony Optimization and Swarm Intelligence (ants’04), volume 3172 of Lecture Notes in Computer Science, pages 202–213. Springer- Verlag, 2004. [37] P. Raghavan and E. Upfal. Efficient all-optical routing. In 26th. Annual ACM Symposium on Theory of Computing (stoc’94), pages 134–143. ACM Press, 1994. [38] H. Ripphausen-Lipa, D. Wagner, and K. Weihe. The vertex-disjoint Menger problem in planar graphs. SIAM Journal on Computing, 26(2):331–349, 1997. [39] D. Sidhu, R. Nair, and S. Abdallah. Finding disjoint paths in networks. ACM SIGCOMM Computer Communication Review, 21(4):43–51, 1991. [40] A. Srinivasan. Improved approximations for edge-disjoint paths, unsplittable flow and related routing problems. In 38th Annual IEEE Symposium on Foundations of Computer Science (focs’97), pages 416–425. IEEE Computer Society Press, 1997. [41] T. St¨utzle and H. Hoos. MAX-MIN ant system. Future Generation Computer Systems, 16(8):889–914, 2000. [42] K. Varadarajan and G. Venkataraman. Graph decomposition and a greedy algorithm for edgedisjoint paths. In 15th annual ACM-SIAM Symposium on Discrete Algorithms (soda’04), pages 379–380. Society for Industrial and Applied Mathematics, 2004. [43] J. Vygen. NP-completeness of some edge-disjoint paths problems. Discrete Applied Mathematics, 61(1):83–90, 1995. [44] B. Waxman. Routing of multipoint connections. IEEE Journal on Selected Areas in Communications, 6(9):1671–1622, 1988. [45] K. Weihe. Edge-disjoint (s−t)-paths in undirected planar graphs in linear time. Journal of Algorithms, 23(1):121–138, 1997. 25 0.1,0.1 0.1,1 0.1,10 1,0.1 1,1 1,10 10,0.1 10,1 10,10 6 7 8 9 10 Considering the beta and gamma parameters together (AS−BA.R−Wax.v100e190, 10 pairs, 1st phase YES, drate=0.75) Values of the beta and gamma parameters size (nb. disjoint paths) 0.1,0.1 0.1,1 0.1,10 1,0.1 1,1 1,10 10,0.1 10,1 10,10 10 12 14 16 18 Considering the beta and gamma parameters together (AS−BA.R−Wax.v100e190, 25 pairs, 1st phase YES, drate=0.75) Values of the beta and gamma parameters size (nb. disjoint paths) 0.1,0.1 0.1,1 0.1,10 1,0.1 1,1 1,10 10,0.1 10,1 10,10 14 16 18 20 22 Considering the beta and gamma parameters together (AS−BA.R−Wax.v100e190, 40 pairs, 1st phase YES, drate=0.75) Values of the beta and gamma parameters size (nb. disjoint paths) (a) Costs of the best solutions found 0.1,0.1 0.1,1 0.1,10 1,0.1 1,1 1,10 10,0.1 10,1 10,10 0 1 2 3 Considering the beta and gamma parameters together (AS−BA.R−Wax.v100e190, 10 pairs, 1st phase YES, drate=0.75) Values of the beta and gamma parameters time to find the best (seconds) 0.1,0.1 0.1,1 0.1,10 1,0.1 1,1 1,10 10,0.1 10,1 10,10 0 2 4 6 8 Considering the beta and gamma parameters together (AS−BA.R−Wax.v100e190, 25 pairs, 1st phase YES, drate=0.75) Values of the beta and gamma parameters time to find the best (seconds) 0.1,0.1 0.1,1 0.1,10 1,0.1 1,1 1,10 10,0.1 10,1 10,10 0 5 10 15 Considering the beta and gamma parameters together (AS−BA.R−Wax.v100e190, 40 pairs, 1st phase YES, drate=0.75) Values of the beta and gamma parameters time to find the best (seconds) (b) Times needed to find the best solutions Figure 12: Analyzing parameters βand γtogether when fixing distinguishphase1to yes, the determinism rate (drate) to 0.75. The results are obtained for graph AS-BA.R-Wax.v100e190 when looking for 10 (leftmost graphic), 25 (middle) and 40 (rightmost graphic) disjoint paths (0.1|V|, 0.25|V|and 0.4|V|, respectively) between randomly chosen nodes. In each graphic, the x-axis considers the different combinations of values for the pair (β,γ) of parameters, i.e., (0.1,0.1), (0.1,1), (0.1,10), (1,0.1), (1,1), (1,10), (10,0.1), (10,1), and (10,10), from left to right, respectively). The subfigure (a) shows the cost of the best solutions found, while subfigure (b) shows the time needed to reach those best solutions. 7 0.01 0.05 0.10 7.0 7.5 8.0 8.5 9.0 9.5 10.0 Considering the eating−away rate (AS−BA.R−Wax.v100e190, 10 pairs, 1st phase YES, drate 0.75, beta 1, gamma 1) Eating−away rate size (nb. disjoint paths) 0.01 0.05 0.10 11 12 13 14 15 16 17 Considering the eating−away rate (AS−BA.R−Wax.v100e190, 25 pairs, 1st phase YES, drate 0.75, beta 1, gamma 1) Eating−away rate size (nb. disjoint paths) 0.01 0.05 0.10 14 16 18 20 22 Considering the eating−away rate (AS−BA.R−Wax.v100e190, 40 pairs, 1st phase YES, drate 0.75, beta 1, gamma 1) Eating−away rate size (nb. disjoint paths) (a) Costs of the best solutions found 0.01 0.05 0.10 0.0 0.5 1.0 1.5 2.0 2.5 Considering the eating−away rate (AS−BA.R−Wax.v100e190, 10 pairs, 1st phase YES, drate 0.75, beta 1, gamma 1) Eating−away rate time to find the best (seconds) 0.01 0.05 0.10 02468 Considering the eating−away rate (AS−BA.R−Wax.v100e190, 25 pairs, 1st phase YES, drate 0.75, beta 1, gamma 1) Eating−away rate time to find the best (seconds) 0.01 0.05 0.10 0 2 4 6 8 10 12 Considering the eating−away rate (AS−BA.R−Wax.v100e190, 40 pairs, 1st phase YES, drate 0.75, beta 1, gamma 1) Eating−away rate time to find the best (seconds) (b) Times needed to find the best solutions Figure 13: Analyzing the evaporation rate (erate)when fixing distinguishphase1to yes, the determinism rate (drate) to 0.75, βto 1, and γto 1. The results are obtained for graph AS-BA.R- Wax.v100e190 when looking for 10 (leftmost graphic), 25 (middle) and 40 (rightmost graphic) disjoint paths (0.1|V|, 0.25|V|and 0.4|V|, respectively) between randomly chosen nodes. In each graphic, the x-axis considers the values tested for the evaporation rate (erate =0.01, erate =0.05 and erate =0.10, from left to right, respectively). The subfigure (a) shows the cost of the best solutions found, while subfigure (b) shows the time needed to reach those best solutions. 8 SEQ 2 candidates SEQ 50% candidates SEQ all candidates 11 12 13 14 15 16 17 18 Considering the candidate list strategy (AS−BA.R−Wax.v100e190, 25 pairs, 1st phase YES, beta 1, gamma 1, drate 0.75, erate 0.10, destrate 0) Candidates considered size (nb. disjoint paths) PAR PAR PAR 11 12 13 14 15 16 17 18 SR 2 candidates SR 50% candidates SR all candidates 11 12 13 14 15 16 17 18 Considering the candidate list strategy (AS−BA.R−Wax.v100e190, 25 pairs, 1st phase YES, beta 1, gamma 1, drate 0.75, erate 0.10, destrate 0.25) Candidates considered size (nb. disjoint paths) SL SL SL 11 12 13 14 15 16 17 18 PR PR PR 11 12 13 14 15 16 17 18 PL PL PL 11 12 13 14 15 16 17 18 SR 2 candidates SR 50% candidates SR all candidates 11 12 13 14 15 16 17 18 Considering the candidate list strategy (AS−BA.R−Wax.v100e190, 25 pairs, 1st phase YES, beta 1, gamma 1, drate 0.75, erate 0.10, destrate 0.5) Candidates considered size (nb. disjoint paths) SL SL SL 11 12 13 14 15 16 17 18 PR PR PR 11 12 13 14 15 16 17 18 PL PL PL 11 12 13 14 15 16 17 18 (a) The cases of no destruction (leftmost graphic), 25% destruction (middle) and 50% destruction (rightmost graphic) are considered. The x-axis of each graphic shows different sizes for the candidate lists (i.e., 2 candidates, 50% candidates and all the candidates), together with the different solution construction strategies (i.e., sequential and parallel). 0 0 |−−− s e q u e n t i a l −−−| |−−−−− p a r a l l e l −−−−−| 12 13 14 15 16 17 18 Considering the candidate list strategy (AS−BA.R−Wax.v100e190, 25 pairs, 1st phase YES, beta 1, gamma 1, drate 0.75, erate 0.10, 2 candidates) Solution construction strategy and destruction rate and type size (nb. disjoint pahts) 0.25 rand 0.25 rand 12 13 14 15 16 17 18 0.25 long 0.25 long 12 13 14 15 16 17 18 0.5 rand 0.5 rand 12 13 14 15 16 17 18 0.5 long 0.5 long 12 13 14 15 16 17 18 0 0 |−−− s e q u e n t i a l −−−| |−−−−− p a r a l l e l −−−−−| 12 13 14 15 16 17 18 Considering the candidate list strategy (AS−BA.R−Wax.v100e190, 25 pairs, 1st phase YES, beta 1, gamma 1, drate 0.75, erate 0.10, 50% candidates) Solution construction strategy and destruction rate and type size (nb. disjoint pahts) 0.25 rand 0.25 rand 12 13 14 15 16 17 18 0.25 long 0.25 long 12 13 14 15 16 17 18 0.5 rand 0.5 rand 12 13 14 15 16 17 18 0.5 long 0.5 long 12 13 14 15 16 17 18 0 0 |−−− s e q u e n t i a l −−−| |−−−−− p a r a l l e l −−−−−| 12 13 14 15 16 17 18 Considering the candidate list strategy (AS−BA.R−Wax.v100e190, 25 pairs, 1st phase YES, beta 1, gamma 1, drate 0.75, erate 0.10, all candidates) Solution construction strategy and destruction rate and type size (nb. disjoint pahts) 0.25 rand 0.25 rand 12 13 14 15 16 17 18 0.25 long 0.25 long 12 13 14 15 16 17 18 0.5 rand 0.5 rand 12 13 14 15 16 17 18 0.5 long 0.5 long 12 13 14 15 16 17 18 (b) The cases of considering only 2 candidates (leftmost graphic), 50% of the candidates (middle) and all the candidates (rightmost graphic) are shown. The x-axis of each graphic shows from left to right, respectively, different combinations of values for the solution construction (i.e., sequential or parallel), and for the combination of destruction rate and destruction type (i.e., any destruction, 25% destruction of randomly chosen paths, 25% destruction of the longest paths, 50% destruction of randomly chosen paths, and 50% destruction of the longest paths). Figure 14: Two different ways of showing the information concerning the joined analysis of the candidate lists size, the destruction rate, the destruction type and the sequential/parallel solution construction strategies. The results are obtained for graph AS-BA.R- Wax.v100e190 when trying to establish disjoint paths between 25 randomly chosen endpoints (i.e., 0.25|V|) of the graph, and fixing first phase to yes, the determinism rate (drate) to 0.75, βand γto 1, and erate to 0.10. Only the cost of the best obtained solutions are plotted. Subfigure 14(a) presents the information separated according to the destruction rate; then, the information is separated according to the size of the candidate lists and, for each of these values, according to the solution construction strategy. Subfigure 14(b) presents the information separated according to the candidate lists size; then, the information is discretized according to the different solution construction strategies and, in each of the categories, a finer grain is obtained according the destruction rate and type. 9 SEQ 2 candidates SEQ 50% candidates SEQ all candidates 14 16 18 20 22 Considering the candidate list strategy (AS−BA.R−Wax.v100e190, 40 pairs, 1st phase YES, beta 1, gamma 1, drate 0.75, erate 0.10, destrate 0) Candidates considered size (nb. disjoint paths) PAR PAR PAR 14 16 18 20 22 SR 2 candidates SR 50% candidates SR all candidates 14 16 18 20 22 Considering the candidate list strategy (AS−BA.R−Wax.v100e190, 40 pairs, 1st phase YES, beta 1, gamma 1, drate 0.75, erate 0.10, destrate 0.25) Candidates considered size (nb. disjoint paths) SL SL SL 14 16 18 20 22 PR PR PR 14 16 18 20 22 PL PL PL 14 16 18 20 22 SR 2 candidates SR 50% candidates SR all candidates 14 16 18 20 22 Considering the candidate list strategy (AS−BA.R−Wax.v100e190, 40 pairs, 1st phase YES, beta 1, gamma 1, drate 0.75, erate 0.10, destrate 0.5) Candidates considered size (nb. disjoint paths) SL SL SL 14 16 18 20 22 PR PR PR 14 16 18 20 22 PL PL PL 14 16 18 20 22 (a) The cases of no destruction (leftmost graphic), 25% destruction (middle) and 50% destruction (rightmost graphic) are considered. The x-axis of each graphic shows different sizes for the candidate lists (i.e., 2 candidates, 50% candidates and all the candidates), together with the different solution construction strategies (i.e., sequential and parallel). 0 0 |−−− s e q u e n t i a l −−−| |−−−−− p a r a l l e l −−−−−| 14 16 18 20 22 Considering the candidate list strategy (AS−BA.R−Wax.v100e190, 40 pairs, 1st phase YES, beta 1, gamma 1, drate 0.75, erate 0.10, 2 candidates) Solution construction strategy and destruction rate and type size (nb. disjoint pahts) 0.25 rand 0.25 rand 14 16 18 20 22 0.25 long 0.25 long 14 16 18 20 22 0.5 rand 0.5 rand 14 16 18 20 22 0.5 long 0.5 long 14 16 18 20 22 0 0 |−−− s e q u e n t i a l −−−| |−−−−− p a r a l l e l −−−−−| 14 16 18 20 22 Considering the candidate list strategy (AS−BA.R−Wax.v100e190, 40 pairs, 1st phase YES, beta 1, gamma 1, drate 0.75, erate 0.10, 50% candidates) Solution construction strategy and destruction rate and type size (nb. disjoint pahts) 0.25 rand 0.25 rand 14 16 18 20 22 0.25 long 0.25 long 14 16 18 20 22 0.5 rand 0.5 rand 14 16 18 20 22 0.5 long 0.5 long 14 16 18 20 22 0 0 |−−− s e q u e n t i a l −−−| |−−−−− p a r a l l e l −−−−−| 14 16 18 20 22 Considering the candidate list strategy (AS−BA.R−Wax.v100e190, 40 pairs, 1st phase YES, beta 1, gamma 1, drate 0.75, erate 0.10, all candidates) Solution construction strategy and destruction rate and type size (nb. disjoint pahts) 0.25 rand 0.25 rand 14 16 18 20 22 0.25 long 0.25 long 14 16 18 20 22 0.5 rand 0.5 rand 14 16 18 20 22 0.5 long 0.5 long 14 16 18 20 22 (b) The cases of considering only 2 candidates (leftmost graphic), 50% of the candidates (middle) and all the candidates (rightmost graphic) are shown. The x-axis of each graphic shows from left to right, respectively, different combinations of values for the solution construction (i.e., sequential or parallel), and for the combination of destruction rate and destruction type (i.e., any destruction, 25% destruction of randomly chosen paths, 25% destruction of the longest paths, 50% destruction of randomly chosen paths, and 50% destruction of the longest paths). Figure 15: Two different ways of showing the information concerning the joined analysis of the candidate list size, the destruction rate, the destruction type and the sequential/parallel solution construction strategies. The results are obtained for graph AS-BA.R- Wax.v100e190 when trying to establish disjoint paths between 40 randomly chosen endpoints (i.e., 0.40|V|) of the graph, and fixing first phase to yes, the determinism rate (drate) to 0.75, βand γto 1, and the eating away parameter (erate) to 0.10. Only the cost of the best obtained solutions are plotted. Subfigure 15(a) presents the information separated according to the destruction rate; then, the information is discretized according to the size of the candidate lists and, for each of these values, according to the solution construction strategy. Subfigure 15(b) presents the information separated according to the candidate list size; then, the information is discretized according to the different solution construction strategies and, in each of the categories, a finer grain is obtained according the destruction rate and type. 10 SEQ 2 candidates SEQ 50% candidates SEQ all candidates 58 60 62 64 66 68 70 72 Considering the candidates list strategy (graph4, 108 pairs, 1st phase YES, beta 1, gamma 1, drate 0.75, erate 0.10, destrate 0) Candidates considered size (nb. disjoint paths) PAR PAR PAR 58 60 62 64 66 68 70 72 SR 2 candidates SR 50% candidates SR all candidates 58 60 62 64 66 68 70 72 Considering the candidates list strategy (graph4, 108 pairs, 1st phase YES, beta 1, gamma 1, drate 0.75, erate 0.10, destrate 0.25) Candidates considered size (nb. disjoint paths) SL SL SL 58 60 62 64 66 68 70 72 PR PR PR 58 60 62 64 66 68 70 72 PL PL PL 58 60 62 64 66 68 70 72 SR 2 candidates SR 50% candidates SR all candidates 58 60 62 64 66 68 70 72 Considering the candidates list strategy (graph4, 108 pairs, 1st phase YES, beta 1, gamma 1, drate 0.75, erate 0.10, destrate 0.5) Candidates considered size (nb. disjoint paths) SL SL SL 58 60 62 64 66 68 70 72 PR PR PR 58 60 62 64 66 68 70 72 PL PL PL 58 60 62 64 66 68 70 72 (a) The cases of no destruction (leftmost graphic), 25% destruction (middle) and 50% destruction (rightmost graphic) are considered. The x-axis of each graphic shows different sizes for the candidate lists (i.e., 2 candidates, 50% candidates and all the candidates), together with the different solution construction strategies (i.e., sequential and parallel). 0 0 |−−− s e q u e n t i a l −−−| |−−−−− p a r a l l e l −−−−−| 60 65 70 Considering the candidates list strategy (graph4, 108 pairs, 1st phase YES, beta 1, gamma 1, drate 0.75, erate 0.10, 2 candidates) Solution construction strategy and destruction rate and type size (nb. disjoint pahts) 0.25 rand 0.25 rand 60 65 70 0.25 long 0.25 long 60 65 70 0.5 rand 0.5 rand 60 65 70 0.5 long 0.5 long 60 65 70 0 0 |−−− s e q u e n t i a l −−−| |−−−−− p a r a l l e l −−−−−| 60 65 70 Considering the candidates list strategy (graph4, 108 pairs, 1st phase YES, beta 1, gamma 1, drate 0.75, erate 0.10, 50% candidates) Solution construction strategy and destruction rate and type size (nb. disjoint pahts) 0.25 rand 0.25 rand 60 65 70 0.25 long 0.25 long 60 65 70 0.5 rand 0.5 rand 60 65 70 0.5 long 0.5 long 60 65 70 0 0 |−−− s e q u e n t i a l −−−| |−−−−− p a r a l l e l −−−−−| 60 65 70 Considering the candidates list strategy (graph4, 108 pairs, 1st phase YES, beta 1, gamma 1, drate 0.75, erate 0.10, all candidates) Solution construction strategy and destruction rate and type size (nb. disjoint pahts) 0.25 rand 0.25 rand 60 65 70 0.25 long 0.25 long 60 65 70 0.5 rand 0.5 rand 60 65 70 0.5 long 0.5 long 60 65 70 (b) The cases of considering only 2 candidates (leftmost graphic), 50% of the candidates (middle) and all the candidates (rightmost graphic) are shown. The x-axis of each graphic shows from left to right, respectively, different combinations of values for the solution construction (i.e., sequential or parallel), and for the combination of destruction rate and destruction type (i.e., any destruction, 25% destruction of randomly chosen paths, 25% destruction of the longest paths, 50% destruction of randomly chosen paths, and 50% destruction of the longest paths). Figure 16: Two different ways of showing the information concerning the joined analysis of the candidate list size, the destruction rate, the destruction type and the sequential/parallel solution construction strategies. The results are obtained for graph graph4 when trying to establish disjoint paths between 108 randomly chosen endpoints (i.e., 0.25|V|) of the graph, and fixing first phase to yes, the determinism rate (drate) to 0.75, βand γto 1, and the eating away parameter (erate) to 0.10. Only the cost of the best obtained solutions are plotted. Subfigure 16(a) presents the information separated according to the destruction rate; then, the information is discretized according to the size of the candidate lists and, for each of these values, according to the solution construction strategy. Subfigure 16(b) presents the information separated according to the candidate list size; then, the information is discretized according to the different solution construction strategies and, in each of the categories, a finer grain is obtained according the destruction rate and type. 11 SEQ 2 candidates SEQ 50% candidates SEQ all candidates 75 80 85 90 Considering the candidates list strategy (graph4, 173 pairs, 1st phase YES, beta 1, gamma 1, drate 0.75, erate 0.10, destrate 0) Candidates considered size (nb. disjoint paths) PAR PAR PAR 75 80 85 90 SR 2 candidates SR 50% candidates SR all candidates 75 80 85 90 Considering the candidates list strategy (graph4, 173 pairs, 1st phase YES, beta 1, gamma 1, drate 0.75, erate 0.10, destrate 0.25) Candidates considered size (nb. disjoint paths) SL SL SL 75 80 85 90 PR PR PR 75 80 85 90 PL PL PL 75 80 85 90 SR 2 candidates SR 50% candidates SR all candidates 75 80 85 90 Considering the candidates list strategy (graph4, 173 pairs, 1st phase YES, beta 1, gamma 1, drate 0.75, erate 0.10, destrate 0.5) Candidates considered size (nb. disjoint paths) SL SL SL 75 80 85 90 PR PR PR 75 80 85 90 PL PL PL 75 80 85 90 (a) The cases of no destruction (leftmost graphic), 25% destruction (middle) and 50% destruction (rightmost graphic) are considered. The x-axis of each graphic shows different sizes for the candidate lists (i.e., 2 candidates, 50% candidates and all the candidates), together with the different solution construction strategies (i.e., sequential and parallel). 0 0 |−−− s e q u e n t i a l −−−| |−−−−− p a r a l l e l −−−−−| 75 80 85 90 Considering the candidates list strategy (graph4, 173 pairs, 1st phase YES, beta 1, gamma 1, drate 0.75, erate 0.10, 2 candidates) Solution construction strategy and destruction rate and type size (nb. disjoint pahts) 0.25 rand 0.25 rand 75 80 85 90 0.25 long 0.25 long 75 80 85 90 0.5 rand 0.5 rand 75 80 85 90 0.5 long 0.5 long 75 80 85 90 0 0 |−−− s e q u e n t i a l −−−| |−−−−− p a r a l l e l −−−−−| 75 80 85 90 Considering the candidates list strategy (graph4, 173 pairs, 1st phase YES, beta 1, gamma 1, drate 0.75, erate 0.10, 50% candidates) Solution construction strategy and destruction rate and type size (nb. disjoint pahts) 0.25 rand 0.25 rand 75 80 85 90 0.25 long 0.25 long 75 80 85 90 0.5 rand 0.5 rand 75 80 85 90 0.5 long 0.5 long 75 80 85 90 0 0 |−−− s e q u e n t i a l −−−| |−−−−− p a r a l l e l −−−−−| 75 80 85 90 Considering the candidates list strategy (graph4, 173 pairs, 1st phase YES, beta 1, gamma 1, drate 0.75, erate 0.10, all candidates) Solution construction strategy and destruction rate and type size (nb. disjoint pahts) 0.25 rand 0.25 rand 75 80 85 90 0.25 long 0.25 long 75 80 85 90 0.5 rand 0.5 rand 75 80 85 90 0.5 long 0.5 long 75 80 85 90 (b) The cases of considering only 2 candidates (leftmost graphic), 50% of the candidates (middle) and all the candidates (rightmost graphic) are shown. The x-axis of each graphic shows from left to right, respectively, different combinations of values for the solution construction (i.e., sequential or parallel), and for the combination of destruction rate and destruction type (i.e., any destruction, 25% destruction of randomly chosen paths, 25% destruction of the longest paths, 50% destruction of randomly chosen paths, and 50% destruction of the longest paths). Figure 17: Two different ways of showing the information concerning the joined analysis of the candidate list size, the destruction rate, the destruction type and the sequential/parallel solution construction strategies. The results are obtained for graph graph4 when trying to establish disjoint paths between 173 randomly chosen endpoints (i.e., 0.40|V|) of the graph, and fixing first phase to yes, the determinism rate (drate) to 0.75, βand γto 1, and the eating away parameter (erate) to 0.10. Only the cost of the best obtained solutions are plotted. Subfigure 17(a) presents the information separated according to the destruction rate; then, the information is discretized according to the size of the candidate lists and, for each of these values, according to the solution construction strategy. Subfigure 17(b) presents the information separated according to the candidate list size; then, the information is discretized according to the different solution construction strategies and, in each of the categories, a finer grain is obtained according the destruction rate and type. 12