A tabu search with gradual evolution process

•The paper investigates a new framework for executing tabu search (TS).•The framework changes the nature of the problem dynamically during optimization run.•The basic idea is inspired by the recent viral transmission incidents.•Numerical experiments showed interesting results.

We investigate a new framework for executing tabu search (TS). A unique aspect of this framework is that it performs multiple small-scale TS runs iteratively to identify the most promising area of the feasible region before executing the final TS run. The basic idea is inspired by recent viral transmission incidents, which showed that a virus would often go through an indirect and gradual evolution process to transform itself into a new form. Numerical experiments conducted with randomly-generated vehicle routing instances demonstrate interesting results.