Exploiting sparsity in pricing routines for the capacitated arc routing problem

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) routi...

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 2009-07, Vol.36 (7), p.2320-2327
Main Authors: Letchford, Adam N., Oukil, Amar
Format: Article
Language:English
Subjects:
Applied sciences
Arc routing
Bottlenecks
Branch & bound algorithms
Branch-cut-and-price
Column generation
Exact sciences and technology
Graph theory
Logistics
Mathematical programming
Operational research and scientific management
Operational research. Management science
Routing
Sparsity
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0305-0548
1873-765X
0305-0548
DOI:10.1016/j.cor.2008.09.008