Optimization-Based Routing and Scheduling of IED-Detection Assets in Contemporary Military Operations

摘要

Improvised Explosive Devices, or IEDs, have become a familiar and lethal part of contemporary military operations in Iraq and Afghanistan, producing more casualties than any other weapons system. One reason for their success is their practicality in an environment characterized by imbalances in the capabilities of opposing forces. The military forces conducting stability operations in Iraq and Afghanistan rely on the existing road networks to support logistical and operational movements. Insurgents with limited firepower and maneuver capabilities can place a bomb on the side of a road and detonate it anonymously to cause catastrophic effects on a passing convoy. Route clearance teams were developed to combat the emerging threat of IEDs. Capable of detecting IEDs with minimal risk to troops, route clearance teams move along the road network in search of these destructive devices. This thesis explores a mathematical approach to planning and scheduling route clearance missions. To achieve this objective, we first develop a probability-based model of IED activities on a road network used by occupation forces. We then use approximate dynamic programming methods to generate potential route clearance missions that are effective at reducing the risk of IED attacks. Once the paths are generated, they are inputted into a mixed integer program that finds the most risk- reducing combination of missions that can feasibly be executed, given constraints on the availability of route clearance teams. A route clearance schedule and its associated risk-reduction metrics result. We conduct several experiments on the methods developed to test its validity and applicability. Our first experiment examines the effects of mission timing on IED risk reduction, and shows the difficulty in relating this timing to our knowledge of IED risk in the road network.