We introduce a structural problem decomposition for arc routing problems, in which the decisions about edge traversal directions, during service, are made optimally as part of a route-evaluation procedure. Using memory structures, bidirectional dynamic programming, and lower bounds, we show that a combined neighborhood involving classical moves on the sequences of services, and optimal decisions on the other decision sets, can be explored with amortized O(1) time per move. Due to its generality and simplicity, the approach is applied to multiple variants of arc routing problems, extended into large-scale neighborhood searches such as ejection chains, and integrated into two classical metaheuristic frameworks. Our computational experiments with these methods lead to solutions of exceptional quality on all classical benchmark sets, with a total of 670 instances. We also report additional sensitivity analyses on new node, edge and arc routing instances with turn penalties, which are uncommonly challenging yet critical for multiple practical applications.
Mots clés : Arc routing, Turn penalties, Structural problem decomposition, Local search, Large neighborhood search