6533b7d1fe1ef96bd125cc8d
RESEARCH PRODUCT
The Hierarchical Mixed Rural Postman Problem: Polyhedral analysis and a branch-and-cut algorithm
Marco ColombiÁNgel CorberánIsaac PlanaRenata MansiniJosé M. Sanchissubject
Information Systems and ManagementHierarchical Routing ProblemsGeneral Computer Science0211 other engineering and technologiesMixed graph02 engineering and technologyManagement Science and Operations ResearchIndustrial and Manufacturing EngineeringCombinatorics0502 economics and businessOrder (group theory)Mixed Rural Postman ProblemPolyhedral analysisBranch-and-cut Hierarchical Routing Problems Mixed Rural Postman Problem Polyhedral analysis Modeling and Simulation Management Science and Operations Research Information Systems and ManagementMathematicsDiscrete mathematics050210 logistics & transportation021103 operations research05 social sciencesBranch-and-cutModeling and SimulationBenchmark (computing)Polyhedral analysisMATEMATICA APLICADABranch and cutAlgorithmdescription
[EN] The Hierarchical Mixed Rural Postman Problem is defined on a mixed graph where arcs and edges that require a service are divided into clusters' that have to be serviced in a hierarchical order. The problem generalizes the Mixed Rural Postman Problem and thus is NP-hard. In this paper, we provide a polyhedral analysis of the problem and propose a branch-and-cut algorithm for its solution based on the introduced classes of valid inequalities. Extensive computational experiments are reported on benchmark instances. The exact approach allows to find the optimal solutions in less than 1 hour for instances with up to 999 vertices, 2678 links, and five clusters.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2017-02-01 | European Journal of Operational Research |