Nothing Special   »   [go: up one dir, main page]
Skip to main content

Advertisement

SpringerLink
Log in

A multi-population hybrid biased random key genetic algorithm for hop-constrained trees in nonlinear cost flow networks

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

Genetic algorithms and other evolutionary algorithms have been successfully applied to solve constrained minimum spanning tree problems in a variety of communication network design problems. In this paper, we enlarge the application of these types of algorithms by presenting a multi-population hybrid genetic algorithm to another communication design problem. This new problem is modeled through a hop-constrained minimum spanning tree also exhibiting the characteristic of flows. All nodes, except for the root node, have a nonnegative flow requirement. In addition to the fixed charge costs, nonlinear flow dependent costs are also considered. This problem is an extension of the well know NP-hard hop-constrained Minimum Spanning Tree problem and we have termed it hop-constrained minimum cost flow spanning tree problem. The efficiency and effectiveness of the proposed method can be seen from the computational results reported.

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

Access this article

Log in via an institution

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.

Institutional subscriptions

Similar content being viewed by others

References

  1. Ahuja R., Orlin J.: Multi-exchange neighborhood structures for the capacitated minimum spanning tree problem. Math. Program. 91, 71–97 (2001)

    MathSciNet  MATH  Google Scholar 

  2. Beasley J.E.: Or-library: distributing test problems by electronic mail. J. Oper. Res. Soc. 41, 1069–1072 (1990)

    Google Scholar 

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

    Article  Google Scholar 

  4. Cormen T.H., Leiserson C.E., Rivest R.L., Stein C.: Introduction to algorithms. MIT press, Cambridge (2001)

    MATH  Google Scholar 

  5. Dahl G., Gouveia L., Requejo C.: On formulations and methods for the hop-constrained minimum spanning tree problem. In: Pardalos, P.M., Resende, M. (eds) Handbooks of Telecommunications, pp. 493–515. Springer, Berlin (2006)

    Chapter  Google Scholar 

  6. Deering S.E., Cheriton D.R.: Multicast routing in datagram internetworks and extended lans. ACM Trans. Comput. Syst. 8, 85–110 (1990)

    Article  Google Scholar 

  7. Deering, S.E., Esrtrin, D., Farinacci, D.: An architecture for wide-area multicast routing. Proceedings of SIGCOMM (1994)

  8. Fontes D.B.M.M.: Optimal hop-constrained trees for nonlinear cost flow networks. INFOR 48, 13–22 (2010)

    MathSciNet  Google Scholar 

  9. Fontes D.B.M.M., Gonçalves J.F.: Heuristic solutions for general concave minimum cost network flow problems. Networks 50, 67–76 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  10. Fontes D.B.M.M., Hadjiconstantinou E., Christofides N.: Upper bounds for single source uncapacitated minimum concave-cost network flow problems. Networks 41, 221–228 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  11. Fontes D.B.M.M., Hadjiconstantinou E., Christofides N.: A branch-and-bound algorithm for concave network flow problems. J. Global Optim. 34, 127–155 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  12. Fontes D.B.M.M., Hadjiconstantinou E., Christofides N.: A dynamic programming approach for solving single-source uncapacitated concave minimum cost network flow problems. Eur. J. Oper. Res. 174, 1205–1219 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  13. Fontes, D.B.M.M., Gonçalves, J.F.: Upper bounds for single source uncapacitated concave minimum cost network flow problems. Proceedings of INOC—International Network Optimization Conference (2009)

  14. Gallo G., Sodini C.: Adjacent extreme flows and application to min concave cost flow problems. Networks 9, 95–121 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  15. Gen M., Cheng R., Oren S.: Network design techniques using adapted genetic algorithms. Adv. Eng. Softw. 32, 731–744 (2001)

    Article  MATH  Google Scholar 

  16. Gen M., Kumar A., Kim R.: Recent network design techniques using evolutionary algorithms. Int. J. Prod. Econ. 98, 251–261 (2005)

    Article  Google Scholar 

  17. Gonçalves J.F., Mendes J.J.M., Resende M.: A genetic algorithm for the resource constrained multi-project scheduling problem. Eur. J. Oper. Res. 189, 1171–1190 (2009)

    Article  Google Scholar 

  18. Gonçalves J., Resende M.: A parallel multi-population genetic algorithm for a constrained two-dimensional orthogonal packing problem. J. Comb. Optim. 22, 1–22 (2010)

    Google Scholar 

  19. Gonçalves J., Resende M., Mendes J.: A biased random-key genetic algorithm with forward-backward improvement for the resource constrained project scheduling problem. J. Heuristics 17, 1–20 (2010)

    Google Scholar 

  20. Gonçalves J., Sousa P.: A genetic algorithm for lot sizing and scheduling under capacity constraints and allowing backorders. Int. J. Prod. Res. 49(9), 2683–2703 (2011)

    Article  Google Scholar 

  21. Gonçalves J.: A hybrid genetic algorithm-heuristic for a two-dimensional orthogonal packing problem. Eur. J. Oper. Res. 183(3), 1212–1229 (2007)

    Article  MATH  Google Scholar 

  22. Gonçalves J., Almeida J.: A hybrid genetic algorithm for assembly line balancing. J. Heuristics 8, 629–642 (2002)

    Article  Google Scholar 

  23. Gonçalves J., Mendes J., Resende M.: A hybrid genetic algorithm for the job shop scheduling problem. Eur. J. Oper. Res. 167(1), 77–95 (2005)

    Article  MATH  Google Scholar 

  24. Gonçalves J., Resende M.: An evolutionary algorithm for manufacturing cell formation. Comput. Ind. Eng. 47, 247–273 (2004)

    Article  Google Scholar 

  25. Gonçalves J., Resende M.: Biased random-key genetic algorithms for combinatorial optimization. J. Heuristics 17, 487–525 (2010)

    Article  Google Scholar 

  26. Gonçalves J., Resende M.: A parallel multi-population biased randomkey genetic algorithm for a container loading problem. Comput. Oper. Res. 39, 179–190 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  27. Gouveia L.: Using the Miller–Tucker–Zemlin constraints to formulate a minimal spanning tree problem with hop constraints. Comput. Oper. Res. 22, 959–970 (1995)

    Article  MATH  Google Scholar 

  28. Gouveia L.: Multicommodity flow models for spanning trees with hop constraints. Eur. J. Oper. Res. 91, 178–190 (1996)

    Article  Google Scholar 

  29. Gouveia L., Martins P.: The capacitated minimum spanning tree problem: revisiting hop-indexed formulations. Comput. Oper. Res. 32, 2435–2452 (2005)

    Article  MATH  Google Scholar 

  30. Gouveia L., Requejo C.: A new lagrangean relaxation approach for the hop-constrained minimum spanning tree problem. Eur. J. Oper. Res. 132, 539–552 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  31. Han, L., Wang, Y., Guo, F.: A new genetic algorithm for the degree-constrained minimum spanning tree problem. IEEE International Workshop on VLSI Design and Video Technology, pp. 125–128 (2005)

  32. Holland J.: Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor (1975)

    Google Scholar 

  33. Kawatra R.: A hop constrained min-sum arborescence with outage costs. Comput. Oper. Res. 34, 2648–2656 (2007)

    Article  MATH  Google Scholar 

  34. Kompella V., Pasquale J., Polyzos G.: Multicast routing for multimedia communication. IEEE/ACM Trans. Netw. 1, 286–292 (1993)

    Article  Google Scholar 

  35. Lacerda E., Medeiros M.: A genetic algorithm for the capacitated minimum spanning tree problem. IEEE Congr. Evol. Comput. 1(6), 725–729 (2006)

    Google Scholar 

  36. LeBlanc, L., Reddoch, R.: Reliable link topology/capacity design and routing in backbone telecommunication networks. First ORSA telecommunications SIG conference (1990)

  37. Lee Y., Atiquzzaman M.: Least cost heuristic for the delay constrained capacitated minimum spanning tree problem. Comput. Commun. 28, 1371–1379 (2005)

    Article  Google Scholar 

  38. Lelarge M.: Packet reordering in networks with heavy-tailed delays. Math. Methods Oper. Res. 67, 341–371 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  39. Montemanni R., Gambardella L.: A benders decomposition approach for the robust spanning tree problem with interval data. Eur. J. Oper. Res. 161, 771–779 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  40. Nahapetyan A., Pardalos P.: Adaptive dynamic cost updating procedure for solving fixed charge network flow problems. Comput. Optim. Appl. 39, 37–50 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  41. Park S.K., Miller K.W.: Random number generators: good ones are hard to find. Commun. ACM 31, 1192–1201 (1998)

    Article  MathSciNet  Google Scholar 

  42. Raidl G., Julstrom B.: Edge sets: an effective evolutionary coding of spanning trees. IEEE Trans. Evol. Comput. 7, 225–239 (2003)

    Article  Google Scholar 

  43. Rebennack S., Nahapetyan A., Pardalos P.M.: Bilinear modeling solution approach for fixed charge network flow problems. Optim. Lett. 3, 347–355 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  44. Thompson E., Paulden T., Smith D.: The dandelion code: a new coding of spanning trees for genetic algorithms. IEEE Trans. Evol. Comput. 11, 91–100 (2007)

    Article  Google Scholar 

  45. Woolston K., Albin S.: The design of centralized networks with reliability and availability constraints. Comput. Oper. Res. 15, 207–217 (1988)

    Article  Google Scholar 

  46. Zeng, Y., Wang, Y.: A new genetic algorithm with local search method for degree-constrained minimum spanning tree problems. ICCIMA—5th International Conference on Computational Intelligence and Multimedia Applications, pp. 218–222 (September 2003)

Download references

Author information

Authors and Affiliations

  1. Faculdade de Economia da Universidade do Porto and LIAAD-INESC Porto L.A, Rua Dr. Roberto Frias, 4200-464, Porto, Portugal

    Dalila B. M. M. Fontes & José Fernando Gonçalves

Authors
  1. Dalila B. M. M. Fontes
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. José Fernando Gonçalves
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Dalila B. M. M. Fontes.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Fontes, D.B.M.M., Gonçalves, J.F. A multi-population hybrid biased random key genetic algorithm for hop-constrained trees in nonlinear cost flow networks. Optim Lett 7, 1303–1324 (2013). https://doi.org/10.1007/s11590-012-0505-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-012-0505-5

Keywords

Search

Navigation