IDEAS home Printed from https://ideas.repec.org/p/por/fepwps/493.html
   My bibliography  Save this paper

Solving Hop-constrained MST problems with ACO

Author

Listed:
  • Marta S.R. Monteiro

    (Faculdade de Economia and LIAAD-INESC TEC)

  • Dalila B.M.M. Fontes

    (Faculdade de Economia and LIAAD-INESC TEC)

  • Fernando A.C.C. Fontes

    (Faculdade de Engenharia da Universidade do Porto and ISR-Porto)

Abstract

The Hop-constrained Minimum cost Flow Spanning Tree (HMFST) problem is an extension of the Hop-Constrained Minimum Spanning Tree problem since it considers flow requirements other than unit flows. Given that we consider the total costs to be nonlinearly flow dependent with a fixed-charge component and given the combinatorial nature of this class of problems, we propose a heuristic approach to address them. The proposed approach is a hybrid metaheuristic based on Ant Colony Optimization (ACO) and on Local Search (LS). In order to test the performance of our algorithm we have solved a set of benchmark problems and compared the results obtained with the ones reported in the literature for a Multi-Population Genetic Algorithm (MPGA). We have also compared our results, regarding computational time, with those of CPLEX. Our algorithm proved to be able to find an optimum solution in more than 75% of the runs, for each problem instance solved, and was also able to improve on many results reported for the MPGA. Furthermore, for every single problem instance we were able to find a feasible solution, which was not the case for the MPGA nor for CPLEX. Regarding running times, our algorithm improves upon the computational time used by CPLEX and was always lower than that of the MPGA.

Suggested Citation

  • Marta S.R. Monteiro & Dalila B.M.M. Fontes & Fernando A.C.C. Fontes, 2013. "Solving Hop-constrained MST problems with ACO," FEP Working Papers 493, Universidade do Porto, Faculdade de Economia do Porto.
    • Handle: RePEc:por:fepwps:493
    as

    Download full text from publisher

    File URL: http://www.fep.up.pt/investigacao/workingpapers/wp493.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Santos, Luís & Coutinho-Rodrigues, João & Current, John R., 2010. "An improved ant colony optimization based algorithm for the capacitated arc routing problem," Transportation Research Part B: Methodological, Elsevier, vol. 44(2), pages 246-266, February.
    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. Gao, Shangce & Wang, Yirui & Cheng, Jiujun & Inazumi, Yasuhiro & Tang, Zheng, 2016. "Ant colony optimization with clustering for solving the dynamic location routing problem," Applied Mathematics and Computation, Elsevier, vol. 285(C), pages 149-173.
    2. Claudia Bode & Stefan Irnich, 2012. "Cut-First Branch-and-Price-Second for the Capacitated Arc-Routing Problem," Operations Research, INFORMS, vol. 60(5), pages 1167-1182, October.
    3. Li, Jiliu & Qin, Hu & Shen, Huaxiao & Tsui, Kwok Leung, 2019. "The unilateral transportation problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 132(C), pages 1-29.
    4. Yu, Mingzhu & Jin, Xin & Zhang, Zizhen & Qin, Hu & Lai, Qidong, 2019. "The split-delivery mixed capacitated arc-routing problem: Applications and a forest-based tabu search approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 132(C), pages 141-162.
    5. Calvete, Herminia I. & Galé, Carmen & Iranzo, José A., 2016. "MEALS: A multiobjective evolutionary algorithm with local search for solving the bi-objective ring star problem," European Journal of Operational Research, Elsevier, vol. 250(2), pages 377-388.
    6. Coutinho-Rodrigues, João & Tralhão, Lino & Alçada-Almeida, Luís, 2012. "A bi-objective modeling approach applied to an urban semi-desirable facility location problem," European Journal of Operational Research, Elsevier, vol. 223(1), pages 203-213.
    7. Meisel, Frank & Thiele, Nicole, 2014. "Where to dispose of urban green waste? Transportation planning for the maintenance of public green spaces," Transportation Research Part A: Policy and Practice, Elsevier, vol. 64(C), pages 147-162.
    8. Chen, Yuning & Hao, Jin-Kao, 2018. "Two phased hybrid local search for the periodic capacitated arc routing problem," European Journal of Operational Research, Elsevier, vol. 264(1), pages 55-65.
    9. Tao Zhang & W. Art Chaovalitwongse & Yuejie Zhang, 2014. "Integrated Ant Colony and Tabu Search approach for time dependent vehicle routing problems with simultaneous pickup and delivery," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 288-309, July.
    10. Zsuzsanna Nagy & Ágnes Werner-Stark & Tibor Dulai, 2022. "An Artificial Bee Colony Algorithm for Static and Dynamic Capacitated Arc Routing Problems," Mathematics, MDPI, vol. 10(13), pages 1-38, June.
    11. Zhang, Zhenzhen & Wei, Lijun & Lim, Andrew, 2015. "An evolutionary local search for the capacitated vehicle routing problem minimizing fuel consumption under three-dimensional loading constraints," Transportation Research Part B: Methodological, Elsevier, vol. 82(C), pages 20-35.
    12. Reddy, K. Nageswara & Kumar, Akhilesh & Choudhary, Alok & Cheng, T. C. Edwin, 2022. "Multi-period green reverse logistics network design: An improved Benders-decomposition-based heuristic approach," European Journal of Operational Research, Elsevier, vol. 303(2), pages 735-752.
    13. Claudia Bode & Stefan Irnich, 2012. "In-Depth Analysis of Pricing Problem Relaxations for the Capacitated Arc-Routing Problem," Working Papers 1212, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    14. Thibaut Vidal, 2017. "Node, Edge, Arc Routing and Turn Penalties: Multiple Problems—One Neighborhood Extension," Operations Research, INFORMS, vol. 65(4), pages 992-1010, August.
    15. Claudia Bode & Stefan Irnich, 2015. "In-Depth Analysis of Pricing Problem Relaxations for the Capacitated Arc-Routing Problem," Transportation Science, INFORMS, vol. 49(2), pages 369-383, May.
    16. Chen, Yuning & Hao, Jin-Kao & Glover, Fred, 2016. "A hybrid metaheuristic approach for the capacitated arc routing problem," European Journal of Operational Research, Elsevier, vol. 253(1), pages 25-39.
    17. Les Foulds & Humberto Longo & Jean Martins, 2015. "A compact transformation of arc routing problems into node routing problems," Annals of Operations Research, Springer, vol. 226(1), pages 177-200, March.

    More about this item

    Keywords

    Ant Colony Optimization; Nonlinear Costs; Hybrid; Local Search; Minimum Spanning Tree Problem; Hop-constraints;
    All these keywords.

    JEL classification:

    • C61 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Optimization Techniques; Programming Models; Dynamic Analysis
    • C44 - Mathematical and Quantitative Methods - - Econometric and Statistical Methods: Special Topics - - - Operations Research; Statistical Decision Theory

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    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:por:fepwps:493. 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: the person in charge (email available below). General contact details of provider: https://edirc.repec.org/data/fepuppt.html .

    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.