The Hierarchical Mixed Rural Postman Problem

Marco Colombi (), Ángel Corberán (), Renata Mansini (), Isaac Plana () and José M. Sanchis ()
Additional contact information
Marco Colombi: Department of Information Engineering, University of Brescia, 25123 Brescia, Italy
Ángel Corberán: Department of Statistics and Operational Research, University of Valencia, 46100 Burjassot, Valencia, Spain
Renata Mansini: Department of Information Engineering, University of Brescia, 25123 Bresica, Italy
Isaac Plana: Department of Mathematics for Economics and Business, University of Valencia, 46100 Burjassot, Valencia, Spain
José M. Sanchis: Department of Applied Mathematics, Polytechnic University of Valencia, 46100 Burjassot, Valencia, Spain

Transportation Science, 2017, vol. 51, issue 2, 755-770

Abstract: In this paper, we study a generalization of the Hierarchical Chinese Postman Problem on a mixed graph where only a subset of arcs and edges require a service to be accomplished following a hierarchical order. The problem, called the Hierarchical Mixed Rural Postman Problem, also generalizes the Rural Postman Problem and thus is NP-hard. We propose a new mathematical formulation, and introduce two effective solution algorithms. The first procedure is a matheuristic that is based on the exact solution of a variant of the Mixed Rural Postman Problem for each hierarchy. The second approach is a tabu search algorithm based on different improvement and diversification strategies. Computational results on an extended set of instances show how the proposed solution methods are quite effective and efficient when compared to the solutions of a branch-and-cut algorithm stopped after one hour of computation.

Keywords: hierarchy; mixed graph; rural postman problem (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
https://doi.org/10.1287/trsc.2016.0686 (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:51:y:2017:i:2:p:755-770

Access Statistics for this article

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