Date of Award

August 2021

Document Type


Degree Name

Doctor of Philosophy (PhD)


Industrial Engineering

Committee Member

Yongjia Song

Committee Member

J. Cole Smith

Committee Member

Mary E. Kurz


We study vehicle routing for target surveillance and consider several extensions to present a holistic account of military-operational experiences. These problems are variations of the multi-vehicle covering tour problem which has been well-studied within the optimization community. Although many formulations and solution methodologies have been presented, they cannot be directly applied to our problems due to specific problem structures under study. We provide a review of the relevant literature and propose several different optimization models and algorithms for solving our problems of interest. First, we consider routing a fleet of vehicles for target surveillance within a deterministic setting with speed optimization under covering constraints; we present both (i) a branch-and-price-based exact algorithm and an effective labeling algorithm with an innovative set of dominance rules for solving the resulting pricing problem, and (ii) effective heuristic approaches. Next, we consider dynamic routing plans for target surveillance due to the sudden materialization of new targets. We propose a Markov decision process model to adapt to the changing information state and develop a two-stage stochastic programming-based look-ahead approach within a rolling horizon procedure. Lastly, we investigate the effect that routing markers' locations have on the vehicle set's coverage capabilities in the presence of an unknown target set. We formulate a two-stage stochastic program for marker selection and use scenario-decomposition techniques to avoid solving the large-scale mixed-integer program. Collectively, our research can be used by military and security personnel to analyze and improve their processes and to help these decision-makers implement economical, sustainable, and successful policies.



To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.