Route Optimization for Multiple Searchers

Loading...
Thumbnail Image
Authors
Royset, J.O.
Sato, H.
Subjects
Advisors
Date of Issue
August 26, 2010
Date
2010-08-26
Publisher
Language
Abstract
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.
Type
Article
Description
Series/Report No
Department
Operations Research (OR)
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
Naval Research Logistics, 57, 701-717, 2010
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.
Collections