Fuzzy Clustering Based Genetic Algorithm for the Multi-Depot Polygon Visiting Dubins Multiple Traveling Salesman Problem

Abstract

A genetic algorithm (GA) and Fuzzy Logic System (FLS) based approach to the path representation of a variant of the Traveling Salesman Problem (TSP), the Multi-Depot Polygon Visiting Dubins Multiple Traveling Salesman Problem (MDPVDMTSP) is presented. Utilizing a hybridization of control techniques, this work effectively and efficiently approximates path planning and visbility problems encountered by a UAV swarm in the constant altitude, constant velocity, two-dimensional case. Benchmarking capabilities only exist for a 20 polygon PVDTSP case (1 UAV), but for this case a 9.8% increase in accuracy along with an order of magnitude decrease in run-time was found compared to the alternative method, despite utilizing a slower computer and programming language. Over 100 runs, the best solution was found 99% of the times, with a 1% chance of settling to a local minima. Comparison opportunities for MDPVDMTSP’s are currently not present, but the algorithms work similarly well for this scenario. MDPVDMTSP’s with 250 polygons, 20 UAV’s, and 4 different depots can be accurately approximated in under 30 seconds on the same machine. Being a combination of approximate methods, a decrease in run-time was expected, however the accuracy of this work shows great future promise for more complex variants of this problem.