Adaptive large neighborhood search algorithm for the rural postman problem with time windows. Issue 1 (21st June 2017)

• Record Type: Journal Article
• Authors: Monroy‐Licht, Marcela; Amaya, Ciro Alberto; Langevin, André
• Is Part Of: Networks. Volume 70:Issue 1(2017)
• Page Start: 44
• Page End: 59
• Publication Date: 2017-06-21
• Subjects: rural postman problem -- time windows -- adaptive large neighborhood search -- metaheuristics; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21747
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract : The rural postman problem with time windows is the problem of serving some required edges with one vehicle; the vehicle must visit these edges during established time windows. This article presents a competitive adaptive large neighborhood search algorithm to solve the problem. Computational experiments are performed on a large set of instances with up to 104 required edges. The results show that this approach is efficient, significantly reducing the computational time on large instances and achieving good solutions: the algorithm is able to solve to optimality 224 of 232 instances. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 70(1), 44–59 2017