Back to search

Clemson University

Optimization Models and Algorithms for Vehicle Routing and Target Surveillance

Abstract

dc:description.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.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy (PhD)
Level thesis:degree_level
Dissertation
Discipline thesis:degree_discipline
Industrial Engineering

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Margolis, Joshua Taylor
Contributors dc:contributor
  • Yongjia Song
  • J. Cole Smith
  • Mary E. Kurz

Subjects

dc:subject × 6

Identifiers

dc:identifier.*
Repository record dc:identifier
https://open.clemson.edu/all_dissertations/2865

Chain of custody

source
Harvested from
Clemson University
Base URL
open.clemson.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Margolis, Joshua Taylor. Optimization Models and Algorithms for Vehicle Routing and Target Surveillance. Dissertation thesis, https://open.clemson.edu/all_dissertations/2865