Improving the Performance of Multi-start Search on the Traveling Salesman Problem

Abstract. Constructive multi-start search algorithms are commonly used to address combinatorial optimization problems. Multi-start algorithms recover from local optima by restarting, which can lead to redundant configurations when search paths converge. In this paper, we investigate ways to minimize redundancy using record keeping and analyze several restart algorithms in the context of iterative hill climbing with applications to the traveling salesman problem. Experimental results identify the best performing restart algorithms