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 ...
Kiland, Ingolf Norman Jr.; Kotchka, Jerry Allen (Monterey, California. U.S. Naval Postgraduate School, 1967-12);The problem of allocation of ASW forces assigned to an oceanic convoy in a submarine warfare environment is postulated as a two-person game with the payoff function being based on the "formula of random search". The ...
Heisinger, Ryan R. (Monterey, California. Naval Postgraduate School, 2007-09);Currently, the Marine Corps does not have a process or system to distribute supplies in support of combat operations in an optimal manner. We consider the problem of re-supplying a forward-deployed United States Marine ...