| In this thesis, the close enough traveling salesman (CETSP) problem is considered. The classic traveling sales man (TSP) problem is well known; given a set of demand points possibly with an underlying graph structure, like a set of cities on a road map, the objective is to visit each point on a tour, while minimizing the total travel distance. This problem is known to be NP-Complete; the only known optimal algorithms require at least exponential time.;The Close Enough variant of this problem is relevant to tasks such as security monitoring. Rather than reaching an exact location, the requirement is only to come close to a given area: for example, a security guard on patrol might only need to view a position, rather than move through it.;We study this problem, and adapt approximation algorithms and heuristics for it. Three methods for solving TSP problems were implemented: brute force enumeration, a traditional approach based on dynamic programming, and a simple approximation algorithm based on spanning trees. These TSP solutions were then adapted for the CETSP variant, to evaluate how much impact an initial route had upon the final solution. Through a number of experiments, we have observed that the approximation algorithm quickly obtains good solutions; the results are typically very close to solutions derived from optimal TSP routes, but with much lower computing demands. |
