Skip to main content
SpringerLink
Log in

Variable neighbourhood search for the minimum labelling Steiner tree problem

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

We present a study on heuristic solution approaches to the minimum labelling Steiner tree problem, an NP-hard graph problem related to the minimum labelling spanning tree problem. Given an undirected labelled connected graph, the aim is to find a spanning tree covering a given subset of nodes of the graph, whose edges have the smallest number of distinct labels. Such a model may be used to represent many real world problems in telecommunications and multimodal transportation networks. Several metaheuristics are proposed and evaluated. The approaches are compared to the widely adopted Pilot Method and it is shown that the Variable Neighbourhood Search that we propose is the most effective metaheuristic for the problem, obtaining high quality solutions in short computational running times.

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

Access this article

Log in via an institution

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

  • Aarts, E., Korst, J., & Michiels, W. (2005). Simulated annealing. In E. K. Burke & G. Kendall (Eds.), Search methodologies: introductory tutorials in optimization and decision support techniques (pp. 187–210). Berlin: Springer.

    Google Scholar 

  • Avis, D., Hertz, A., & Marcotte, O. (2005). Graph theory and combinatorial optimization. New York: Springer.

    Book  Google Scholar 

  • Blum, C., & Roli, A. (2003). Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys, 35(3), 268–308.

    Article  Google Scholar 

  • Cerulli, R., Fink, A., Gentili, M., & Voß, S. (2005). Metaheuristics comparison for the minimum labelling spanning tree problem. In B. L. Golden, S. Raghavan, & E. A. Wasil (Eds.), The next wave on computing, optimization, and decision technologies (pp. 93–106). New York: Springer.

    Chapter  Google Scholar 

  • Cerulli, R., Fink, A., Gentili, M., & Voß, S. (2006). Extensions of the minimum labelling spanning tree problem. Journal of Telecommunications and Information Technology, 4, 39–45.

    Google Scholar 

  • Chang, R. S., & Leu, S. J. (1997). The minimum labelling spanning trees. Information Processing Letters, 63(5), 277–282.

    Article  Google Scholar 

  • Consoli, S. (2007). Test datasets for the minimum labelling Steiner tree problem. [Online], available at http://people.brunel.ac.uk/~mapgssc/MLSteiner.htm.

  • Consoli, S., Darby-Dowman, K., Mladenović, N., & Moreno-Pérez, J. A. (2008a). Greedy randomized adaptive search and variable neighbourhood search for the minimum labelling spanning tree problem. European Journal of Operational Research. doi:10.1016/j.ejor.2008.03.014.

    Google Scholar 

  • Consoli, S., Darby-Dowman, K., Mladenović, N., & Moreno-Pérez, J. A. (2008b). Heuristics based on greedy randomized adaptive search and variable neighbourhood search for the minimum labelling spanning tree problem. Technical Report TR/01/07, Brunel University, West London, UK. Available: http://hdl.handle.net/2438/737.

  • Demśar, J. (2006). Statistical comparison of classifiers over multiple data sets. Journal of Machine Learning Research, 7, 1–30.

    Google Scholar 

  • Duin, C., & Voß, S. (1999). The Pilot method: A strategy for heuristic repetition with applications to the Steiner problem in graphs. Networks, 34(3), 181–191.

    Article  Google Scholar 

  • Feo, T. A., & Resende, M. G. C. (1989). A probabilistic heuristic for a computationally difficult set covering problem. Operations Research Letters, 8, 67–71.

    Article  Google Scholar 

  • Francis, R. L., McGinnis, L. F., & White, J. A. (1992). Facility layout and location: an analytical approach. Englewood Cliffs: Prentice-Hall.

    Google Scholar 

  • Friedman, M. (1940). A comparison of alternative tests of significance for the problem of m rankings. Annals of Mathematical Statistics, 11, 86–92.

    Article  Google Scholar 

  • Garey, M. R., Graham, R. L., & Johnson, D. S. (1977). The complexity of computing Steiner minimal trees. SIAM Journal on Applied Mathematics, 32, 835–859.

    Article  Google Scholar 

  • Grimwood, G. R. (1994). The Euclidean Steiner tree problem: simulated annealing and other heuristics. Master’s thesis, Victoria University, Wellington, New Zealand, URL http://www.isor.vuw.ac.nz/~geoff/thesis.html.

  • Hansen, P., & Mladenović, N. (1997). Variable neighbourhood search. Computers and Operations Research, 24, 1097–1100.

    Article  Google Scholar 

  • Hansen, P., & Mladenović, N. (2003). Variable neighbourhood search. In F. Glover & G. A. Kochenberger (Eds.), Handbook of metaheuristics (pp. 145–184). Norwell: Kluwer. Chap 6.

    Google Scholar 

  • Hollander, M., & Wolfe, D. A. (1999). Nonparametric statistical methods (2nd edn.). New York: Wiley.

    Google Scholar 

  • Hwang, F. K., Richards, D. S., & Winter, P. (1992). The Steiner tree problem. Amsterdam: North-Holland.

    Google Scholar 

  • Karp, R. M. (1975). On the computational complexity of combinatorial problems. Networks, 5, 45–68.

    Google Scholar 

  • Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. In Proceedings of the 4th IEEE international conference on neural networks, Perth, Australia (pp. 1942–1948).

  • Kennedy, J., & Eberhart, R. (1997). A discrete binary version of the particle swarm algorithm. In IEEE conference on systems, man, and cybernetics (Vol. 5, pp. 4104–4108).

  • Kennedy, J., & Eberhart, R. (2001). Swarm intelligence. San Francisco: Morgan Kaufmann.

    Google Scholar 

  • Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598), 671–680.

    Article  Google Scholar 

  • Korte, B., Prömel, H. J., & Steger, A. (1990). Steiner trees in VLSI-layout. In B. Korte, L. Lovász, H. J. Prömel, & A. Schrijver (Eds.), Paths, flows, and VLSI-layout (pp. 185–214). Berlin: Springer.

    Google Scholar 

  • Krarup, J., & Vajda, S. (1997). On Torricelli’s geometrical solution to a problem of Fermat. IMA. Journal of Mathematics Applied in Business and Industry, 8(3), 215–224.

    Google Scholar 

  • Krumke, S. O., & Wirth, H. C. (1998). On the minimum label spanning tree problem. Information Processing Letters, 66(2), 81–85.

    Article  Google Scholar 

  • Miehle, W. (1958). Link-minimization in networks. Operations Research, 6, 232–243.

    Article  Google Scholar 

  • Moreno-Pérez, J. A., Castro-Gutiérrez, J. P., Martínez-García, F. J., Melián, B., Moreno-Vega, J. M., & Ramos, J. (2007). Discrete particle swarm optimization for the p-median problem. In Proceedings of the 7th metaheuristics international conference, Montréal, Canada.

  • Nemenyi, P. B. (1963). Distribution-free multiple comparisons. Ph.D. thesis, Princeton University, New Jersey.

  • Pacheco, J., Casado, S., & Nuñez, L. (2007). Use of VNS and TS in classification: variable selection and determination of the linear discrimination function coefficients. IMA Journal of Management Mathematics, 18(2), 191–206.

    Article  Google Scholar 

  • Pitsoulis, L. S., & Resende, M. G. C. (2002). Greedy randomized adaptive search procedure. In P. Pardalos & M. G. C. Resende (Eds.), Handbook of applied optimization (pp. 168–183). Oxford: Oxford University Press.

    Google Scholar 

  • Pérez-Pérez, M., Almeida-Rodríguez, F., & Moreno-Vega, J. M. (2007). A hybrid VNS-path relinking for the p-hub median problem. IMA Journal of Management Mathematics, 18(2), 157–171.

    Article  Google Scholar 

  • Raghavan, S., & Anandalingam, G. (2003). Telecommunications network design and management. New York: Springer.

    Google Scholar 

  • Resende, M. G. C., & Ribeiro, C. C. (2003). Greedy randomized adaptive search procedure. In F. Glover & G. Kochenberger (Eds.), Handbook in metaheuristics (pp. 219–249). Dordrecht: Kluwer.

    Google Scholar 

  • Tanenbaum, A. S. (1989). Computer networks. Englewood Cliffs: Prentice-Hall.

    Google Scholar 

  • Van-Nes, R. (2002). Design of multimodal transport networks: a hierarchical approach. Delft: Delft University Press.

    Google Scholar 

  • Voß, S. (2000). Modern heuristic search methods for the Steiner tree problem in graphs. In D. Z. Du, J. M. Smith, & J. H. Rubinstein (Eds.), Advances in Steiner tree (pp. 283–323). Boston: Kluwer.

    Google Scholar 

  • Voß, S. (2006). Steiner tree problems in telecommunications. In M. Resende & P. Pardalos (Eds.), Handbook of optimization in telecommunications (pp. 459–492). New York: Springer. Chap 18.

    Chapter  Google Scholar 

  • Voß, S., Martello, S., Osman, I. H., & Roucairol, C. (1999). Meta-heuristics. Advanced and trends local search paradigms for optimization. Norwell: Kluwer.

    Google Scholar 

  • Voß, S., Fink, A., & Duin, C. (2004). Looking ahead with the Pilot method. Annals of Operations Research, 136, 285–302.

    Article  Google Scholar 

  • Wan, Y., Chen, G., & Xu, Y. (2002). A note on the minimum label spanning tree. Information Processing Letters, 84, 99–101.

    Article  Google Scholar 

  • Winter, P. (1987). Steiner problem in networks: a survey. Networks, 17, 129–167.

    Article  Google Scholar 

  • Xiong, Y., Golden, B., & Wasil, E. (2005a). A one-parameter genetic algorithm for the minimum labelling spanning tree problem. IEEE Transactions on Evolutionary Computation, 9(1), 55–60.

    Article  Google Scholar 

  • Xiong, Y., Golden, B., & Wasil, E. (2005b). Worst case behavior of the mvca heuristic for the minimum labelling spanning tree problem. Operations Research Letters, 33(1), 77–80.

    Article  Google Scholar 

  • Xiong, Y., Golden, B., & Wasil, E. (2006). Improved heuristics for the minimum labelling spanning tree problem. IEEE Transactions on Evolutionary Computation, 10(6), 700–703.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. CARISMA and NET-ACE, School of Information Systems, Computing and Mathematics, Brunel University, Uxbridge, Middlesex, UB8 3PH, UK

    Sergio Consoli, Kenneth Darby-Dowman & Nenad Mladenović

  2. Facultad de Matemáticas, DEIOC, IUDR, Universidad de La Laguna, 4a planta Astrofisico Francisco Sánchez s/n, 38271, Santa Cruz de Tenerife, Spain

    José Andrés Moreno-Pérez

Authors
  1. Sergio Consoli
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Kenneth Darby-Dowman
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Nenad Mladenović
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. José Andrés Moreno-Pérez
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sergio Consoli.

Additional information

Sergio Consoli was supported by an E.U. Marie Curie Fellowship for Early Stage Researcher Training (EST-FP6) under grant number MEST-CT-2004-006724 at Brunel University (project NET-ACE).

José Andrés Moreno-Pérez was supported by the projects TIN2005-08404-C04-03 of the Spanish Government (with financial support from the European Union under the FEDER project) and PI042005/044 of the Canary Government.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Consoli, S., Darby-Dowman, K., Mladenović, N. et al. Variable neighbourhood search for the minimum labelling Steiner tree problem. Ann Oper Res 172, 71–96 (2009). https://doi.org/10.1007/s10479-008-0507-y

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-008-0507-y

Keywords

Search

Navigation