A Time Window Constraint for Local Search

A Time Window Constraint for Local Search

Abstract

This paper introduces a global time windows constraint for the vehicles routing problems in local search optimisation. It relies on pre-computed values and achieves O(1) -time complexity on traditional routing neighbourhoods (1-opt,2-opt,3-opt), and scales to more complex ones.

The pre-computation has O(n²) -time complexity, making our approach practical on neighbourhoods with at least O(n²) neighbours to explore (2-opt,3-opt). This contribution is included in the LGPL OscaR.CBLS engine.