A heuristic algorithm for optimized routing of unmanned aerial systems for the interdiction of improvised explosive devices
Loading...
Authors
Scioletti, Michael S.
Subjects
Advisors
Royset, Johannes O.
Date of Issue
2008-06
Date
Publisher
Monterey, California. Naval Postgraduate School
Language
Abstract
Improvised explosive devices (IEDs) are effective weapons for insurgents targeting conventional military and security forces. Real-time information gathering about likely use of such weapons is one approach to reduce the effectiveness of IEDs. Unmanned aerial system (UASs) may provide the information gathering capability commanders need to interdict IEDs. Currently, UASs are not systematically utilized in that capacity. This research develops a routing tool that uses column-generation techniques and a greedy algorithm to route UASs through suspected IED locations for the purpose of IED interdiction as it transit to and from command directed missions. In empirical studies of data sets with up to 125 IED locations and missions, the routing tool provides optimal or near-optimal solutions in all instances tested. The tool produces de-conflicted routes for up to three UASs within five minutes of computing time.
Type
Thesis
Description
Series/Report No
Department
Organization
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
Sponsors
Funding
Format
xiv, 45 p. : ill. ;
Citation
Distribution Statement
Approved for public release; distribution is unlimited.
Rights
This publication is a work of the U.S. Government as defined
in Title 17, United States Code, Section 101. As such, it is in the
public domain, and under the provisions of Title 17, United States
Code, Section 105, is not copyrighted in the U.S.