Optimization Models and Algorithms for Vehicle Routing and Target Surveillance

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\u27 locations have on the vehicle set\u27s 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