IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v226y2015i1p177-20010.1007-s10479-014-1732-1.html
   My bibliography  Save this article

A compact transformation of arc routing problems into node routing problems

Author

Listed:
  • Les Foulds
  • Humberto Longo
  • Jean Martins

Abstract

We describe a compact method to transform arc routing problem instances into node routing problem instances. Any node routing problem instance thus created must be solved by a branch-and-price process, such as the one described in this paper. The purpose is to make the number of nodes in the resulting transformed graphs greater by only one unit than the number $$r$$ r of required arcs (arcs having demand) in the original graph, that is, $$r+1$$ r + 1 nodes. This low increase in the number of nodes represents an improvement compared to the methods previously presented by Pearn, Assad and Golden ( $$3r+1$$ 3 r + 1 nodes) and by Longo, Poggi de Aragão and Uchoa and also by Baldacci and Maniezzo ( $$2r+1$$ 2 r + 1 nodes). Using an adapted version of an existing branch-cut-and-price algorithm for a capacitated node routing problem on the transformed graph results in an effective approach for a capacitated arc routing problem. Computational experiments using this approach produced useful lower bounds in reasonable computational time for many challenging numerical instances from the literature. Additionally, some such previously open instances were solved to optimality for the first time. Copyright Springer Science+Business Media New York 2015

Suggested Citation

  • 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.
    • Handle: RePEc:spr:annopr:v:226:y:2015:i:1:p:177-200:10.1007/s10479-014-1732-1
    DOI: 10.1007/s10479-014-1732-1
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-014-1732-1
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-014-1732-1?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. G. B. Dantzig & J. H. Ramser, 1959. "The Truck Dispatching Problem," Management Science, INFORMS, vol. 6(1), pages 80-91, October.
    2. 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.
    3. 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.
    4. Moshe Dror, 1994. "Note on the Complexity of the Shortest Path Models for Column Generation in VRPTW," Operations Research, INFORMS, vol. 42(5), pages 977-978, 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. 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.
    2. Merve Cengiz Toklu, 2023. "A fuzzy multi-criteria approach based on Clarke and Wright savings algorithm for vehicle routing problem in humanitarian aid distribution," Journal of Intelligent Manufacturing, Springer, vol. 34(5), pages 2241-2261, June.
    3. Erfan Babaee Tirkolaee & Alireza Goli & Selma Gütmen & Gerhard-Wilhelm Weber & Katarzyna Szwedzka, 2023. "A novel model for sustainable waste collection arc routing problem: Pareto-based algorithms," Annals of Operations Research, Springer, vol. 324(1), pages 189-214, May.
    4. Zhang, Guowei & Jia, Ning & Zhu, Ning & Adulyasak, Yossiri & Ma, Shoufeng, 2023. "Robust drone selective routing in humanitarian transportation network assessment," European Journal of Operational Research, Elsevier, vol. 305(1), pages 400-428.

    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. Boschetti, Marco Antonio & Maniezzo, Vittorio & Strappaveccia, Francesco, 2017. "Route relaxations on GPU for vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 258(2), pages 456-466.
    2. 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.
    3. Dayarian, Iman & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2015. "A column generation approach for a multi-attribute vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 241(3), pages 888-906.
    4. 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.
    5. Pradhananga, Rojee & Taniguchi, Eiichi & Yamada, Tadashi & Qureshi, Ali Gul, 2014. "Bi-objective decision support system for routing and scheduling of hazardous materials," Socio-Economic Planning Sciences, Elsevier, vol. 48(2), pages 135-148.
    6. Bianchessi, N. & Mansini, R. & Speranza, M.G., 2014. "The distance constrained multiple vehicle traveling purchaser problem," European Journal of Operational Research, Elsevier, vol. 235(1), pages 73-87.
    7. Dollevoet, T.A.B. & Pecin, D. & Spliet, R., 2020. "The path programming problem and a partial path relaxation," Econometric Institute Research Papers EI-2020-04, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    8. Range, Troels Martin, 2013. "Exploiting Set-Based Structures to Accelerate Dynamic Programming Algorithms for the Elementary Shortest Path Problem with Resource Constraints," Discussion Papers on Economics 17/2013, University of Southern Denmark, Department of Economics.
    9. Leonardo Lozano & Daniel Duque & Andrés L. Medaglia, 2016. "An Exact Algorithm for the Elementary Shortest Path Problem with Resource Constraints," Transportation Science, INFORMS, vol. 50(1), pages 348-357, February.
    10. Schulz, Arne & Pfeiffer, Christian, 2024. "Using fixed paths to improve branch-and-cut algorithms for precedence-constrained routing problems," European Journal of Operational Research, Elsevier, vol. 312(2), pages 456-472.
    11. 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.
    12. Li, Jiliu & Xu, Min & Sun, Peng, 2022. "Two-echelon capacitated vehicle routing problem with grouping constraints and simultaneous pickup and delivery," Transportation Research Part B: Methodological, Elsevier, vol. 162(C), pages 261-291.
    13. Stefan Irnich & Guy Desaulniers & Jacques Desrosiers & Ahmed Hadjar, 2010. "Path-Reduced Costs for Eliminating Arcs in Routing and Scheduling," INFORMS Journal on Computing, INFORMS, vol. 22(2), pages 297-313, May.
    14. Miao Yu & Viswanath Nagarajan & Siqian Shen, 2022. "Improving Column Generation for Vehicle Routing Problems via Random Coloring and Parallelization," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 953-973, March.
    15. Asvin Goel & Stefan Irnich, 2017. "An Exact Method for Vehicle Routing and Truck Driver Scheduling Problems," Transportation Science, INFORMS, vol. 51(2), pages 737-754, May.
    16. Bulhões, Teobaldo & Hà, Minh Hoàng & Martinelli, Rafael & Vidal, Thibaut, 2018. "The vehicle routing problem with service level constraints," European Journal of Operational Research, Elsevier, vol. 265(2), pages 544-558.
    17. F. Errico & G. Desaulniers & M. Gendreau & W. Rei & L.-M. Rousseau, 2018. "The vehicle routing problem with hard time windows and stochastic service times," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 7(3), pages 223-251, September.
    18. Guy Desaulniers & Diego Pecin & Claudio Contardo, 2019. "Selective pricing in branch-price-and-cut algorithms for vehicle routing," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(2), pages 147-168, June.
    19. Qie He & Stefan Irnich & Yongjia Song, 2018. "Branch-Cut-and-Price for the Vehicle Routing Problem with Time Windows and Convex Node Costs," Working Papers 1804, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    20. Bhusiri, Narath & Qureshi, Ali Gul & Taniguchi, Eiichi, 2014. "The trade-off between fixed vehicle costs and time-dependent arrival penalties in a routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 62(C), pages 1-22.

    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:spr:annopr:v:226:y:2015:i:1:p:177-200:10.1007/s10479-014-1732-1. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.