We propose in this paper a novel way of looking at local search algorithms for combinatorial optimization problems which better suits constraint programming by performing branch-and-bound search at their core. We concentrate on neighborhood exploration and show how the framework described yields a more efficient local search and opens the door to more elaborate neighborhoods. Numerical results are given in the context of the traveling salesman problem with time windows. This work on neighborhood exploration is part of ongoing research to develop constraint programming tabu search algorithms applied to routing prob-lems.
展开▼