Scientific Program > Talks by Speaker > Reula Martín Miguel

Arc routing problems consist of finding one or several routes traversing a given set of arcs and/or edges that must be served. The Close-Enough Arc Routing Problem (CEARP), also known as Generalized Directed Rural Postman Problem, considers that each costumer is not located in a specfic arc, but can be served whenever the vehicle traverses any arc of a prefixed subset. The idea is that each customer is served when the vehicle gets closer than a certain distance. Some examples of real-life applications include routing for meter reading. A vehicle with a receiver travels through a series of neighborhoods. If the vehicle gets within a certain distance of a meter, the receiver can record the consumption. Therefore, the vehicle does not need to traverse every street, but only a few, in order to be close enough to each meter. In this paper we deal with an extension of this problem, the Distance-Constrained Close Enough Arc Routing Problem, in which a fleet of vehicles is available. The vehicles have to leave from and return to the depot, and the length of their routes must not exceed a maximum distance.
We propose a formulation for this problem and study a relaxation of its associated polyhedron. We present some families of valid inequalities that we use in the implementation of a branch-and-cut algorithm for solving the problem. Computational experiments have been performed on a set of benchmark instances and the results are compared with those obtained with the algorithms proposed in the Literature.