Show simple item record

dc.contributor.advisorRathinam, Sivakumaren_US
dc.creatorDoshi, Riddhi Rajeeven_US
dc.date.accessioned2011-10-21T22:02:54Zen_US
dc.date.accessioned2011-10-22T07:11:40Z
dc.date.available2011-10-21T22:02:54Zen_US
dc.date.available2011-10-22T07:11:40Z
dc.date.created2010-08en_US
dc.date.issued2011-10-21en_US
dc.date.submittedAugust 2010en_US
dc.identifier.urihttp://hdl.handle.net/1969.1/ETD-TAMU-2010-08-7736en_US
dc.description.abstractVarious 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).en_US
dc.format.mimetypeapplication/pdfen_US
dc.language.isoen_USen_US
dc.subjectHamiltonian Path Problemen_US
dc.subjectHeterogeneous Vehiclesen_US
dc.subjectRoutingen_US
dc.subjectApproximation Algorithmen_US
dc.titleApproximation Algorithms and Heuristics for a 2-depot, Heterogeneous Hamiltonian Path Problemen_US
dc.typeThesisen
thesis.degree.departmentMechanical Engineeringen_US
thesis.degree.disciplineMechanical Engineeringen_US
thesis.degree.grantorTexas A&M Universityen_US
thesis.degree.nameMaster of Scienceen_US
thesis.degree.levelMastersen_US
dc.contributor.committeeMemberSwaroop, Dvahgen_US
dc.contributor.committeeMemberButenko, Sergiyen_US
dc.type.genrethesisen_US
dc.type.materialtexten_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record