IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v53y2019i6p1673-1694.html
   My bibliography  Save this article

Comparative Analysis of Capacitated Arc Routing Formulations for Designing a New Branch-Cut-and-Price Algorithm

Author

Listed:
  • Diego Pecin

    (H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332)

  • Eduardo Uchoa

    (Departamento de Engenharia de Produção, Universidade Federal Fluminense, Niterói RJ, Brasil 24210-240)

Abstract

The current best exact algorithms for the Capacitated Arc Routing Problem are based on the combination of cut and column generation. This work presents a deep theoretical investigation of the formulations behind those algorithms, classifying them and pointing out similarities and differences, advantages and disadvantages. In particular, we discuss which families of cuts and branching strategies are suitable for each alternative and their pricing complexities. That analysis is used to justify key decisions on constructing a new branch-cut-and-price algorithm that combines several features picked from the capacitated arc routing literature with some features adapted from the most successful recent algorithms for node routing. The computational experiments show that the resulting algorithm is indeed effective and can solve almost all open instances from the classical benchmark sets.

Suggested Citation

  • Diego Pecin & Eduardo Uchoa, 2019. "Comparative Analysis of Capacitated Arc Routing Formulations for Designing a New Branch-Cut-and-Price Algorithm," Transportation Science, INFORMS, vol. 53(6), pages 1673-1694, November.
    • Handle: RePEc:inm:ortrsc:v:53:y:2019:i:6:p:1673-1694
    DOI: 10.1287/trsc.2019.0900
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/trsc.2019.0900
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.2019.0900?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
    ---><---

    References listed on IDEAS

    as
    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. 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.
    3. Tilk, Christian & Rothenbächer, Ann-Kathrin & Gschwind, Timo & Irnich, Stefan, 2017. "Asymmetry matters: Dynamic half-way points in bidirectional labeling for solving shortest path problems with resource constraints faster," European Journal of Operational Research, Elsevier, vol. 261(2), pages 530-539.
    4. Mads Jepsen & Bjørn Petersen & Simon Spoorendonk & David Pisinger, 2008. "Subset-Row Inequalities Applied to the Vehicle-Routing Problem with Time Windows," Operations Research, INFORMS, vol. 56(2), pages 497-511, April.
    5. 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.
    6. Roberto Baldacci & Aristide Mingozzi & Roberto Roberti, 2011. "New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem," Operations Research, INFORMS, vol. 59(5), pages 1269-1283, October.
    7. Pessoa, Artur & Sadykov, Ruslan & Uchoa, Eduardo, 2018. "Enhanced Branch-Cut-and-Price algorithm for heterogeneous fleet vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 270(2), pages 530-543.
    8. Hatem Ben Amor & Jacques Desrosiers & José Manuel Valério de Carvalho, 2006. "Dual-Optimal Inequalities for Stabilized Column Generation," Operations Research, INFORMS, vol. 54(3), pages 454-463, June.
    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. Stefan Irnich & Daniel Villeneuve, 2006. "The Shortest-Path Problem with Resource Constraints and k -Cycle Elimination for k (ge) 3," INFORMS Journal on Computing, INFORMS, vol. 18(3), pages 391-406, August.
    11. 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.
    12. 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.
    13. Bode, Claudia & Irnich, Stefan, 2014. "The shortest-path problem with resource constraints with (k,2)-loop elimination and its application to the capacitated arc-routing problem," European Journal of Operational Research, Elsevier, vol. 238(2), pages 415-426.
    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. Thibaut Vidal & Rafael Martinelli & Tuan Anh Pham & Minh Hoàng Hà, 2021. "Arc Routing with Time-Dependent Travel Times and Paths," Transportation Science, INFORMS, vol. 55(3), pages 706-724, May.

    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. Katrin Heßler & Stefan Irnich, 2023. "Partial Dominance in Branch-Price-and-Cut for the Basic Multicompartment Vehicle-Routing Problem," INFORMS Journal on Computing, INFORMS, vol. 35(1), pages 50-65, January.
    2. Bode, Claudia & Irnich, Stefan, 2014. "The shortest-path problem with resource constraints with (k,2)-loop elimination and its application to the capacitated arc-routing problem," European Journal of Operational Research, Elsevier, vol. 238(2), pages 415-426.
    3. Luciano Costa & Claudio Contardo & Guy Desaulniers, 2019. "Exact Branch-Price-and-Cut Algorithms for Vehicle Routing," Transportation Science, INFORMS, vol. 53(4), pages 946-985, July.
    4. 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.
    5. Katrin Heßler & Stefan Irnich, 2021. "Partial Dominance in Branch-Price-and-Cut for the Basic Multi-Compartment Vehicle-Routing Problem," Working Papers 2115, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    6. Timo Hintsch & Stefan Irnich & Lone Kiilerich, 2021. "Branch-Price-and-Cut for the Soft-Clustered Capacitated Arc-Routing Problem," Transportation Science, INFORMS, vol. 55(3), pages 687-705, May.
    7. Stefan Faldum & Timo Gschwind & Stefan Irnich, 2023. "Subset-Row Inequalities and Unreachability in Path-based Formulations for Routing and Scheduling Problems," Working Papers 2310, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    8. Guy Desaulniers & Timo Gschwind & Stefan Irnich, 2020. "Variable Fixing for Two-Arc Sequences in Branch-Price-and-Cut Algorithms on Path-Based Models," Transportation Science, INFORMS, vol. 54(5), pages 1526-5447, September.
    9. Ann-Kathrin Rothenbächer & Michael Drexl & Stefan Irnich, 2018. "Branch-and-Price-and-Cut for the Truck-and-Trailer Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 52(5), pages 1174-1190, October.
    10. Heßler, Katrin, 2021. "Exact algorithms for the multi-compartment vehicle routing problem with flexible compartment sizes," European Journal of Operational Research, Elsevier, vol. 294(1), pages 188-205.
    11. 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.
    12. Ann-Kathrin Rothenbächer & Michael Drexl & Stefan Irnich, 2016. "Branch-and-Price-and-Cut for the Truck-andTrailer Routing Problem with Time Windows," Working Papers 1617, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    13. Gschwind, Timo & Bianchessi, Nicola & Irnich, Stefan, 2019. "Stabilized branch-price-and-cut for the commodity-constrained split delivery vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 278(1), pages 91-104.
    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. Jeanette Schmidt & Christian Tilk & Stefan Irnich, 2023. "Exact Solution of the Vehicle Routing Problem With Drones," Working Papers 2311, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    16. Katrin Heßler, 2020. "Exact Algorithms for the Multi-Compartment Vehicle Routing Problem with Flexible Compartment Sizes," Working Papers 2007, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    17. Nicola Bianchessi & Stefan Irnich & Christian Tilk, 2020. "A Branch-Price-and-Cut Algorithm for the Capacitated Multiple Vehicle Traveling Purchaser Problem with Unitary Demand," Working Papers 2003, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    18. Timo Hintsch & Stefan Irnich, 2018. "Exact Solution of the Soft-Clustered Vehicle Routing Problem," Working Papers 1813, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    19. Christian Tilk & Ann-Kathrin Rothenbächer & Timo Gschwind & Stefan Irnich, 2016. "Asymmetry Helps: Dynamic Half-Way Points for Solving Shortest Path Problems with Resource Constraints Faster," Working Papers 1615, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    20. Tilk, Christian & Rothenbächer, Ann-Kathrin & Gschwind, Timo & Irnich, Stefan, 2017. "Asymmetry matters: Dynamic half-way points in bidirectional labeling for solving shortest path problems with resource constraints faster," European Journal of Operational Research, Elsevier, vol. 261(2), pages 530-539.

    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:inm:ortrsc:v:53:y:2019:i:6:p:1673-1694. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.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.