Accession Number:

ADA443502

Title:

Delaying a Convoy

Descriptive Note:

Master's thesis

Corporate Author:

NAVAL POSTGRADUATE SCHOOL MONTEREY CA DEPT OF OPERATIONS RESEARCH

Personal Author(s):

Report Date:

2005-12-01

Pagination or Media Count:

69.0

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 adversarys 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 convoys 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.

Subject Categories:

  • Operations Research
  • Logistics, Military Facilities and Supplies

Distribution Statement:

APPROVED FOR PUBLIC RELEASE