Optimal Interdiction of a Ground Convoy

摘要

This paper explores the convoy quickest-path interdiction problem (CQPI). In this problem, an interdictor or attacker uses limited offensive resources to attack components of a road network (i.e., road segments or intersections) to maximally delay a ground convoy transiting between specified origin and destination nodes in the network. The convoy's commander, or defender, routes the convoy on a quickest path, which determines a convoy's instantaneous speed by the convoy's length, network characteristics (e.g., topology, speed limits), and by doctrine. After defining this new convoy quickest-path (CQP) problem, we develop an A* search algorithm for its solution. Finally, assuming a binary interdiction model in which an interdicted network component becomes impassable, we note the CQPI is NP-hard and show how to solve instances using a decomposition algorithm that solves CQP subproblems to evaluate tentative interdiction plans.