Home > Research > Publications & Outputs > On matchings, T-joins and arc routing problems

Electronic data

  • arps-and-matchings

    Accepted author manuscript, 386 KB, PDF document

    Available under license: CC BY: Creative Commons Attribution 4.0 International License


Text available via DOI:

View graph of relations

On matchings, T-joins and arc routing problems

Research output: Contribution to Journal/MagazineJournal articlepeer-review

<mark>Journal publication date</mark>31/01/2022
Issue number1
Number of pages12
Pages (from-to)20-31
Publication StatusPublished
Early online date5/03/21
<mark>Original language</mark>English


Matchings and T-joins are fundamental and much-studied concepts in graph theory and combinatorial optimisation. One important application of matchings and T-joins is in the computation of strong lower bounds for Arc Routing Problems (ARPs). An ARP is a special kind of vehicle routing problem, in which the demands are located along edges or arcs, rather than at nodes. We point out that the literature on applying matchings and T-joins to ARPs does not fully exploit the structure of real-life road networks. We propose some ways to exploit this structure. Computational results show significant running time improvements, without deteriorating the quality of the lower bounds.