Adaptive large neighborhood search algorithm for the rural postman problem with time windows

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 experim...

Full description

Saved in:
Bibliographic Details
Published in:Networks 2017-08, Vol.70 (1), p.44-59
Main Authors: Monroy‐Licht, Marcela, Amaya, Ciro Alberto, Langevin, André
Format: Article
Language:English
Subjects:
Adaptive algorithms
adaptive large neighborhood search
Algorithms
metaheuristics
Routing
rural postman problem
time windows
Windows (intervals)
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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
ISSN:0028-3045
1097-0037
DOI:10.1002/net.21747