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)
|