The Hierarchical Mixed Rural Postman Problem

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 Rura...

Full description

Saved in:
Bibliographic Details
Published in:Transportation science 2017-05, Vol.51 (2), p.755-770
Main Authors: Colombi, Marco, Corberán, Ángel, Mansini, Renata, Plana, Isaac, Sanchis, José M.
Format: Article
Language:English
Subjects:
Algorithms
Analysis
Diversification
Exact solutions
Graph theory
Heuristic
hierarchy
mixed graph
Postal service
Problem solving
Rural areas
rural postman problem
Search algorithms
Tabu search
Transportation problem (Operations research)
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: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.
ISSN:0041-1655
1526-5447
DOI:10.1287/trsc.2016.0686