Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
475355 | Computers & Operations Research | 2009 | 8 Pages |
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
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Adam N. Letchford, Amar Oukil,