An approach to the asymmetric multi-depot capacitated arc routing problem

•The directed multidepot capacitated arc routing problem is addressed.•An MILP formulation and some valid inequalities that can be used to tighten its LP-relaxation are proposed.•A branch-and-cut approach for solving the problem exactly is presented.•A numerical study exploring the properties of the...

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 2015-07, Vol.244 (1), p.100-109
Main Authors: Krushinsky, Dmitry, Van Woensel, Tom
Format: Article
Language:English
Subjects:
Arc routing
Asymmetry
Branch-and-cut
Broken symmetry
Carp
Concentrates
Inequalities
Mathematical models
Mathematical problems
Numerical analysis
Operational research
Route optimization
Routing
Studies
Symmetry
Transportation problem (Operations research)
Valid inequalities
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 directed multidepot capacitated arc routing problem is addressed.•An MILP formulation and some valid inequalities that can be used to tighten its LP-relaxation are proposed.•A branch-and-cut approach for solving the problem exactly is presented.•A numerical study exploring the properties of the multidepot version of the problem and of the proposed approach is reported. Despite the fact that the Capacitated Arc Routing Problems (CARPs) received substantial attention in the literature, most of the research concentrates on the symmetric and single-depot version of the problem. In this paper, we fill this gap by proposing an approach to solving a more general version of the problem and analysing its properties. We present an MILP formulation that accommodates asymmetric multi-depot case and consider valid inequalities that may be used to tighten its LP relaxation. A symmetry breaking scheme for a single-depot case is also proposed. An extensive numerical study is carried to investigate the properties of the problem and the proposed solution approach.
ISSN:0377-2217
1872-6860
DOI:10.1016/j.ejor.2015.01.005