Combining Neighborhood-based Heuristics: A Framework and Pilot Study on Baselines

Abstract

In this paper, we propose an algorithmic framework for combining multiple neighborhood-based heuristics. An algorithm derived from this framework will function by chaining the heuristics in a pipelined fashion. Conceptually, this framework is an algorithmic template that contains two pieces of changeable components: 1) the policy H for selecting heuristics, and 2) the policy L for choosing the length of the pipeline that chains the selected heuristics. In this paper, we will first offer a theoretical discussion on the design of the policy L, and provide empirical evidence showing the effectiveness of the derived algorithm. We will then briefly touch on the issue of designing the policy H at the end of this paper, and demonstrate a simple pruning strategy and how it can contribute positively to the performance of the algorithm.