Spatiotemporal Network Vulnerability Identification for the Material Routing Problem: A Bilevel Programming Approach

The routing of material over a distribution network is subject to manmade and natural disruptions, and it is important to understand the network's spatiotemporal vulnerabilities, i.e., when and where disruptions will notably affect outcomes. Knowledge of vulnerabilities informs mitigation efforts to ensure shipments are routed efficiently while meeting delivery deadlines. This research formulates and examines the bilevel material routing problem, wherein an upper-level problem identifies the time and location for a limited number of fi xed-duration attacks on arcs, and a lower-level problem routes shipments over the network between respective origins and destinations. The defender minimizes a combination of the weighted distance traveled, transport time of shipments, and penalties for delivering shipments outside of desired time windows, while meeting required delivery deadlines. This research develops a customized genetic algorithm to search the attacker's feasible region and develop high-quality solutions. For a representative scenario using a road network within the continental United States, testing examines the robustness of alternative assumptions a distance-maximizing attacker may make about defender priorities over the lower-level objective functions. For the most robust attacker assumption, testing examines for a range of attacker capabilities the spatiotemporal disruptions an effective attacker would make, i.e., the network vulnerabilities that merit mitigation by a defender.