Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - The general routing polyhedron
T2 - a unifying framework
AU - Letchford, A. N.
PY - 1999/1/1
Y1 - 1999/1/1
N2 - It is shown how to transform the General Routing Problem (GRP) into a variant of the Graphical Travelling Salesman Problem (GTSP). This transformation yields a projective characterisation of the GRP polyhedron. Using this characterisation, it is shown how to convert facets of the GTSP polyhedron into valid inequalities for the GRP polyhedron. The resulting classes of inequalities subsume several previously published classes.
AB - It is shown how to transform the General Routing Problem (GRP) into a variant of the Graphical Travelling Salesman Problem (GTSP). This transformation yields a projective characterisation of the GRP polyhedron. Using this characterisation, it is shown how to convert facets of the GTSP polyhedron into valid inequalities for the GRP polyhedron. The resulting classes of inequalities subsume several previously published classes.
KW - arc routing problems
KW - polyhedral combinatorics
KW - polyhedra
KW - Valid inequalities
KW - General routing problem
U2 - 10.1016/S0377-2217(97)00377-9
DO - 10.1016/S0377-2217(97)00377-9
M3 - Journal article
VL - 112
SP - 122
EP - 133
JO - European Journal of Operational Research
JF - European Journal of Operational Research
SN - 0377-2217
IS - 1
ER -