Daniel Harabor
>>
Projects
>>
Local Search

Simple to state yet difficult to solve, the Travelling Salesman Problem (TSP) is one of the oldest in Computer Science. The objective is to compute a minimum cost tour of a set of cities without visiting any city twice (except the origin).

Known to be NP-Complete, there is very little hope of ever finding an efficient method to solve arbitrary TSPs optimally. In response, the academic community has focused much effort on developing local search methods that can compute "good enough" solutions in a short amount of time.

Goals

This project is concerned with the development of informed local search heuristics for solving the TSP. The main idea is to rank every successor state in a neighbourhood using a lower-bound on the cost of the best tour which is still reachable from that successor.

This approach is quite different from others in the literature where greedy "least-cost-move" heuristics are used to evaluate successor states.

Main Result

We develop the Constrained 1-Tree; an informed admissible heuristic which is able to guide a well known local search method to very high quality solutions in just a small number of iterations. The main idea is compute a 1-tree as an initial global lowerbound for the problem and then repair it as the search progresses, forcing the inclusion of some edges and the exclusion of others in order to retain the admissibility of the heuristic.

Further work on this project involves developing faster yet-still-informed heuristics to guide the search more quickly.

Resources

Harabor D. and Kilby P. 2011. Informed Heuristics for Guiding Stem-and-Cycle Ejection Chains. In arXiv:1103.3904.
(pdf)