We consider a discrete time-and-space route-optimization problem across a finite time horizon in which multiple searchers seek to detect one or more probabilistically mov- ing targets. The paper formulates a novel convex mixed-integer nonlinear program for this problem that generalizes earlier models to situations with multiple targets, searcher decon- fliction, and target- and location-dependent search effectiveness. We present two solution approaches, one based on the cutting-plane method and the other on linearization. These approaches result in the first practical exact algorithms for solving this important problem, which arises broadly in military, rescue, law enforcement, and border patrol operations. The cutting-plane approach solves many realistically sized problem instances in a few minutes, while existing branch-and-bound algorithms fail. A specialized cut improves solution time by 50% in difficult problem instances. The approach based on linearization, which is appli- cable in important special cases, may further reduce solution time with one or two orders of magnitude. The solution time for the cutting-plane approach tends to remain constant as the number of searchers grows. In part, then, we overcome the difficulty that earlier solution methods have with many searchers.
展开▼
