Approximation Algorithms and Heuristics for a Heterogeneous Traveling Salesman Problem

Abstract

Unmanned Vehicles (UVs) are developed for several civil and military applications. For these applications, there is a need for multiple vehicles with different capabilities to visit and monitor a set of given targets. In such scenarios, routing problems arise naturally where there is a need to plan paths in order to optimally use resources and time. The focus of this thesis is to address a basic optimization problem that arises in this setting.

We consider a routing problem where some targets have to be visited by specific vehicles. We approach this problem by dividing the routing into two sub problems: partitioning the targets while satisfying vehicle target constraints and sequencing. We solve the partitioning problem with the help of a minimum spanning tree algorithm. We use 3 different approaches to solve the sequencing problem; namely, the 2 approximation algorithm, Christofide's algorithm and the Lin - Kernighan Heuristic (LKH). The approximation algorithms were implemented in MATLAB. We also developed an integer programming (IP) model and a relaxed linear programming (LP) model in C with the help of Concert Technology for CPLEX, to obtain lower bounds.

We compare the performance of the developed approximation algorithms with both the IP and the LP model and found that the heuristic performed very well and provided the better quality solutions as compared to the approximation algorithms. It was also found that the approximation algorithms gave better solutions than the apriori guarantees.