Date of Award
August 2021
Document Type
Dissertation
Degree Name
Doctor of Philosophy (PhD)
Department
Industrial Engineering
Committee Member
Yongjia Song
Committee Member
J. Cole Smith
Committee Member
Mary E. Kurz
Abstract
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.
Recommended Citation
Margolis, Joshua Taylor, "Optimization Models and Algorithms for Vehicle Routing and Target Surveillance" (2021). All Dissertations. 2865.
https://tigerprints.clemson.edu/all_dissertations/2865