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. 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.
    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. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. 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.
    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. 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.
    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. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    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. 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.
    10. 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.
    11. 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.
    12. 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.
    13. 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.
    14. 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.
    15. 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.
    16. 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.
    17. Timo Gschwind & Nicola Bianchessi & Stefan Irnich, 2018. "Stabilized Branch-Price-and-Cut for the Commodity-constrained Split Delivery Vehicle Routing Problem," Working Papers 1817, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    18. 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.
    19. 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.
    20. 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.

    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.