Delaying a convoy

Loading...
Thumbnail Image
Authors
Oh, Dong Hwan
Subjects
Advisors
Wood, R. Kevin
Lee, Sang Heon
Date of Issue
2005-12
Date
Publisher
Monterey, CA; Naval Postgraduate School
Language
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.
Type
Thesis
Description
Series/Report No
Organization
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
Sponsors
Funder
Format
xvi, 51 p. : col. ill. ;
Citation
Distribution Statement
Approved for public release; distribution is unlimited.
Rights
Collections