In situations with typically lots of dense jobs and vehicles, it's possible that we sometime produce solutions with route crossings. I've noticed this in both real-life and benchmark instances. On some instances, I've confirmed that those crossings are indeed sub-optimal (not required by e.g. timing constraints) and that re-ordering jobs by solving a route-level TSP does produce a (better) crossing-free route.

While we usually happily live with producing sub-optimal solutions, it's bad when there's an obvious move that improves our solution. The thing is we don't have a classical 2-opt move operating on a single route. The TwoOpt and ReverseTwoOpt moves we have are meant to mend crosses between two different routes.

We should implement such a LS operator and evaluate it's impact on both solution quality and computing times.