Renaud De Landtsheer, Gustavo Ospina, Fabian Germeau, Thomas Fayolle, A Time Window Constraint for Local Search, ORBEL33, Hasselt, February 7-8, 2019
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.