12,000

We have over 12,000 students, from over 100 countries, within one of the safest campuses in the UK

93%

93% of Lancaster students go into work or further study within six months of graduating

Home > Research > Publications & Outputs > Exploiting sparsity in pricing routines for the...
View graph of relations

« Back

Exploiting sparsity in pricing routines for the capacitated arc routing problem

Research output: Contribution to journalJournal article

Published

Journal publication date2009
JournalComputers and Operations Research
Journal number7
Volume36
Number of pages8
Pages2320-2327
Original languageEnglish

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.