On the Distance-Constrained Generalized Directed Rural Postman Problem

Autores UPV
Año
CONGRESO On the Distance-Constrained Generalized Directed Rural Postman Problem

Abstract

The Generalized Directed Rural Postman Problem (GDRPP) is an arc routing problem with some interesting real-life applications, such as routing for meter reading. In this problem, we have a family of arc subsets and the goal is to find a minimal cost tour traversing an arc in each subset. The Distance-Constrained GDRPP is a generalization of this problem in which a fleet of identical vehicles is available and the goal is to minimize the sum of the costs of all the routes, provided that no route exceeds a maximum distance. In this talk we introduce and compare several formulations for this problem. Moreover, different families of valid inequalities are proposed. Some results with preliminary branch-and-cut algorithms are reported.