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

Research

Associated organisational units

Electronic data

  • arps-and-matchings

    Accepted author manuscript, 386 KB, PDF document

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

Links

Text available via DOI:

Keywords

View graph of relations

On matchings, T-joins and arc routing problems

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

On matchings, T-joins and arc routing problems. / Boyacı, Burak; Dang, Thu; Letchford, Adam.
In: Networks, Vol. 79, No. 1, 31.01.2022, p. 20-31.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Boyacı, B, Dang, T & Letchford, A 2022, 'On matchings, T-joins and arc routing problems', Networks, vol. 79, no. 1, pp. 20-31. https://doi.org/10.1002/net.22033

APA

Boyacı, B., Dang, T., & Letchford, A. (2022). On matchings, T-joins and arc routing problems. Networks, 79(1), 20-31. https://doi.org/10.1002/net.22033

Vancouver

Boyacı B, Dang T, Letchford A. On matchings, T-joins and arc routing problems. Networks. 2022 Jan 31;79(1):20-31. Epub 2021 Mar 5. doi: 10.1002/net.22033

Author

Boyacı, Burak ; Dang, Thu ; Letchford, Adam. / On matchings, T-joins and arc routing problems. In: Networks. 2022 ; Vol. 79, No. 1. pp. 20-31.

Bibtex

@article{a68f4e1b445448b7985b67567903e450,
title = "On matchings, T-joins and arc routing problems",
abstract = "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.",
keywords = "vehicle routing, combinatorial optimisation",
author = "Burak Boyacı and Thu Dang and Adam Letchford",
year = "2022",
month = jan,
day = "31",
doi = "10.1002/net.22033",
language = "English",
volume = "79",
pages = "20--31",
journal = "Networks",
issn = "0028-3045",
publisher = "Blackwell-Wiley",
number = "1",

}

RIS

TY - JOUR

T1 - On matchings, T-joins and arc routing problems

AU - Boyacı, Burak

AU - Dang, Thu

AU - Letchford, Adam

PY - 2022/1/31

Y1 - 2022/1/31

N2 - 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.

AB - 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.

KW - vehicle routing

KW - combinatorial optimisation

U2 - 10.1002/net.22033

DO - 10.1002/net.22033

M3 - Journal article

VL - 79

SP - 20

EP - 31

JO - Networks

JF - Networks

SN - 0028-3045

IS - 1

ER -