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

Two phased hybrid local search for the periodic capacitated arc routing problem

Author

Listed:
  • Chen, Yuning
  • Hao, Jin-Kao

Abstract

The periodic capacitated arc routing problem (PCARP) is a challenging general model with important applications. The PCARP has two hierarchical optimization objectives: a primary objective of minimizing the number of vehicles (Fv) and a secondary objective of minimizing the total cost (Fc). In this paper, we propose an effective two phased hybrid local search (HLS) algorithm for the PCARP. The first phase makes a particular effort to optimize the primary objective while the second phase seeks to further optimize both objectives by using the resulting number of vehicles of the first phase as an upper bound to prune the search space. For both phases, combined local search heuristics are devised to ensure an effective exploration of the search space. Experimental results on 63 benchmark instances demonstrate that HLS performs remarkably well both in terms of computational efficiency and solution quality. In particular, HLS discovers 44 improved best known values (new upper bounds) for the total cost objective Fc while attaining all the known optimal values regarding the objective of the number of vehicles Fv. To our knowledge, this is the first PCARP algorithm reaching such a performance. Key components of HLS are analyzed to better understand their contributions to the overall performance.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:264:y:2018:i:1:p:55-65
    DOI: 10.1016/j.ejor.2017.06.025
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221717305647
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2017.06.025?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. 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.
    2. 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.
    3. Francis, Peter & Smilowitz, Karen, 2006. "Modeling techniques for periodic vehicle routing problems," Transportation Research Part B: Methodological, Elsevier, vol. 40(10), pages 872-884, December.
    4. M. Gaudioso & G. Paletta, 1992. "A Heuristic for the Periodic Vehicle Routing Problem," Transportation Science, INFORMS, vol. 26(2), pages 86-92, May.
    5. Beullens, Patrick & Muyldermans, Luc & Cattrysse, Dirk & Van Oudheusden, Dirk, 2003. "A guided local search heuristic for the capacitated arc routing problem," European Journal of Operational Research, Elsevier, vol. 147(3), pages 629-643, June.
    6. Alain Hertz & Michel Mittaz, 2001. "A Variable Neighborhood Descent Algorithm for the Undirected Capacitated Arc Routing Problem," Transportation Science, INFORMS, vol. 35(4), pages 425-434, November.
    7. 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.
    8. 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.
    9. 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.
    10. Alain Hertz & Gilbert Laporte & Michel Mittaz, 2000. "A Tabu Search Heuristic for the Capacitated arc Routing Problem," Operations Research, INFORMS, vol. 48(1), pages 129-135, February.
    11. Philippe Lacomme & Christian Prins & Wahiba Ramdane-Cherif, 2004. "Competitive Memetic Algorithms for Arc Routing Problems," Annals of Operations Research, Springer, vol. 131(1), pages 159-185, October.
    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. 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.
    2. Li, Mingjie & Hao, Jin-Kao & Wu, Qinghua, 2022. "Learning-driven feasible and infeasible tabu search for airport gate assignment," European Journal of Operational Research, Elsevier, vol. 302(1), pages 172-186.
    3. Christina C. Bartenschlager & Jens O. Brunner, 2019. "Reaching for the stars: attention to multiple testing problems and method recommendations using simulation for business research," Journal of Business Economics, Springer, vol. 89(4), pages 447-479, June.
    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.

    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. 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.
    2. Abdelkader Sbihi & Richard Eglese, 2010. "Combinatorial optimization and Green Logistics," Annals of Operations Research, Springer, vol. 175(1), pages 159-175, March.
    3. Jesica Armas & Peter Keenan & Angel A. Juan & Seán McGarraghy, 2019. "Solving large-scale time capacitated arc routing problems: from real-time heuristics to metaheuristics," Annals of Operations Research, Springer, vol. 273(1), pages 135-162, February.
    4. 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.
    5. 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.
    6. Fung, Richard Y.K. & Liu, Ran & Jiang, Zhibin, 2013. "A memetic algorithm for the open capacitated arc routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 50(C), pages 53-67.
    7. 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.
    8. 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.
    9. Gilbert Laporte & Roberto Musmanno & Francesca Vocaturo, 2010. "An Adaptive Large Neighbourhood Search Heuristic for the Capacitated Arc-Routing Problem with Stochastic Demands," Transportation Science, INFORMS, vol. 44(1), pages 125-135, February.
    10. Porumbel, Daniel & Goncalves, Gilles & Allaoui, Hamid & Hsu, Tienté, 2017. "Iterated Local Search and Column Generation to solve Arc-Routing as a permutation set-covering problem," European Journal of Operational Research, Elsevier, vol. 256(2), pages 349-367.
    11. 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.
    12. 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.
    13. 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.
    14. 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.
    15. 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.
    16. 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.
    17. 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.
    18. Ann-Kathrin Rothenbächer, 2017. "Branch-and-Price-and-Cut for the Periodic Vehicle Routing Problem with Flexible Schedule Structures," Working Papers 1714, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    19. 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.
    20. 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.

    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:264:y:2018:i:1:p:55-65. 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.