RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación
Artículo científico (JournalArticle)
A New Branch-and-Cut Algorithm for the Generalized Directed Rural Postman Problem
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, The authors wish to thank Minh Hoang Ha, Nathalie Bostel, Andre Langevin, and Louis-Martin Rousseau for providing their instances. The authors also thank the Spanish Ministerio de Economia y Competitividad [project MTM2012-36163-C06-02] and the Generalitat Valenciana [project GVPROMETEO2013-049] for their support.