Article ID: | iaor20173085 |
Volume: | 65 |
Issue: | 4 |
Start Page Number: | 992 |
End Page Number: | 1010 |
Publication Date: | Aug 2017 |
Journal: | Operations Research |
Authors: | Vidal Thibaut |
Keywords: | combinatorial optimization, decision, graphs, heuristics, programming: dynamic, vehicle routing & scheduling |
This article explores a structural neighborhood decomposition for arc routing problems, in which the decisions about traversal orientations during services are made optimally as part of neighbor evaluation procedures. Using memory structures, bidirectional dynamic programming, and lower bounds, we show that a large neighborhood involving classical moves on the sequences of services along with optimal orientation decisions can be searched in amortized