1 Introduction

Nowadays, the number of users of the Internet has raised exponentially. Unfortunately, our current data networks are not able to support this exponential growth because their bandwidth is not sufficient. The usage of optical data networks is a suitable option for dealing with this drawback.

Since the vast majority of devices require only a few Gbps of bandwidth, there exists a wastage of bandwidth in each optical link (an optical fiber is around 50 Tbps). To optimize the usage of bandwidth in optical networks, a new technology has been introduced. This technique is known as wavelength division multiplexing (WDM). This technology multiplies the available capacity of an optical fiber link by adding new channels, with each channel on a new wavelength of light. The aim of WDM is to ensure fluent communications between several devices, avoiding bottlenecks (Hamad and Kamal 2002).

However, a problem occurs when it is necessary to establish a set of traffic demands. This problem is known in the literature as routing and wavelength assignment (RWA) problem. The RWA problem consists of two subproblems: routing and wavelength assignment. As shown in Fig. 1, in the first place, we calculate a physical route for connection (A, F): A–B–C–F. Afterward, we assign to each physical link of this route an available wavelength (λ1). This connection carried end-to-end from a source node to a destination node over a wavelength on each intermediate optical fiber link is known as lightpath A–λ1–B–λ1–C–λ1–F.

Fig. 1
figure 1

Illustrative representation of a lightpath

Full size image

There are two varieties of RWA problem: depending on the establishment of the demands, we could refer to a static problem when the demands are given in advance (static RWA problem), and a dynamic problem when the demands are given in real time (dynamic RWA problem). Since wide area networks are oriented to precontracted services (Hamad and Kamal 2002), in this work we focus on tackling the static RWA problem.

In this paper, we have developed a new multiobjective evolutionary algorithm (MOEA) for solving the static RWA problem. It is a multiobjective version of the artificial bee colony (ABC) algorithm. The main feature of the ABC algorithm is that it performs a kind of exploitative neighborhood search combined with random explorative search; so, unlike other metaheuristics, it has a well-balanced exploration and exploitation ability, which allows it to solve real-world problems in an efficient way (Sonmez 2011; Yeh and Hsieh 2011).

Since we tackle the static RWA problem as a multiobjective optimization problem, we have to adapt the heuristics to the multiobjective context (MO-ABC). To demonstrate the proper functioning of our proposal, we present several comparisons with other approaches published in the literature.

The rest of this work is organized as follows. In Sect. 2, we present how other authors have dealt with this problem. The static RWA problem is presented in a formal way in Sect. 3. A description of the multiobjective artificial bee colony algorithm appears in Sect. 4. With the aim of proving the good functioning of the MO-ABC algorithm, in Sect. 5, we present several comparisons with other approaches published in the literature. Finally, the conclusions and future work are left for Sect. 6.

2 Related work

As mentioned in the previous section, the RWA problem can be divided into two subproblems: on the one hand, the routing of the connection requests over a given topology, and on the other hand assigning an available wavelength at each link of each path established. Ramaswami and Sivarajan (1995) propose mixed-integer linear programming for solving each subproblem separately. Zang et al. (2000) make a review of several heuristics for solving both subproblems of routing and wavelength assignment.

For solving the first subproblem, there exist three well-known methods, which have been applied in the literature. In the first place, we found fixed routing heuristics which calculates a single permanent route for each demand (Li and Somani 1999) and determines routes using a least cost algorithm. In the second place, a modification of fixed routing, known as fixed-alternate routing (Chan and Yum 1994; Masayuki et al. 1997), stores several fixed routes instead of one. Finally, the heuristics adaptive routing offers a trade-off between quality of network information and overhead (Ramamurthy and Mukherjee 2002). Varela and Sinclair (1999) propose different varieties of ant colony optimization (ACO) algorithms for solving the routing subproblem.

Several approaches have been suggested in the literature for solving the second subproblem. Some examples of these heuristics for tackling the wavelength assignment subproblem are: Random, First-Fit, Least-Used, Most-Used, Min-Product, and Least Loaded (Chlamtac et al. 1989; Birman and Kershenbaum 1995; Jeong and Ayanoglu 1996). The MAX-SUM heuristics is presented in Barry and Subramaniam (1997). In Karasan and Ayanoglu (1998), Subramaniam and Barry (1997), and Zhang and Qiao (1998), the Relative Capacity Loss, Wavelength Reservation, and Protecting Threshold are proposed.

Since the RWA problem requires excessive computational efforts, several authors have dealt with it using metaheuristics. Morley and Grover (2001), Grosso et al. (2001), and Yan et al. (2001) tackle the RWA using Tabu Search algorithm. Other authors decide to apply Simulated Annealing to solve this telecommunication problem (Mukherjee et al. 1996; Rodriguez-Dagnino et al. 1999), as well as genetic algorithm (Inkret et al. 1998; Ali et al. 1999; Shiann-Tsong et al. 2001; Zong and Ramamurthy 2001; Saha and Sengupta 2005; Banerjee et al. 2004). Thompson and Bilbro (2000) make a comparison between a genetic algorithm and a simulated annealing approach, concluding that the first one obtains better performance than the second one.

All the previously mentioned proposals consider the RWA problem as monobjective and solve both subproblems separately. However, in more recent literature, this problem has been tackled as a multiobjective optimization problem, in which both subproblems are solved jointly.

In Insfrán et al. (2006) and Arteta et al. (2007), several multiobjective varieties of ant colony optimization algorithms are suggested. Furthermore, in Arteta et al. (2007), the authors present a comparison among many varieties of MOACOs and typical heuristics in the telecommunication field.

Rubio-Largo et al. (2010a, b) present two multiobjective metaheuristics for solving the RWA problem. They are multiobjective varieties of the well-known differential evolution and variable neighborhood search algorithms; they refer to them as DEPT and MO-VNS, respectively.

This work is an extended and improved version of the work published in the 11th International Work Conference on Artificial Neural Networks (IWANN 2011) (Rubio-Largo et al. 2011). In this manuscript, the background—including key concepts and related work—has been extended. The description of the MO-ABC procedure has been improved through a more detailed explanation of the algorithm with the representation of the individuals. In the experimental study, the number of problem instances is doubled, including an additional real-world network topology and more complex sets of requests. Furthermore, a statistical analysis of the results is presented.

3 Routing and wavelength assignment problem

This section consists of two subsections. In the first place, we present in a formal way the problem formulation and, secondly, we illustrate the problem using an example to facilitate the understanding of this telecommunication problem.

3.1 Problem formulation

In this paper, an optical network is modeled as a direct graph \(G=(V,E,C),\) where V is the set of nodes, E is the set of links between nodes, and C is the set of available wavelengths for each optical link in E.

  • \((i,j) \in E{:}\) optical link from node i to node j.

  • \(c_{ij} \in C{:}\) number of channels or different wavelengths at link \((i,j)\).

  • \(u=(s_u, d_u){:}\) unicast request u with source node \(s_u\) and a destination node \(d_u\), where \(s_u, d_u \in V\).

  • \(U{:}\) set of unicast requests, where \(U=\{ u |u \text{ is} \text{ an} \text{ unicast} \text{ request}\}\). Note that \(|U|\) is the number of unicast requests.

  • \(u_{i,j}^\lambda{:}\) wavelength λ assigned to the unicast request u at link \((i,j)\).

  • \(l_u{:}\) lightpath or set of links between a source node \(s_u\) and destination node \(d_u\); with the corresponding wavelength assignment in each link \((i,j)\).

  • \(L_U{:}\) solution of the RWA problem considering the set of U requests.

Note that \(L_U = \{l_u\;|\;l_u \text{ is} \text{ the} \text{ set} \text{ of} \text{ links} \text{ with} \text{ their} \text{ corresponding} \text{ wavelength} \text{ assignment} \}.\) Using the above definitions, the RWA problem may be stated as a multiobjective optimization problem (Coello et al. 2010), searching the best solution \(L_u\) that simultaneously minimizes the following two objective functions:

  1. 1.

    Number of hops:

    $$\begin{aligned} y_1=\sum _{u \in U}{|l_u|} \end{aligned}$$
    (1)

    \({\rm where} \;|l_u|\;{\rm is\;the\;cardinality\;(number\;of\;links)\;of\;the\;set}\;l_{u}\)

  2. 2.

    Number of wavelength (λ) conversions:

    $$\begin{aligned} y_2=\sum _{u \in U}{\sum _{i \in V}{ \varphi _i^u}} \quad {\rm where} \left\{ \begin{array}{ll} \varphi _i^u = 1 & \text{ if } i \in V {\rm switches } \lambda \\ \varphi _i^u = 0&{\rm otherwise} \\ \end{array}\right\} \end{aligned}$$
    (2)

Furthermore, we have to fulfill the wavelength conflict constraint: Two different unicast transmissions must be allocated with different wavelengths when they are transmitted through the same optical link \((i,j)\).

Fig. 2
figure 2

Example of RWA problem

Full size image
Fig. 3
figure 3

Representation of an Individual (k-shortest paths = 2)

Full size image

3.2 Example of RWA problem

In this subsection, we show an illustrative example of the RWA problem. The main aim is to facilitate the understanding of the problem formulation as well as the objective functions presented in Sect. 3.1.

Statement: Given the optical network topology of Fig. 2, we will suppose the following set of demands (U) and number of different wavelengths at link (\(c_{ij}\)):

$$\begin{aligned} U = \{(C, D) (C, F) (D, G) (B, F)\}, c_{ij} = 2 \end{aligned}$$

As we can observe in Fig. 2, the demands (C, D), (C, F), and (D, G) do not present any wavelength switching; however, the demand (B, F) presents one wavelength conversion in node D. Therefore, the solution consists of ten hops (\(y_1=10\)) and one wavelength conversion (\(y_2=1\)).

The solution presented for this topology might not be the best one; this example only tries to help explain the problem formulation and the objective functions.

4 Multiobjective artificial bee colony algorithm

The artificial bee colony (ABC) algorithm created by Karaboga and Akay (2009) is a population-based algorithm inspired by the intelligent behavior of honeybees.

The colony of artificial bees contains three groups of bees: employed, onlooker, and scout; so, the size of the colony is \(N + {\rm NS}\) bees, where N is the sum of the employed and the onlooker bees, and NS is the number of scout bees. In this way, the first half of N consists of employed bees and the second half constitutes the onlooker bees. The onlooker bee waits in the dance area for making decision to choose a food source, and a bee going to the food source visited by itself previously is an employed bee. Finally, NS scout bees carry out random searches of new food sources. In the ABC algorithm, a possible solution to an optimization problem is represented by the position of food source, where the quality (fitness) of the solution corresponds with the amount of nectar of this food source.

In this paper, we propose the multiobjective artificial bee colony (MO-ABC) algorithm. This multiobjective version is based on the ABC algorithm, but adapted to solve multiobjective optimization problems.

The representation of the individuals determines how the problem is structured, providing us with the necessary information to understand the behavior of the MO-ABC algorithm. The representation of an individual is presented in Fig. 3. It corresponds with the solution shown in the RWA example (Fig. 2). We start calculating the k-shortest paths (by running the Yen’s algorithm) from each source node s to each destination node d of the U. Then, for each shortest path, we generate a list with all possible combinations with the available wavelengths (\(c_{ij}\)); so, if the shortest path consists of n hops, and we have \(c_{ij}\) available wavelengths per link, then we generate \(c_{ij}^n\) possible lightpaths. In Fig. 3, the shortest path D–F–G consists of 2 hops; thus, supposing \(c_{ij}=2\), we generate \(2^{2}\) possible lightpaths:

  • \(D{-}\lambda _1{-}F{-}\lambda _1{-}G\)

  • \(D{-}\lambda _1{-}F{-}\lambda _2{-}G\)

  • \(D{-}\lambda _2{-}F{-}\lambda _1{-}G\)

  • \(D{-}\lambda _2{-}F{-}\lambda _2{-}G\)

To generate a random individual, we choose randomly a possible lightpath (fulfilling the wavelength conflict constraint) from the generated list of each demand of the set U and store a pointer to the entry of the list in the chromosome of the individual. Note that the set of lists is only calculated once, at the beginning of the execution of the algorithm.

With the aim of adapting the ABC algorithm to the multiobjective domain, we have used the fast non-dominated sort procedure from the well-known fast non-dominated sorting genetic algorithm (NSGA-II) (Deb et al. 2002).

In Algorithm 1, we show the pseudocode for the MO-ABC algorithm. As we can see, the population (colony C) consists of N  + NS individuals or bees (line 1 in Algorithm 1).

In the first place, we calculate the first half of N with random employed bees and, after that, for each employed bee its respective value of MOFitness (Weicker et al. 2003) (lines 3–6). The MOFitness parameter is a scalar value used for measuring the quality of each bee (see Eq. 3).

$$\begin{aligned} MOFitness (X_i) = |isDominated(X_i)|*N + |Dominates(X_i)| \end{aligned}$$
(3)

In Eq. 3, \(isDominated\) is the set of bees which dominate \(X_i\). On the other hand, \(Dominates\) is the set of bees which are dominated by \(X_i\). Note that we use the cardinality of these sets for calculating the value of MOFitness. To sum up, the MOFitness of each bee is obtained considering the quality of each bee with regard to the remaining bees from the colony.

figure a

Afterward, we initialize the set of non-dominated solutions (Pareto Front) as empty, as indicated in line 7 of Algorithm 1.

Every generation of the algorithm can be divided into three steps. Firstly, we improve the first half of N (lines 9–16), which contains the employed bees. In order to improve them, we apply to each employed bee a mutation (the amount of mutation is defined by the mutation factor F). After that, we have to check whether this new bee (\(X_{mutatedEB}\)) has better value of MOFitness than its ancestor (\(X_{EB}\)). In that case, \(X_{EB}\) is replaced by \(X_{mutatedEB}\); otherwise, \(X_{EB}\) stays in the colony and \(X_{mutatedEB}\) is discarded. Once the employed bees have been improved, we generate a probability vector (line 18), which contains the probability of an employed bee to be selected in the next step.

Secondly, we generate the second half of N, which contains the onlooker bees (lines 19–29). To generate an onlooker bee (\(X_{OB}\)), we have to select an employed bee (\(X_j\)) according to the probability vector. After applying a mutation to the selected bee, we check if this mutated bee (\(X_{mutatedOB}\)) obtains higher or equal value of MOFitness than \(X_j\). In that case, we store \(X_{mutatedOB}\) in the colony; otherwise, we copy the selected bee (\(X_j\)) to the colony and we discard the mutated one.

Table 1 Specifications of data sets for the real-world optical network topologies NTT and COST239
Full size table

In the last step, we add to the colony \(NS\) random bees to enhance the exploration of the search space and avoid stagnation of the algorithm; we will refer to them as scout bees (lines 30–34). After that, we sort the bees of the colony in terms of quality (using the value of MOFitness) with the aim of using the best bees as employed bees in the next generation (line 36). Finally, we update the Pareto front (line 37).

5 Experimental results

In this section, we present a comparison among our proposal MO-ABC and several approaches published in the literature. In the first place, we present all methodological issues followed for carrying out the experiments. In the second place, we compare the MO-ABC algorithm with other multiobjective approaches. Finally, we study the goodness of MO-ABC by comparing its results with those obtained by other heuristics and metaheuristics published by other authors.

5.1 Methodological issues

In this subsection, we show the methodology followed to make the comparisons.

We performed all experiments in a Pentium IV (2.8 GHz) computer with 1GB of RAM. Furthermore, the source codes of the approaches were compiled using gcc compiler with no optimization options.

In our experiments, we used two real-world optical network topologies. In the first place, we present the major Japanese backbone, the Nippon Telegraph and Telephone (NTT, Japan); it consists of 55 optical nodes and 144 links. The second one corresponds to the Pan European Optical Network (COST239, Europe); it consists of 11 nodes and 52 links. The physical topologies of both networks are shown in Table 1.

For each topology, we have six different data sets (Table 1). The corresponding data sets of NTT were taken from Schaerer and Barán (2003). In case of COST239 topology, we used a gravity demand model (Leung and Grover 2005) to generate data sets with a high number of demands (from 100 to 600).

$$\begin{aligned} {\rm demands}(a,b) = \left[\frac{{\rm deg}(a) * {\rm deg}(b)}{d(a,b)}*{\rm constant} \right]\end{aligned}$$
(4)

According to Eq. 4, the total number of demands between two nodes a and b is proportional to the product of the degrees of the nodes, and inversely proportional to the Euclidean distance between them. We also used a constant value to generate different data sets; in Table 1, we present the value of constant in Eq. 4 for each data set of COST239.

For each MOEA, we carried out 30 runs, and a Pareto front was obtained in each independent run as a result. The stop criterion considered in this work is based on runtime (the corresponding runtime of each data set is presented in Table 1). In order to measure the quality of these Pareto fronts produced in each run, we applied two well-known multiobjective metrics: Hypervolume (Auger et al. 2009) and Set Coverage (Zitzler et al. 2003).

On the one hand, the Hypervolume metrics evaluates the volume (in objective function space) covered by members of a non-dominated set of solutions (Pareto front). To calculate the hypervolume, the usage of two reference points is required: \(r_{\min}(x_{\min},y_{\min})\) and \(r_{\max} (x_{\max}, y_{\max})\), where x is the number of hops (\(y_1\)) and y is the number of wavelength switchings (\(y_2\)). In Table 1, we show the reference points used for each data set. The \(r_{\max}\) point for every data set was calculated from experience.

On the other hand, the Set Coverage measures the fraction of non-dominated solutions obtained by an algorithm B which are covered by the non-dominated solutions evolved by an algorithm A.

Since MOEAs are stochastic, in this work we performed a statistical analysis to ensure a certain level of confidence. We start making a test for checking whether the values of the data follow a Gaussian distribution or not; in this work, we applied the Kolmogorov–Smirnov test to check it. If this test for calculating residual normality is not satisfactory, then we perform a non-parametric test, such as Kruskal–Wallis. In case it is satisfactory, we verify the homogeneity of the variances using the Levene test, to finally apply the ANOVA test (parametric test); otherwise, if the variances are not homogeneous, we apply the non-parametric Kruskal–Wallis test. The confidence level adopted in this paper is always 95 % in each statistical test (a significance level of 5 % or p = 0.05).

5.2 Comparison with other MOEAs

In this subsection, we present a comparison among our swarm proposal (MO-ABC) and three multiobjective approaches: differential evolution with Pareto tournaments (DEPT) (Rubio-Largo et al. 2010), multiobjective variable neighborhood search (MO-VNS) (Rubio-Largo et al. 2010), and the well-known fast non-dominated sorting genetic algorithm (NSGA-II) (Deb et al. 2002). In Table 2, we present the best configuration found for each metaheuristics for the RWA problem.

Table 2 Best configuration found for each metaheuristics for the RWA problem
Full size table
Table 3 Comparison among DEPT, MO-VNS, NSGA-II, and MO-ABC using average Hypervolume of 30 runs
Full size table
Fig. 4
figure 4

Illustrative comparison among DEPT, MO-VNS, NSGA-II, and MO-ABC using Hypervolume metrics. a NTT topology, b COST239 topology

Full size image
Fig. 5
figure 5

Non-dominated solutions obtained by the metaheuristics in N6(a) and C6(b). a Data set N6, b Data set C6

Full size image

In the first place, we start comparing the metaheuristics using the Hypervolume metrics. In this work, we performed a statistical analysis by pairs of MOEAs. In this way, we were to say whether the differences in hypervolume between them were statistically significant. For each pair of MOEAs, we performed the statistical analysis described in Sect. 5.1. However, in all cases, we have to apply the Kruskal–Wallis non-parametric statistical test because the variances were not homogeneous.

On the one hand, we focus on studying the performance of the metaheuristics when tackling the NTT topology. As we can see in Table 3, the MO-ABC algorithm obtains identical values of hypervolume in data sets N1 and N2, which are the easiest ones (they consist of 10 demands). In the rest of the NTT data sets, MO-ABC obtains higher values of hypervolume than any other approach. Furthermore, we highlight the fact that, for this specific network topology, the average hypervolume of MO-ABC is 69.15 %; whereas DEPT, MO-VNS, and NSGA-II obtain an average below 68 %. In Fig. 4a, we present an illustrative view of these results. As we can observe, MO-ABC clearly overcomes the values of hypervolume achieved by the rest of metaheuristics in almost all data sets of NTT. After performing a statistical analysis, we conclude that there is no statistically significant differences among the metaheuristics in the easiest data sets (N1 and N2), and also between MO-VNS and NSGA-II in N3 and N6. In the rest of data sets, all differences were statistically significant (see Table 4).

On the other hand, we continue using the Pan European Optical Network (COST239) to ensure the proper goodness of MO-ABC when tackling a high number of requests (100–600 demands) in an optical network. In Table 3, we can notice that our swarm proposal obtains higher quality results in all data sets than DEPT, MO-VNS, and NSGA-II. At this point, we can highlight that there exists more than 3 % difference of mean hypervolume, among MO-ABC and the other three metaheuristics. As we may observe in Table 4, the statistical analysis showed that the differences found were statistically significant in almost all data sets, except on data set C1 (MO-VNS and NSGA-II). Finally, Fig. 4b shows a graphical representation of this comparison.

After comparing the metaheuristics using the hypervolume indicator, we are able to say that MO-ABC obtains non-dominated solutions with higher quality than those generated by DEPT, MO-VNS, and NSGA-II. In Fig. 5, we present a visual comparison among the Pareto fronts obtained by the algorithms when dealing with data sets N6 and C6 to demonstrate it. To create the plot, we used the Pareto front that has a value of hypervolume closer to the mean hypervolume obtained in the 30 runs by each algorithm (see Table 3).

Table 4 Kruskal–Wallis tests
Full size table

The next step is performing a comparison among the multiobjective approaches using the Set Coverage indicator.

We start analyzing the Japanese optical topology, NTT. As we can see in Table 5, in all NTT data sets, the Pareto front obtained by MO-ABC covers 100 % of the non-dominated solutions obtained by all the other approaches. In data sets N1 and N2, all algorithms are able to obtain the same coverage relation, SC(A, B) = 100 %. This is due to all non-dominated solutions of the set achieved by B being dominated by or equal to the non-dominated solutions obtained by A. If we focus on the average coverage relation, we can notice that the non-dominated sets of DEPT, MO-VNS, and NSGA-II only cover a mean of 33.33, 38.89, and 33.33 %, respectively, of the Pareto front obtained by MO-ABC.

We continue comparing the MOEAs using the European topology COST239. On the one hand, DEPT, MO-VNS, and NSGA-II are able to cover only a mean of 11.67, 10.83, and 25 % of the non-dominated solutions achieved by MO-ABC. On the other hand, the set of non-dominated solutions of MO-ABC covers a mean of 77.62, 75, and 66.67 % of DEPT, MO-VNS, and NSGA-II, respectively.

To sum up, we can conclude that the MO-ABC obtains very promising results, because it performs better than other multiobjective metaheuristics published in the literature (DEPT and MO-VNS), as well as overcoming the results of a well-known MOEA (NSGA-II). In a global view, the MO-ABC algorithm seems to be a very propitious approach for solving the static routing and wavelength assignment problem.

5.3 Comparison with other authors

As we mentioned in Sect. 2, other authors have also tackled the static RWA problem. The aim of this subsection is to ensure the goodness of the MO-ABC algorithm with several comparisons with other approaches published in the literature. In Table 6, we present the different heuristics (typical in telecommunication field) and the MOACOs algorithms proposed in Arteta et al. (2007) and Insfrán et al. (2006).

Table 5 Comparison among the algorithms DEPT, MO-VNS, NSGA-II, and MO-ABC using the Set Coverage (\(A \succeq B\))
Full size table

In order to make these comparisons, we have used the same methodology as we used in previous subsections. Unfortunately, in Arteta et al. (2007) and Insfrán et al. (2006), the authors present only results for the following data sets: N1, N3, N4, and N6. Furthermore, for each data set, they suggest which is the typical heuristics and MOACO that obtain better results, therefore, we will compare the MO-ABC algorithm with the best typical heuristics and variety of MOACO.

Table 6 Typical heuristics in telecommunication field and several varieties of MOACOs proposed in Arteta et al. (2007) and Insfrán et al. (2006)
Full size table
Fig. 6
figure 6

Non-dominated solutions obtained by the approaches in N6

Full size image

In the first place, we start the comparison using the Hypervolume indicator. As we can see in Table 7, the MO-ABC obtains higher values of hypervolume than the best typical heuristics and MOACO for almost all data sets. In the easy data set N1, we notice that the suggested typical heuristics and MOACOs obtain the same value of hypervolume than MO-ABC. In Fig. 6, we see that in data set N6, the Pareto front achieved by MO-ABC clearly dominates the fronts obtained by the best approaches suggested in Arteta et al. (2007) and Insfrán et al. (2006).

Table 7 Comparison among the best approaches suggested in Arteta et al. (2007) and Insfrán et al. (2006), and MO-ABC (Hypervolume metrics)
Full size table
Table 8 Comparison among the best approaches suggested in Arteta et al. (2007) and Insfrán et al. (2006), and MO-ABC (Set Coverage metrics, \(A \succeq B\))
Full size table

Secondly, we present a direct comparison of the results achieved by the algorithms presented above using the second multiobjective metrics (Set Coverage). In this case, we discard the data set N1, because all approaches have obtained the same Pareto front. In Table 8, we notice that in data sets N4 and N6, the Pareto front obtained by MO-ABC dominates both fronts of the best MOACOs and best typical heuristics. As for N3, on the one hand, MO-ABC presents better coverage relation than the best MOACOs (MAS and MOA). On the other hand, the non-dominated solutions provided by 3SPLU are not able to dominate the non-dominated solutions obtained by MO-ABC and vice versa.

To sum up, after performing a comparison with diverse typical heuristics in the telecommunication field, and varieties of MOACOs proposed in Arteta et al. (2007) and Insfrán et al. (2006), we conclude that the MO-ABC algorithm obtains promising results. Since MO-ABC obtains non-dominated solutions with higher quality than the best approaches suggested in Arteta et al. (2007) and Insfrán et al. (2006), we are able to say that it performs better than 16 different approaches.

6 Conclusions and future work

In this work, we have proposed the usage of a new multiobjective approach of the artificial bee colony (ABC) algorithm (MO-ABC) for solving the static routing and wavelength assignment (RWA) problem in WDM networks. To ensure the effectiveness of our proposal, we have made several comparisons with diverse algorithms published in the literature. To make these comparisons, we used two real-world network topologies: the Nippon Telegraph and Telephone network (NTT, Japan) and the Pan European Optical Network (COST239); and six data sets per topology, therefore a total of 12 data sets. Furthermore, to decide which of the algorithms performs better, we used two well-known metrics in the multiobjective field: Hypervolume and Coverage Relation. After making all these comparisons, we conclude that the MO-ABC algorithm overcomes the results obtained by almost 20 different approaches (DEPT, MO-VNS, NSGA-II, and 16 methods proposed in Arteta et al. (2007) and Insfrán et al. (2006).

As future work, we intend to apply other multiobjective versions of Swarm Intelligence algorithms for the static RWA problem with the aim of comparing with the results achieved by MO-ABC. Another possible research line is to apply this MOEA to tackle other telecommunication problems, such as traffic grooming problem.