Portal de Periódicos da CAPES

The Rural Postman Problem with time windows

2014; Wiley; Volume: 64; Issue: 3 Linguagem: Inglês

10.1002/net.21569

1097-0037

Marcela Monroy‐Licht, Ciro Alberto Amaya, André Langevin,

Optimization and Packing Problems

NetworksVolume 64, Issue 3 p. 169-180 Research Article The Rural Postman Problem with time windows Marcela Monroy-Licht, Marcela Monroy-Licht Département de Mathématiques et de Génie Industriel, École Polytechnique de Montréal, Quebec, Canada Centre Interuniversitaire de Recherche, sur les Réseaux d'Entreprises, la Logistique et le Transport (CIRRELT), Montréal, Quebec, CanadaSearch for more papers by this authorCiro Alberto Amaya, Ciro Alberto Amaya Departamento de Ingeniería Industrial, Universidad de Los Andes, Bogotá, ColombiaSearch for more papers by this authorAndré Langevin, Corresponding Author André Langevin Département de Mathématiques et de Génie Industriel, École Polytechnique de Montréal, Quebec, Canada Centre Interuniversitaire de Recherche, sur les Réseaux d'Entreprises, la Logistique et le Transport (CIRRELT), Montréal, Quebec, CanadaCorrespondence to: A. Langevin; e-mail: [email protected]Search for more papers by this author Marcela Monroy-Licht, Marcela Monroy-Licht Département de Mathématiques et de Génie Industriel, École Polytechnique de Montréal, Quebec, Canada Centre Interuniversitaire de Recherche, sur les Réseaux d'Entreprises, la Logistique et le Transport (CIRRELT), Montréal, Quebec, CanadaSearch for more papers by this authorCiro Alberto Amaya, Ciro Alberto Amaya Departamento de Ingeniería Industrial, Universidad de Los Andes, Bogotá, ColombiaSearch for more papers by this authorAndré Langevin, Corresponding Author André Langevin Département de Mathématiques et de Génie Industriel, École Polytechnique de Montréal, Quebec, Canada Centre Interuniversitaire de Recherche, sur les Réseaux d'Entreprises, la Logistique et le Transport (CIRRELT), Montréal, Quebec, CanadaCorrespondence to: A. Langevin; e-mail: [email protected]Search for more papers by this author First published: 07 October 2014 https://doi.org/10.1002/net.21569Citations: 3Read the full textAboutPDF ToolsRequest permissionExport citationAdd to favoritesTrack citation ShareShare Give accessShare full text accessShare full-text accessPlease review our Terms and Conditions of Use and check box below to share full-text version of article.I have read and accept the Wiley Online Library Terms and Conditions of UseShareable LinkUse the link below to share a full-text version of this article with your friends and colleagues. Learn more.Copy URL Share a linkShare onFacebookTwitterLinkedInRedditWechat Abstract 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 Citing Literature Volume64, Issue3October 2014Pages 169-180 RelatedInformation