Sliced Neighborhood Search

The integration of tree search and metaheuristic techniques for the solution of combinatorial optimization problems is a research area widely explored in the last decade. We propose a search strategy called Sliced Neighborhood Search, SNS, that iteratively explores slices of large neighborhoods of an incumbent solution by performing constraint programming tree search (along with constraint propagation). SNS encloses concepts from metaheuristic techniques. SNS can be used both as a stand alone search strategy, and embedded in other strategies as intensification and diversification mechanism. We provide an extensive experimental evaluation of SNS on hard instances of the Asymmetric Traveling Salesman Problem with Time Windows. We show the effectiveness of SNS as a stand alone strategy when compared to Limited Discrepancy Search and of SNS when included in a heuristic framework such as the constraint programming based local branching.