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 Hierarchical Mixed Rural Postman Problem (HMRPP), 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 which 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.

The Hierarchical Mixed Rural Postman Problem

COLOMBI, Marco;MANSINI, Renata;
2017-01-01

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 Hierarchical Mixed Rural Postman Problem (HMRPP), 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 which 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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11379/465518
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 4
social impact