IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v274y2019i1p22-34.html
   My bibliography  Save this article

A hybrid metaheuristic for the minimum labeling spanning tree problem

Author

Listed:
  • Silva, Thiago Gouveia da
  • Queiroga, Eduardo
  • Ochi, Luiz Satoru
  • Cabral, Lucídio dos Anjos Formiga
  • Gueye, Serigne
  • Michelon, Philippe

Abstract

An edge-labeled graph (ELG) is a graph in which each edge has a label associated. Given G, an ELG, the minimum labeling spanning tree problem (MLSTP) is an NP-hard problem that consists in finding a spanning tree in G by using a minimum number of labels. The MLSTP has applications in areas such as computer networks, multimodal transportation networks, and data compression. This paper introduces new concepts, presents a revised version of the maximum vertex covering algorithm and provides a tighter bound to its time complexity. Further, a new MIP-based metaheuristic is proposed for solving the MLSTP, the multi-start local branching (MSLB). It combines the efficiency of the proposed constructive heuristics with the capacity of exploration of a new local search method based on MIP. The computational experiments performed show that the MSLB is superior to the current state-of-the-art metaheuristics in respect to quality of the solutions and processing times.

Suggested Citation

  • Silva, Thiago Gouveia da & Queiroga, Eduardo & Ochi, Luiz Satoru & Cabral, Lucídio dos Anjos Formiga & Gueye, Serigne & Michelon, Philippe, 2019. "A hybrid metaheuristic for the minimum labeling spanning tree problem," European Journal of Operational Research, Elsevier, vol. 274(1), pages 22-34.
    • Handle: RePEc:eee:ejores:v:274:y:2019:i:1:p:22-34
    DOI: 10.1016/j.ejor.2018.09.044
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221718308269
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2018.09.044?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Consoli, S. & Darby-Dowman, K. & Mladenovic, N. & Moreno Pérez, J.A., 2009. "Greedy Randomized Adaptive Search and Variable Neighbourhood Search for the minimum labelling spanning tree problem," European Journal of Operational Research, Elsevier, vol. 196(2), pages 440-449, July.
    2. Andreas M. Chwatal & Günther R. Raidl, 2011. "Solving the Minimum Label Spanning Tree Problem by Mathematical Programming Techniques," Advances in Operations Research, Hindawi, vol. 2011, pages 1-38, June.
    3. Sergio Consoli & Kenneth Darby-Dowman & Nenad Mladenović & José Moreno-Pérez, 2009. "Variable neighbourhood search for the minimum labelling Steiner tree problem," Annals of Operations Research, Springer, vol. 172(1), pages 71-96, November.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Thiago Gouveia da Silva & Serigne Gueye & Philippe Michelon & Luiz Satoru Ochi & Lucídio dos Anjos Formiga Cabral, 2019. "A polyhedral approach to the generalized minimum labeling spanning tree problem," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 7(1), pages 47-77, March.
    2. Raffaele Cerulli & Ciriaco D'Ambrosio & Domenico Serra & Carmine Sorgente, 2024. "The Budgeted Labeled Minimum Spanning Tree Problem," Mathematics, MDPI, vol. 12(2), pages 1-22, January.
    3. Pierre Hansen & Nenad Mladenović & José Moreno Pérez, 2010. "Variable neighbourhood search: methods and applications," Annals of Operations Research, Springer, vol. 175(1), pages 367-407, March.
    4. Zhaowei Miao & Feng Yang & Ke Fu & Dongsheng Xu, 2012. "Transshipment service through crossdocks with both soft and hard time windows," Annals of Operations Research, Springer, vol. 192(1), pages 21-47, January.
    5. Clímaco, João C.N. & Eugénia Captivo, M. & Pascoal, Marta M.B., 2010. "On the bicriterion - minimal cost/minimal label - spanning tree problem," European Journal of Operational Research, Elsevier, vol. 204(2), pages 199-205, July.
    6. Ghoshal, Sudishna & Sundar, Shyam, 2020. "Two heuristics for the rainbow spanning forest problem," European Journal of Operational Research, Elsevier, vol. 285(3), pages 853-864.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:274:y:2019:i:1:p:22-34. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.