Joel L. Ryan

Date of Award

3-1998

Document Type

Thesis

Degree Name

Master of Science

Department

Department of Operational Sciences

First Advisor

T. Glenn Bailey, PhD

Abstract

We apply a Reactive Tabu Search (RTS) heuristic within a discrete event simulation to solve routing problems for Unmanned Aerial Vehicles (UAVs). Our formulation represents this problem as a multiple Traveling Salesman Problem with time windows (mTSPTW), with the objective of attaining a specified level of target coverage using a minimum number of vehicles. Incorporating weather and probability of UAV survival at each target as random inputs, the RTS heuristic in the simulation searches for the best solution in each realization of the problem scenario in order to identify those routes that are robust to variations in weather, threat, or target service times. Generalizing this approach as Embedded Optimization (EO), we define EO as a characteristic of a discrete event simulation model that contains optimization or heuristic procedures that can affect the state of the system. The RTS algorithm in the UAV simulation demonstrates the utility of EO by determining the necessary fleet size for an operationally representative scenario. From our observation of robust routes, we suggest a methodology for using robust tours as initial solutions in subsequent replications. We present an object oriented implementation of this approach using MODSIM III, and show how mapping object inheritance to the GVRP hierarchy allows for minimal adjustments from previously written objects when creating new types. Finally, we use EO to conduct an analysis of fleet size requirements within an operationally representative scenario.

AFIT Designator

AFIT-GOR-ENS-98M-20,AFIT-GOR-ENS-98M-21

DTIC Accession Number

ADA342293

Download

Share

COinS