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. This article 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 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 applicable 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.