IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v35y2018i1d10.1007_s10878-015-9945-z.html
   My bibliography  Save this article

Partitioning of supply/demand graphs with capacity limitations: an ant colony approach

Author

Listed:
  • Raka Jovanovic

    (Hamad bin Khalifa University)

  • Abdelkader Bousselham

    (Hamad bin Khalifa University)

  • Stefan Voß

    (University of Hamburg
    Pontificia Universidad Católica de Valparaíso)

Abstract

In recent years there has been a growing interest for the problem of the minimal partitioning of graphs with supply and demand, due to its close connection to electrical distribution systems, especially in the context of smartgrids. In this paper we present a new version of the problem which is more suitable for practical applications in modeling such systems. More precisely, the constraint of having a unique supply node in a subgraph (partition) is substituted with a limit on the number of subgraphs and the capacity for each of them. The problem is initially solved by a two stage greedy method. With the goal of further improving the quality of found solutions, a corresponding GRASP and an ant colony optimization algorithm are developed. Due to the novelty of the problem, we include a description of a method for generating test instances with known optimal solutions. In our computational experiments we evaluate the performance of the proposed algorithms on both trees and general graphs. The tests show that the proposed ant colony approach manages to frequently find optimal solutions. It has an average relative error of less than 2 % when compared to known optimal solutions. Moreover, it outperform the GRASP.

Suggested Citation

  • Raka Jovanovic & Abdelkader Bousselham & Stefan Voß, 2018. "Partitioning of supply/demand graphs with capacity limitations: an ant colony approach," Journal of Combinatorial Optimization, Springer, vol. 35(1), pages 224-249, January.
    • Handle: RePEc:spr:jcomop:v:35:y:2018:i:1:d:10.1007_s10878-015-9945-z
    DOI: 10.1007/s10878-015-9945-z
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-015-9945-z
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-015-9945-z?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. Raka Jovanovic & Abdelkader Bousselham & Stefan Voß, 2015. "A heuristic method for solving the problem of partitioning graphs with supply and demand," Annals of Operations Research, Springer, vol. 235(1), pages 371-393, December.
    2. Stefan Voßs & Andreas Fink & Cees Duin, 2005. "Looking Ahead with the Pilot Method," Annals of Operations Research, Springer, vol. 136(1), pages 285-302, April.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Jianming Zhu & Shuyue Liu & Smita Ghosh, 2019. "Model and algorithm of routes planning for emergency relief distribution in disaster management with disaster information update," Journal of Combinatorial Optimization, Springer, vol. 38(1), pages 208-223, July.

    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. Jorge Oyola & Halvard Arntzen & David L. Woodruff, 2017. "The stochastic vehicle routing problem, a literature review, Part II: solution methods," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 6(4), pages 349-388, December.
    2. GALARZA MONTENEGRO, Bryan David & SÖRENSEN, Kenneth & VANSTEENWEGEN, Pieter, 2023. "A demand-responsive feeder service with a maximum headway at mandatory stops," Working Papers 2023001, University of Antwerp, Faculty of Business and Economics.
    3. Goodson, Justin C. & Thomas, Barrett W. & Ohlmann, Jeffrey W., 2017. "A rollout algorithm framework for heuristic solutions to finite-horizon stochastic dynamic programs," European Journal of Operational Research, Elsevier, vol. 258(1), pages 216-229.
    4. Michele Ciavotta & Carlo Meloni & Marco Pranzo, 2016. "Speeding up a Rollout algorithm for complex parallel machine scheduling," International Journal of Production Research, Taylor & Francis Journals, vol. 54(16), pages 4993-5009, August.
    5. Raka Jovanovic & Antonio P. Sanfilippo & Stefan Voß, 2022. "Fixed set search applied to the multi-objective minimum weighted vertex cover problem," Journal of Heuristics, Springer, vol. 28(4), pages 481-508, August.
    6. 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.
    7. Fabian Schäfer & Manuel Walther & Dominik G. Grimm & Alexander Hübner, 2023. "Combining machine learning and optimization for the operational patient-bed assignment problem," Health Care Management Science, Springer, vol. 26(4), pages 785-806, December.
    8. Carvalho, A.S. & Captivo, M.E. & Marques, I., 2020. "Integrating the ambulance dispatching and relocation problems to maximize system’s preparedness," European Journal of Operational Research, Elsevier, vol. 283(3), pages 1064-1080.
    9. Marian Rainer-Harbach & Petrina Papazek & Günther Raidl & Bin Hu & Christian Kloimüllner, 2015. "PILOT, GRASP, and VNS approaches for the static balancing of bicycle sharing systems," Journal of Global Optimization, Springer, vol. 63(3), pages 597-629, November.
    10. 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.
    11. Höller, Holger & Melián, Belén & Voí, Stefan, 2008. "Applying the pilot method to improve VNS and GRASP metaheuristics for the design of SDH/WDM networks," European Journal of Operational Research, Elsevier, vol. 191(3), pages 691-704, December.
    12. Amadeu A. Coco & Andréa Cynthia Santos & Thiago F. Noronha, 2022. "Robust min-max regret covering problems," Computational Optimization and Applications, Springer, vol. 83(1), pages 111-141, September.
    13. Jorge E. Mendoza & Bruno Castanier & Christelle Guéret & Andrés L. Medaglia & Nubia Velasco, 2011. "Constructive Heuristics for the Multicompartment Vehicle Routing Problem with Stochastic Demands," Transportation Science, INFORMS, vol. 45(3), pages 346-363, August.
    14. de Souza, Mauricio C. & Martins, Pedro, 2008. "Skewed VNS enclosing second order algorithm for the degree constrained minimum spanning tree problem," European Journal of Operational Research, Elsevier, vol. 191(3), pages 677-690, December.
    15. Amadeu Coco & João Júnior & Thiago Noronha & Andréa Santos, 2014. "An integer linear programming formulation and heuristics for the minmax relative regret robust shortest path problem," Journal of Global Optimization, Springer, vol. 60(2), pages 265-287, October.

    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:spr:jcomop:v:35:y:2018:i:1:d:10.1007_s10878-015-9945-z. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.