Premium
The Rural Postman Problem with time windows
Author(s) -
MonroyLicht Marcela,
Amaya Ciro Alberto,
Langevin André
Publication year - 2014
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21569
Subject(s) - travelling salesman problem , computer science , set (abstract data type) , mathematical optimization , plane (geometry) , algorithm , mathematics , geometry , programming language
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. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 64(3), 169–180 2014