| Article ID: | iaor201522263 |
| Volume: | 64 |
| Issue: | 3 |
| Start Page Number: | 169 |
| End Page Number: | 180 |
| Publication Date: | Oct 2014 |
| Journal: | Networks |
| Authors: | Langevin Andr, Amaya Ciro Alberto, Monroy-Licht Marcela |
| Keywords: | combinatorial optimization, networks, graphs |
The Rural Postman Problem with Time Windows for the undirected case is introduced. The problem occurs in the monitoring of roads for black‐ice detection. Different formulations are proposed and tested on sets of instances adapted from the literature. A cutting plane algorithm based on valid inequalities for the Traveling Salesman Problem (TSP) with Time Windows and the Precedence Constrained TSP is presented as solution method and tested on a set of real‐life networks. Computational results show that this approach is able to solve to optimality instances with up to 104 required edges. At the end of the article the formulations for the undirected case are extended to the directed case.