Dijous 18 de Setembre, 12:30 hores, Saló de Graus.
The Generalized Directed Rural Postman Problem (GDRPP), also known as the Close-Enough Arc Routing Problem, is an arc routing problem with some interesting real-life applications, such as routing for meter reading. In this application, a vehicle with a receiver travels through a series of neighborhoods. If the vehicle gets closer than a certain distance to a meter (customer), the receiver is able to record the gas, water, or electricity consumption. Therefore, the vehicle does not need to traverse every street, but only a few, in order to get close enough to each meter. Note that in most arc routing problems each customer must be serviced from exactly one street, and thus the goal is to find a route traversing all the streets in a given set. However, in the GDRPP each customer can be serviced from one or more streets, so the vehicle only needs to traverse one of them. In this talk we introduce two new formulations for this problem as well as various families of new valid inequalities that are used to design and implement a branch-and-cut algorithm. The computational results obtained on test bed instances from the literature show that this algorithm outperforms the existing exact methods.