Route Optimization for Multiple Searchers

摘要

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 moving targets. The paper formulates a novel convex mixed-integer nonlinear program for this problem that generalizes earlier models to situations with multiple targets, searcher deconfliction, 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 few minutes, while existing branch-and- bound algorithms fail. A specialized cut improves solution times by 50% in difficult problem instances. The approach based on linearization, which is applicable in important special cases, may further reduce solution times with one or two orders of magnitude. The solution times for the cutting-plane approach tend to remain constant as the number of searchers grows. In part, then, we overcome the difficulty that earlier solution methods have with many searchers.