Home > Research > Publications & Outputs > Exploiting sparsity in pricing routines for the...

Research

Electronic data

Links

Text available via DOI:

Keywords

View graph of relations

Exploiting sparsity in pricing routines for the capacitated arc routing problem

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

Published

Standard

Exploiting sparsity in pricing routines for the capacitated arc routing problem. / Letchford, A N; Oukil, A.
In: Computers and Operations Research, Vol. 36, No. 7, 2009, p. 2320-2327.

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

Harvard

Letchford, AN & Oukil, A 2009, 'Exploiting sparsity in pricing routines for the capacitated arc routing problem', Computers and Operations Research, vol. 36, no. 7, pp. 2320-2327. https://doi.org/10.1016/j.cor.2008.09.008

APA

Letchford, A. N., & Oukil, A. (2009). Exploiting sparsity in pricing routines for the capacitated arc routing problem. Computers and Operations Research, 36(7), 2320-2327. https://doi.org/10.1016/j.cor.2008.09.008

Vancouver

Letchford AN, Oukil A. Exploiting sparsity in pricing routines for the capacitated arc routing problem. Computers and Operations Research. 2009;36(7):2320-2327. doi: 10.1016/j.cor.2008.09.008

Author

Letchford, A N ; Oukil, A. / Exploiting sparsity in pricing routines for the capacitated arc routing problem. In: Computers and Operations Research. 2009 ; Vol. 36, No. 7. pp. 2320-2327.

Bibtex

@article{02bf61e159eb44de8444d1f8a57d594a,
title = "Exploiting sparsity in pricing routines for the capacitated arc routing problem",
abstract = "The capacitated arc routing problem (CARP) is a well-known and fundamental vehicle routing problem. A promising exact solution approach to the CARP is to model it as a set covering problem and solve it via branch-cut-and-price. The bottleneck in this approach is the pricing (column generation) routine. In this paper, we note that most CARP instances arising in practical applications are defined on sparse graphs. We show how to exploit this sparsity to yield faster pricing routines. Extensive computational results are given.",
keywords = "arc routing, column generation, branch-cut-and-price",
author = "Letchford, {A N} and A Oukil",
year = "2009",
doi = "10.1016/j.cor.2008.09.008",
language = "English",
volume = "36",
pages = "2320--2327",
journal = "Computers and Operations Research",
issn = "0305-0548",
publisher = "Elsevier Ltd",
number = "7",

}

RIS

TY - JOUR

T1 - Exploiting sparsity in pricing routines for the capacitated arc routing problem

AU - Letchford, A N

AU - Oukil, A

PY - 2009

Y1 - 2009

N2 - The capacitated arc routing problem (CARP) is a well-known and fundamental vehicle routing problem. A promising exact solution approach to the CARP is to model it as a set covering problem and solve it via branch-cut-and-price. The bottleneck in this approach is the pricing (column generation) routine. In this paper, we note that most CARP instances arising in practical applications are defined on sparse graphs. We show how to exploit this sparsity to yield faster pricing routines. Extensive computational results are given.

AB - The capacitated arc routing problem (CARP) is a well-known and fundamental vehicle routing problem. A promising exact solution approach to the CARP is to model it as a set covering problem and solve it via branch-cut-and-price. The bottleneck in this approach is the pricing (column generation) routine. In this paper, we note that most CARP instances arising in practical applications are defined on sparse graphs. We show how to exploit this sparsity to yield faster pricing routines. Extensive computational results are given.

KW - arc routing

KW - column generation

KW - branch-cut-and-price

U2 - 10.1016/j.cor.2008.09.008

DO - 10.1016/j.cor.2008.09.008

M3 - Journal article

VL - 36

SP - 2320

EP - 2327

JO - Computers and Operations Research

JF - Computers and Operations Research

SN - 0305-0548

IS - 7

ER -