A compact transformation of arc routing problems into node routing problems

Les Foulds (), Humberto Longo () and Jean Martins ()

Annals of Operations Research, 2015, vol. 226, issue 1, 177-200

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

Keywords: Graph transformation; Arc routing; Node routing; CARP; CVRP (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-014-1732-1 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:226:y:2015:i:1:p:177-200:10.1007/s10479-014-1732-1

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-014-1732-1

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().