A New Branch-and-Cut Algorithm for the Generalized Directed Rural Postman Problem

Thais Ávila (), Ángel Corberán (), Isaac Plana () and José M. Sanchis ()
Additional contact information
Thais Ávila: Departamento d’Estadística i Investigació Operativa, Universitat de València, 46100 Valencia, Spain
Ángel Corberán: Departamento d’Estadística i Investigació Operativa, Universitat de València, 46100 Valencia, Spain
Isaac Plana: Departamento de Matemáticas para la Economía y la Empresa, Universitat de València, 46010 Valencia, Spain
José M. Sanchis: Departamento de Matemática Aplicada, Universidad Politécnica de València, 46022 Valencia, Spain

Transportation Science, 2016, vol. 50, issue 2, 750-761

Abstract: The generalized directed rural postman problem, also known as the close-enough arc routing problem, is an arc routing problem with some interesting real-life applications, such as routing for meter reading. In this article we introduce two new formulations for this problem as well as various families of new valid inequalities that are used to design and implement a branch-and-cut algorithm. The computational results obtained on test bed instances from the literature show that this algorithm outperforms the existing exact methods.

Keywords: generalized rural postman problem; close-enough arc routing problem; branch-and-cut (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2015.0588 (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:ortrsc:v:50:y:2016:i:2:p:750-761

Access Statistics for this article

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