Optimal routing in a high threat environment : models and algorithms

Abstract

In this thesis, we develop routing models and algorithms in a high threat environment. Although routing problems have been studied extensively in many other contexts, they are usually designed for only one objective: minimizing total cost (distance). However, many other factors, such as risk and path diversification, must be taken into account while routing in a high threat environment. In this thesis, we consider two approaches to solve the routing problem in a high threat environment. In the first approach, we use a multi-objective integer programming to find best routes for troops from bases to target area given a transportation network. Objective functions we consider include minimizing total distance, total risk, and maximum flow on a given transportation arc. The main contribution of the first approach is quantification of risk given static locations of potential improvised explosive device attacks. In the second approach, we develop a Markov decision model to dynamically route a troop in a dynamically changing hostile environment. We solve it optimally for a small problem instance using value iteration algorithm. For larger instances, we introduce a novel approximation scheme for the underlying dynamic program. Numerical experiments show that our approximation gives near optimal routing policies efficiently.