An Exact Algorithm for the Capacitated Arc Routing Problem with Deadheading Demand

Enrico Bartolini (), Jean-François Cordeau () and Gilbert Laporte ()
Additional contact information
Enrico Bartolini: HEC Montréal, and Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT), Montréal, Quebec H3T 2A7, Canada
Jean-François Cordeau: HEC Montréal, and Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT), Montréal, Quebec H3T 2A7, Canada
Gilbert Laporte: HEC Montréal, and Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT), Montréal, Quebec H3T 2A7, Canada

Operations Research, 2013, vol. 61, issue 2, 315-327

Abstract: We study an extension of the capacitated arc routing problem (CARP) called the capacitated arc routing problem with deadheading demand (CARPDD). This problem extends the classical capacitated arc routing problem by introducing an additional capacity consumption incurred by a vehicle deadheading an edge. It can be used, e.g., to model time or distance constrained arc routing problems. We show that the strongest CARP lower bounds can be weak when directly applied to the CARPDD, and we introduce a new family of valid inequalities shown to significantly strengthen these bounds. We develop an exact algorithm for the CARPDD based on cut-and-column generation and branch and price, and we report extensive computational results on a large set of benchmark instances. The same exact algorithm is also tested on classical CARP benchmark sets and is shown to improve upon the best known exact algorithms for the CARP.

Keywords: capacitated arc routing problem; double demand; cut-and-column generation; branch and price (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1120.1154 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:61:y:2013:i:2:p:315-327

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().