Delaying a convoy
Oh, Dong Hwan
Wood, R. Kevin
Lee, Sang Heon
MetadataShow full item record
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.
Showing items related by title, author, creator and subject.
Pfeiffer, Volker (Monterey, California. Naval Postgraduate School, 2006-12);The nature of warfare has changed dramatically during the last decade. Western armies are increasingly required to conduct complex operations in urban terrain against asymmetric threats. These opponents use cities and their ...
Washburn, Alan (Monterey, California. Naval Postgraduate School, 2006); NPS-OR-06-007This report deals with network interdiction campaigns that are expected to be carried out indefinitely in time. Two sides are always involved, one desiring the unimpeded movement of some commodity, while the other desires ...
Smith, William T. (Monterey, California. Naval Postgraduate School, 2009-06);not along that route, and (c) the risk involved with moving from route to route. It is possible for a player to be interdicted even if his adversary is not on that route. Each player has a payoff matrix that maximizes ...