Various civil and military applications of UAVs, or ground robots, require a set of vehicles to monitor a group of targets. Routing problems naturally arise in this setting where the operators of the vehicles have to plan the paths suitably in order to optimize the use of resources available such as sensors, fuel etc. These vehicles may differ either in their structural (design and dynamics) or functional (sensing) capabilities. This thesis addresses an important routing problem involving two heterogeneous vehicles. As the addressed routing problem is NP-Hard, we develop an approximation algorithm and heuristics to solve the problem. Our approach involves dividing the routing problem into two sub-problems: Partitioning and Sequencing. Partitioning the targets involves finding two distinct sets of targets, each corresponding to one of the vehicles. We then find a sequence in which these targets need to be visited in order to optimize the use of resources to the maximum possible extent. The sequencing problem can be solved either by Christofides algorithm or the Lin-Kernighan Heuristic (LKH). The problem of partitioning is tackled by solving a Linear Program (LP) obtained by relaxing some of the constraints of an Integer Programming (IP) model for the problem. We observe the performance of two LP models for the partitioning. The first LP model is obtained by relaxing only the integrality constraints whereas in the second model relaxes both integrality and degree constraints. The algorithms were implemented in a C++ environment with the help of Concert Technology for CPLEX, and Boost Graph Libraries. The performance of these algorithms was studied for 50 random instances of varying problem sizes. It was found that on an average, the algorithms based on the first LP model provided better (closer to the optimum) solutions as compared to those based on the second LP model. We also observed that for both the LP models, the average quality of solutions given by the heuristics were found to be better ( within 5% of the optimum) than the average quality of solutions obtained from the approximation algorithm (between 30 - 60% of the optimum depending on the problem size).

In this dissertation, the problem of planning the motion of m Unmanned Vehicles (UVs) (or simply vehicles) through n points in a plane is considered. A motion plan for a vehicle is given by the sequence of points and the corresponding angles at which each point must be visited by the vehicle. We require that each vehicle return to the same initial location(depot) at the same heading after visiting the points. The objective of the motion planning problem is to choose at most q(≤ m) UVs and find their motion plans so that all the points are visited and the total cost of the tours of the chosen vehicles is a minimum amongst all the possible choices of vehicles and their tours. This problem is a generalization of the wellknown Traveling Salesman Problem (TSP) in many ways: (1) each UV takes the role of salesman (2) motion constraints of the UVs play an important role in determining the cost of travel between any two locations; in fact, the cost of the travel between any two locations depends on direction of travel along with the heading at the origin and destination, and (3) there is an additional combinatorial complexity stemming from the need to partition the points to be visited by each UV and the set of UVs that must be employed by the mission. In this dissertation, a sub-optimal, two-step approach to motion planning is presented to solve this problem:(1) the combinatorial problem of choosing the vehicles and their associated tours is based on Euclidean distances between points and (2) once the sequence of points to be visited is specified, the heading at each point is determined based on a Dynamic Programming scheme. The solution to the first step is based on a generalization of Held-Karp’s method. We modify the Lagrangian heuristics for finding a close sub-optimal solution. In the later chapters of the dissertation, we relax the assumption that all vehicles are homogenous. The motivation of heterogenous variant of Multi-depot, Multiple Traveling Salesmen Problem (MDMTSP) derives form applications involving Unmanned Aerial Vehicles (UAVs) or ground robots requiring multiple vehicles with different capabilities to visit a set of locations.

This thesis focuses on the design and implementation of an application involving the principles of DNA computing simulation for solving some selected problems. DNA computing represents an unconventional computing paradigm that is totally different from the concept of electronic computers. The main idea of DNA computing is to interpret the DNA as a medium for performing computation. Despite the fact, that DNA reactions are slower than operations performed on computers, they may provide some promising features in the future. The DNA operations are based on two important aspects: massive parallelism and principle of complementarity. There are many important problems for which there is no algorithm that would be able to solve the problem in a polynomial time using conventional computers. Therefore, the solutions of such problems are searched by exploring the entire state space. In this case the massive parallelism of the DNA operations becomes very important in order to reduce the complexity of finding a solution.