VROOM-Project
Use TSP solving at route level with non-binding constraints
I've encountered situations where a single-vehicle problem is submitted with (non-binding) capacity and time window constraints. Because of the constraints, we don't solve such an input using the TSP code, but with our default basic heuristic. This results in solutions that are usually slightly poorer since the TSP code is somehow more efficient in a non-constrained setup.
This extends to the situation where e.g. the timing constraints are actually binding but the resulting heuristic route would be still valid (and better) when running a TSP on the matching subset of jobs. For example if all jobs in a route have similar wide TW and the corresponding TSP solution is better, then the resulting route will also be valid wrt TW.
This even extends to most multiple-vehicle instances where job TW constraints (binding or not) are somehow similar, in particular all CVRP instances.
A first simple step would be to spot those situations and then try "straightening up" routes after the heuristic process by running route-level TSP. I have no idea how efficient/sufficient this would be, another option could be to use the "straightening" step as a single-route operator in the local search process, but this may be too costly.
Also as a side effect of improving the heuristic solutions, the whole local search process may be faster on average.