  Neighborhood search is a cornerstone of state-of-the-art traveling salesman
and vehicle routing metaheuristics. While neighborhood exploration procedures
are well developed for problems with individual services, their counterparts
for one-to-one pickup-and-delivery problems have been more scarcely studied. A
direct extension of classic neighborhoods is often inefficient or complex due
to the necessity of jointly considering service pairs. To circumvent these
issues, we introduce major improvements to existing neighborhood searches for
the pickup-and-delivery traveling salesman problem and new large neighborhoods.
We show that the classical Relocate-Pair neighborhood can be fully explored in
$O(n^2)$ instead of $O(n^3)$ time. We adapt the 4-Opt and Balas-Simonetti
neighborhoods to consider precedence constraints. Moreover, we introduce an
exponential-size neighborhood called 2k-Opt, which includes all solutions
generated by multiple nested 2-Opts and can be searched in $O(n^2)$ time using
dynamic programming. We conduct extensive computational experiments,
highlighting the significant contribution of these new neighborhoods and
speed-up strategies within two classical metaheuristics. Notably, our approach
permits to repeatedly solve small pickup-and-delivery problem instances to
optimality or near-optimality within milliseconds, and therefore it represents
a valuable tool for time-critical applications such as meal delivery or
mobility on demand.
