Submitted manuscript, 346 KB, PDF document
Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
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 -