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

A two-phase hybrid algorithm for the periodic rural postman problem with irregular services on mixed graphs

Author

Listed:
  • Benavent, Enrique
  • Corberán, Ángel
  • Laganà, Demetrio
  • Vocaturo, Francesca

Abstract

In this article we address the periodic rural postman problem with irregular services (PRPP–IS), where some arcs and/or edges of a mixed graph must be traversed (to be serviced) a certain number of times in some subsets of days of a given time horizon. The goal is to define a set of minimum cost tours, one for each day or period of the time horizon, that satisfy the service requirements. For this problem we propose a two-phase algorithm that combines heuristics and mathematical programming. In the first phase, two different procedures are used to construct feasible solutions: a multi-start heuristic based on feasibility pump and a multi-start constructive heuristic. From these solutions, some fragments (parts of tours associated with the different days) are extracted. The second phase determines a solution for the PRPP–IS by combining the fragments by means of a mathematical model. We show the effectiveness of this solution approach through an extensive experimental phase on different sets of instances.

Suggested Citation

  • Benavent, Enrique & Corberán, Ángel & Laganà, Demetrio & Vocaturo, Francesca, 2023. "A two-phase hybrid algorithm for the periodic rural postman problem with irregular services on mixed graphs," European Journal of Operational Research, Elsevier, vol. 307(1), pages 64-81.
    • Handle: RePEc:eee:ejores:v:307:y:2023:i:1:p:64-81
    DOI: 10.1016/j.ejor.2022.09.026
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221722007548
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2022.09.026?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. Patrizia Beraldi & Gianpaolo Ghiani & Roberto Musmanno & Francesca Vocaturo, 2010. "Efficient Neighborhood Search For The Probabilistic Multi-Vehicle Pickup And Delivery Problem," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 27(03), pages 301-314.
    2. Gerardo Berbeglia & Jean-François Cordeau & Gilbert Laporte, 2012. "A Hybrid Tabu Search and Constraint Programming Algorithm for the Dynamic Dial-a-Ride Problem," INFORMS Journal on Computing, INFORMS, vol. 24(3), pages 343-355, August.
    3. Lacomme, Philippe & Prins, Christian & Ramdane-Cherif, Wahiba, 2005. "Evolutionary algorithms for periodic arc routing problems," European Journal of Operational Research, Elsevier, vol. 165(2), pages 535-553, September.
    4. Angel Corberán & Gustavo Mejía & José M. Sanchis, 2005. "New Results on the Mixed General Routing Problem," Operations Research, INFORMS, vol. 53(2), pages 363-376, April.
    5. Chefi Triki, 2017. "Solving the Periodic Edge Routing Problem in the Municipal Waste Collection," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 34(03), pages 1-13, June.
    6. Albareda-Sambola, Maria & Fernandez, Elena & Laporte, Gilbert, 2007. "Heuristic and lower bound for a stochastic location-routing problem," European Journal of Operational Research, Elsevier, vol. 179(3), pages 940-955, June.
    7. 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.
    8. Ali Mehsin Alyasiry & Michael Forbes & Michael Bulmer, 2019. "An Exact Algorithm for the Pickup and Delivery Problem with Time Windows and Last-in-First-out Loading," Transportation Science, INFORMS, vol. 53(6), pages 1695-1705, November.
    9. Chu, Feng & Labadi, Nacima & Prins, Christian, 2006. "A Scatter Search for the periodic capacitated arc routing problem," European Journal of Operational Research, Elsevier, vol. 169(2), pages 586-605, March.
    10. Juan-Pablo Riquelme-Rodríguez & Michel Gamache & André Langevin, 2014. "Periodic capacitated arc-routing problem with inventory constraints," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 65(12), pages 1840-1852, December.
    11. Benavent, Enrique & Corberán, Ángel & Laganà, Demetrio & Vocaturo, Francesca, 2019. "The periodic rural postman problem with irregular services on mixed graphs," European Journal of Operational Research, Elsevier, vol. 276(3), pages 826-839.
    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. D Soler & E Martínez & J C Micó, 2008. "A transformation for the mixed general routing problem with turn penalties," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(4), pages 540-547, April.
    2. Chefi Triki, 2017. "Solving the Periodic Edge Routing Problem in the Municipal Waste Collection," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 34(03), pages 1-13, June.
    3. 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.
    4. Thibaut Vidal & Teodor Gabriel Crainic & Michel Gendreau & Nadia Lahrichi & Walter Rei, 2012. "A Hybrid Genetic Algorithm for Multidepot and Periodic Vehicle Routing Problems," Operations Research, INFORMS, vol. 60(3), pages 611-624, June.
    5. Prodhon, Caroline, 2011. "A hybrid evolutionary algorithm for the periodic location-routing problem," European Journal of Operational Research, Elsevier, vol. 210(2), pages 204-212, April.
    6. Benavent, Enrique & Corberán, Ángel & Laganà, Demetrio & Vocaturo, Francesca, 2019. "The periodic rural postman problem with irregular services on mixed graphs," European Journal of Operational Research, Elsevier, vol. 276(3), pages 826-839.
    7. Abdelkader Sbihi & Richard Eglese, 2010. "Combinatorial optimization and Green Logistics," Annals of Operations Research, Springer, vol. 175(1), pages 159-175, March.
    8. Gopalan, Ram, 2014. "The Aircraft Maintenance Base Location Problem," European Journal of Operational Research, Elsevier, vol. 236(2), pages 634-642.
    9. 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.
    10. A. Mor & M. G. Speranza, 2020. "Vehicle routing problems over time: a survey," 4OR, Springer, vol. 18(2), pages 129-149, June.
    11. LIAN, Ying & LUCAS, Flavien & SÖRENSEN, Kenneth, 2022. "On-demand bus routing problem with dynamic stochastic requests and prepositioning," Working Papers 2022004, University of Antwerp, Faculty of Business and Economics.
    12. Sahar Validi & Arijit Bhattacharya & P. J. Byrne, 2020. "Sustainable distribution system design: a two-phase DoE-guided meta-heuristic solution approach for a three-echelon bi-objective AHP-integrated location-routing model," Annals of Operations Research, Springer, vol. 290(1), pages 191-222, July.
    13. Hashemi Doulabi, Seyed Hossein & Seifi, Abbas, 2013. "Lower and upper bounds for location-arc routing problems with vehicle capacity constraints," European Journal of Operational Research, Elsevier, vol. 224(1), pages 189-208.
    14. Hosni, Hadi & Naoum-Sawaya, Joe & Artail, Hassan, 2014. "The shared-taxi problem: Formulation and solution methods," Transportation Research Part B: Methodological, Elsevier, vol. 70(C), pages 303-318.
    15. Drexl, Michael & Schneider, Michael, 2015. "A survey of variants and extensions of the location-routing problem," European Journal of Operational Research, Elsevier, vol. 241(2), pages 283-308.
    16. Zhang, Jian & Woensel, Tom Van, 2023. "Dynamic vehicle routing with random requests: A literature review," International Journal of Production Economics, Elsevier, vol. 256(C).
    17. Andaryan, Abdullah Zareh & Mousighichi, Kasra & Ghaffarinasab, Nader, 2024. "A heuristic approach to the stochastic capacitated single allocation hub location problem with Bernoulli demands," European Journal of Operational Research, Elsevier, vol. 312(3), pages 954-968.
    18. Lu, Jiawei & Nie, Qinghui & Mahmoudi, Monirehalsadat & Ou, Jishun & Li, Chongnan & Zhou, Xuesong Simon, 2022. "Rich arc routing problem in city logistics: Models and solution algorithms using a fluid queue-based time-dependent travel time representation," Transportation Research Part B: Methodological, Elsevier, vol. 166(C), pages 143-182.
    19. Lian, Ying & Lucas, Flavien & Sörensen, Kenneth, 2024. "Prepositioning can improve the performance of a dynamic stochastic on-demand public bus system," European Journal of Operational Research, Elsevier, vol. 312(1), pages 338-356.
    20. Karels, Vincent C.G. & Rei, Walter & Veelenturf, Lucas P. & Van Woensel, Tom, 2024. "A vehicle routing problem with multiple service agreements," European Journal of Operational Research, Elsevier, vol. 313(1), pages 129-145.

    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:307:y:2023:i:1:p:64-81. 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.