iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/s10732-009-9115-5
Two-level evolutionary approach to the survivable mesh-based transport network topological design | Journal of Heuristics Skip to main content
Log in

Two-level evolutionary approach to the survivable mesh-based transport network topological design

  • Published:
Journal of Heuristics Aims and scope Submit manuscript

Abstract

The complete topology design problem of survivable mesh-based transport networks is to address simultaneously design of network topology, working path routing, and spare capacity allocation based on span-restoration. Each constituent problem in the complete design problem could be formulated as an Integer Programming (IP) and is proved to be \(\mathcal{NP}\) -hard. Due to a large amount of decision variables and constraints involved in the IP formulation, to solve the problem directly by exact algorithms (e.g. branch-and-bound) would be impractical if not impossible. In this paper, we present a two-level evolutionary approach to address the complete topology design problem. In the low-level, two parameterized greedy heuristics are developed to jointly construct feasible solutions (i.e., closed graph topologies satisfying all the mesh-based network survivable constraints) of the complete problem. Unlike existing “zoom-in”-based heuristics in which subsets of the constraints are considered, the proposed heuristics take all constraints into account. An estimation of distribution algorithm works on the top of the heuristics to tune the control parameters. As a result, optimal solution to the considered problem is more likely to be constructed from the heuristics with the optimal control parameters. The proposed algorithm is evaluated experimentally in comparison with the latest heuristics based on the IP software CPLEX, and the “zoom-in”-based approach on 28 test networks problems. The experimental results demonstrate that the proposed algorithm is more effective in finding high-quality topologies than the IP-based heuristic algorithm in 21 out of 28 test instances with much less computational costs, and performs significantly better than the “zoom-in”-based approach in 19 instances with the same computational costs.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • Al-Rumaih, A., Tipper, D., Liu, Y., Norman, B.A.: Spare capacity planning for survivable mesh networks. In: Proceedings of the IFIP-TC6 / European Commission International Conference on Broadband Communications, High Performance Networking, and Performance of Communication Networks. Lecture Notes in Computer Science, pp. 957–968. Springer, Berlin (2000)

    Google Scholar 

  • Álvarez, A.M., Gonzälez, J.L., De-Alba, K.: Scatter search for a network design problem. Technical Report PISIS-2003-02, Universidad Autónoma de Nuevo León, Facultad de Ingeniería Mecánica y Eléctrica, División de Posgrado en Ingeniería de Sistemas, Mexico (2003)

  • Anticona, M.T., Villegas, C.E.: Design of ant colony-based ant route for solve the OSPF problem. CERMA, pp. 386–394 (2007)

  • Baluja, S.: Population-based incremental learning: a method for integrating genetic search based function optimization and competitive learning. Technical Report, Carnegie Mellon University (1994)

  • Buriol, L.S., Resende, M.C.G., Thorup, M.: Survivable IP network design with OSPF routing. Networks 49(1), 51–64 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  • Boorstyn, R., Frank, H.: Large-scale network topological optimization. IEEE Trans. Commun. COM-25 1, 29–47 (1977)

    Article  Google Scholar 

  • Cancela, H., Robledo, F., Rubino, G.: A GRASP algorithm with tree based local search for designing a survivable Wide area network backbone. J. Comput. Sci. Technol. 4(1), 52–58 (2004)

    Google Scholar 

  • Chou, W., Gerla, M., Frank, H., Eckl, J.: A cut saturation algorithm for topological design of packet switched networks. In: Proc. IEEE National Telcom. Conf., pp. 1074–1085 (1974)

  • Cinkler, T., Henk, T., Gordos, G.: Stochastic algorithms for thrifty single-failure-protected networks. In: Proceedings of Design of Reliable Communication Networks, Munich, Germany, pp. 299–303 (2000)

  • Cook, W.J., Cunningham, W.H., Pulleyblank, W.R., Schrijver, A.: Combinatorial Optimization. Wiley, New York (1998)

    MATH  Google Scholar 

  • Corne, D., Dorigo, M., Glover, F. (eds.): New Ideas in Optimization. McGraw–Hill, New York (1999)

    Google Scholar 

  • Dorigo, M., Maniezzo, V., Colorni, A.: The ant system: optimization by a colony of cooperating agents. IEEE Trans. Syst. Man Cybern., Part B 26(1), 29–41 (1996)

    Article  Google Scholar 

  • Faria, Jr.H., Binato, S., Resende, M.G.C., Falcao, D.M.: Power transmission network design by greedy randomized adaptive path relinking. IEEE Trans. Power Syst. (2004)

  • Ferentinos, K.P., Tsiligindis, T.A.: A memetic algorithm for dynamic design of wireless sensor network. CEC 2007, pp. 2774–2781

  • Gavish, B.: Topological design of computer communication networks—the overall design problem. Eur. J. Oper. Res. 58, 149–172 (1992)

    Article  MATH  Google Scholar 

  • Gil, C., Banos, R., Montoya, M.G., Gomez, J.: Performance of simulated annealing, tabu search and evolutionary algorithms for multi-objective network partitioning. 1, 55–64 (2006)

  • Glover, F., Laguna, M.: Tabu Search. Kluwer Academic, Dordrecht (1998)

    Google Scholar 

  • Glover, F., Laguna, M., Marti, R.: Fundamentals of scatter search and path relinking. Control Cybern. 39(3), 653–684 (2000)

    MathSciNet  Google Scholar 

  • Grover, W.D., Doucette, J.: Topological design of survivable mesh-based transport networks. Ann. Oper. Res. 106, 79–125 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  • Hsu, C.-Y., Wu, J., Wang, S., Hong, C.: Survivable and delay-guaranteed backbone wireless mesh network design. J. Parallel Distrib. Comput. 68, 306–320 (2008)

    Article  Google Scholar 

  • Jan, R.H.: Design of reliable networks. Comput. Oper. Res. 20(1), 25–34 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  • Kershenbaum, A.: Telecommunications Network Design Algorithms. McGraw–Hill, New York (1993)

    Google Scholar 

  • Kershenbaum, A., Kermani, P., Grover, G.A.: MENTOR: An algorithm for mesh network topological optimization and routing. IEEE Trans. Commun. 39(3), 503–513 (1991)

    Article  Google Scholar 

  • Larrañaga, P., Lozano, J.A.: Estimation of Distribution Algorithms: a New Tool for Evolutionary Computation. Kluwer Academic, Dordrecht (2002)

    MATH  Google Scholar 

  • Mukherjee, B.: WDM optical communication networks: progress and challenges. IEEE J. Sel. Areas Commun. 18(10), 1810–1824 (2000)

    Article  Google Scholar 

  • Ooubutra, M., Avemprayoon, P., Wnrdkein, P.: Topological communication network design using ant colony optimization. In: Proceedings of the 7th Conference on Advanced Communication Technology, vol. 2, pp. 1147–1151 (2005)

  • Pickavet, M., Demeester, P.: A zoom-in approach to design SDH mesh-restorable networks. J. Heur. 6(1), 103–126 (2000)

    Article  Google Scholar 

  • Pierre, S., Elgibaoui, A.: A tabu-search approach for designing computer-network topologies with unreliable components. IEEE Trans. Reliab. 46(3), 350–359 (1997)

    Article  Google Scholar 

  • Randall, M., McMahon, G., Sugden, S.: A simulated annealing approach to communication network design. J. Comb. Optim. 6, 55–65 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  • Runggeratigul, S.: A memetic algorithm for communication network design taking into consideration an existing network. Appl. Optim. 615–626 (2004)

  • Sakauchi, H., Nishimura, Y., Hasegawa, S.: A self-healing network with an economical spare-channel assignment. In: Proc. IEEE Globecom, pp. 438–444 (1990)

  • Shen, J., Xu, F., Zheng, P.: A tabu search algorithm for the routing and capacity assignment problem in computer network. 32(11), 2785–2800 (2005)

  • Taheri, J., Zomaya, A.Y.: A simulated annealing approach for mobile location management. 30(4), 714–730 (2007)

  • Wille, E.C.G., Mellia, M., Leonardi, E., Marsan, M.A.: Topological design of survivable IP networks using meta-heuristic approaches. In: The 3rd International Workshop on QoS in Multiservice IP Networks (2005)

  • Zhang, Q., Sun, J., Xiao, G., Tsang, E.: Evolutionary algorithm refining a heuristic: a hybrid method for shared path protection in WDM networks under SRLG constraints. IEEE Trans. Syst. Man Cybern., Part B 37(1), 51–61 (2007)

    Article  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to J. Sun.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Sun, J., Zhang, Q. & Li, J. Two-level evolutionary approach to the survivable mesh-based transport network topological design. J Heuristics 16, 723–744 (2010). https://doi.org/10.1007/s10732-009-9115-5

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10732-009-9115-5

Keywords

Navigation