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

Chung-Yao Chuang and Stephen F. Smith
Tech. Report, CMU-RI-TR-19-04, December, 2018

Download Publication

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.


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.

author = {Chung-Yao Chuang and Stephen F. Smith},
title = {Combining Neighborhood-based Heuristics: A Framework and Pilot Study on Baselines},
year = {2018},
month = {December},
institution = {Carnegie Mellon University},
address = {Pittsburgh, PA},
number = {CMU-RI-TR-19-04},
} 2019-06-28T12:24:04-04:00