ABSTRACT

LOCAL SEARCH USING NEIGHBOURHOODS OF EXPONENTIAL SIZE

Prof. Chris Potts, Department of Mathematics, University of Southampton

A new neighbourhood search technique is introduced that uses dynamic programming to search an exponential size neighbourhood in polynomial time. This technique is called dynasearch. We apply dynasearch to two types of sequencing problems; the total weighted tardiness scheduling problem, and the travelling salesman problem. Computational results show that, for restarts close to previous local minima, dynasearch is significantly more effective than classical first improve or best improve descent. As a consequence, our proposed algorithms use dynsearch with an iterated local search framework, where each descent is started a few random moves away from previous local minima. Computational results show that the proposed dynasearch algorithms are more effective than other known local search heuristics for the total weighted tardiness problem, and are competitive with other methods for the travelling salesman problem.

Maintained by rbennett@cs.ucl.ac.uk