Computational study of neighborhood operator performance on the Traveling Salesman Problem with Time Windows in neighborhood search based frameworks (RTS, VNS)

In this work we analyze the performance of different neighborhood operators in terms of solution quality in different neighborhood search based frameworks, namely Reactive Tabu Search and Variable Neighborhood Search, on the Traveling Salesman Problem with Time Windows. We compare the impact of the two different search concepts on the solution quality by embedding the same operators and hence be able to precisely state the impact of the basic concept. Additionally, we analyze the improvement of those search strategies compared to a simple local search procedure. The neighborhood operators under consideration are 1-shift, nodeexchange, lexicographic 2-opt, lexicographic 3-opt and or-opt.