Delaying a Convoy
Abstract
This thesis studies "the convoy-path interdiction problem" (CPIP) in which an interdictor uses limited resources to attack and disrupt road segments ("arcs") or road intersections ("nodes") in a road network in order to delay an adversary's convoy from reaching its destination. The convoy will move between a known origin node a and destination node b using a "quickest path." We first show how to compute, using an A* search, the convoy's quickest path under the assumptions that the convoy may occupy several arcs simultaneously, each arc may have a different speed limit, and the convoy maintains constant inter-vehicle spacing. The basic model assumes that the convoy moves in a single lane of traffic; an extension handles arcs that may have multiple lanes. Using that algorithm as a subroutine, a decomposition algorithm solves the optimal interdiction problem. Interdiction of a node or arc makes that node or arc impassable. Computational results are presented on grid networks with up to 629 nodes and 2452 arcs with varying levels of interdiction resource. Using Xpress-MP optimization software and a 2 GHz Pentium IV computer, the largest network problem solves in no more than 360 seconds given that at most 4 arcs can be interdicted.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 2005
- Accession Number
- ADA443502
Entities
People
- Dong H. Oh
Organizations
- Naval Postgraduate School