Evolutionary Algorithms for Multicast Network Routing

Network Coding based Multicast Network Routing

In network coding, each intermediate node in the network is allowed, if necessary, to recombine data packets received from different incoming links. By doing so, a maximized multicast throughput can always be achieved.

Due to the necessary coding operations, network coding incurs additional cost such as computational overhead or transmission delay. It is thus important that the amount of coding operations is minimized while the benefits of network coding are warranted. However, such problem is NP-hard.


  1. H. Xing, S. Li, Y. Cui, L. Yan, W. Pan, R. Qu, "A Hybrid EDA for Load Balancing in Multicast with Network Coding", Applied Soft Computing, 59: 363-377, 2017
  2. H. Xing, Z. Wang, T. Li, H. Li, R. Qu, "An Improved MOEA/D Algorithm for Multi-objective Multicast Routing with Network Coding", Applied Soft Computing, 59: 88-103, 2017
  3. H. Xing, Y. Xu, R. Qu, and L. Xu, "A PBIL for Load Balancing in Network Coding Based Multicasting", The 17th International Conference on Computational Science and Its Applications (ICCSA 2016), Part II, LNCS 9787, pp. 34-44, 2016
  4. Xing H, Qu R, Xu L, and Qu Z. "A quantum inspired evolutionary algorithm for dynamic multicast routing with network coding", In Proc. 16th IEEE International Symposium on Communications and Information Technologies (ISCIT 2016), Qingdao, China, 2016
  5. Z. Wang, H. Xing, T. Li, Y. Yang, R. Qu, "An Improved MOEA/D for QoS Oriented Multimedia Multicasting with Network Coding", 8th International Conference on Mobile Multimedia Communications (MOBIMEDIA 2015), May 25-27, 2015 Chengdu, China
  6. H. Xing R. Qu, L. Bai, Y. Ji, "On Minimizing Coding Operations in Network Coding Based Multicast: An Evolutionary Algorithm", Applied Intelligence, 41(3): 820-836, 2014
  7. H. Xing, R. Qu, "A Nondominated Sorting Genetic Algorithm for Bi-objective Network Coding Based Multicast Routing Problems". Information Sciences. 233: 36-53, 2013

Multicast Network Routing

Multimedia applications such as video/audio conferencing and distance education demand multicast communications, where data streams are sent from the source node to a set of destinations within the same multicast group in computer networks. The objective is to maximize the multicast throughput within limited and constrained resources. The quality of service (QoS) requirements in the underlying computer network take into account several attributes such as cost, delay, delay variation, packet losses and hop count.



  1. R. Qu, Y. Xu, J. Castro, D. Landa-Silva. "Particle Swarm Optimization for the Steiner Tree in Graph and Delay-Constrained Multicast Routing Problems." Journal of Heuristics, 19(2): 317-342, 2013.
  2. Y. Xu, R. Qu, R. Li. A Simulated Annealing based Genetic Local Search Algorithm for Multi-objective Multicast Routing Problems, Annals of Operations Research, 260: 527-555, 2013
  3. Y. Xu and R. Qu, "An Iterative Local Search Approach based on Fitness Landscapes Analysis for the Delay-constrained Multicast Routing Problem", Computer Communications, 35: 352-365, 2012
  4. Y. Xu and R. Qu, "A Hybrid Scatter Search Meta-heuristic for Delay-constrained Multicast Routing Problems", Applied intelligence, 36(1): 229-241, 2012
  5. Y. Xu and R. Qu, "Solving Multi-objective Multicast Routing Problems by Evolutionary Multi-objective Simulated Annealing Algorithms with Variable Neighborhoods", Journal of Operational Research Society, 62: 313-325, 2010
  6. Y. Xu and R. Qu, "A GRASP approach for the delay-constrained multicast routing problem", The 4th Multidisciplinary International Scheduling: Theory and Applications 2009 (MISTA 2009), pp. 93-104, 10-12 August 2009, Dublin, Ireland.
  7. R. Qu, Y. Xu, G. Kendall, "A Variable Descent Search Algorithm for Delay-Constrained Least-Cost Multicast Routing", Lecture Notes in Computer Science 5851, pp. 15-29, Learning and Intelligent OptimizatioN (LION 3), Trento, Italy, Jan 14-18, 2009

Other Resources

This page includes resources from the research at School of Computer Science, University of Nottingham addressing the Multicast Network Routing using evolutionary algorithms.

Research sponsored by:

  • China Scholarship Council
  • School of Computer Science, University of Nottingham
Last updated: 18 September 2018Maintained by Rong Qu, School of Computer Science, University of Nottingham, UK