Comparison of Approximate Approaches to Solving the Travelling Salesman Problem and its Application to UAV Swarming

Cohen, Kelly; Boone, Nathan; Sathyan, Anoop

Comparison of approximate approaches to solving the Travelling Salesman Problem and its application to UAV swarming. International Journal of Unmanned Systems Engineering. 3(1): 1-16. The Travelling Salesman Problem (TSP) is a widely researched Non-deterministic Polynomial-time hard optimization problem with a range of important applications in a wide spectrum of disciplines including aerospace engineering. In this paper, a comparison of different approaches to solve the TSP and also its application towards swarming of UAVs is considered. The objective of the TSP is to determine the optimal route associated with the shortest tour connecting all targets just once. Genetic Algorithms (GA) are one of the most widely applied techniques for solving this class of optimization problems. Two other techniques, 2-opt and Particle Swarm Optimization, are used and the results are compared with those obtained using GA. The comparison is made for different numbers of targets, using salient figures of merit such as computational time required and the cost function which is the minimum solution (distance) obtained. Results show that the 2-opt approach with the closest neighbour as initial starting point for the search yields superior performance. In the Multiple Travelling Salesman Problem, we propose a cluster-first approach which allocates each specific UAV to a subset of targets. The 200 targets are divided into four clusters corresponding to the four UAVs and then TSP algorithms like 2-opt and GA are employed to solve each cluster. This approach drastically reduces the computational time and also gives much better results than the conventional technique of directly applying GA over the 200 targets.

Creator

License

Submitter

Kelly Cohen

College