1. ¹Defence R&D Canada, CORA, Ottawa, Ontario, Canada
2. ²University of Ottawa, Ottawa, Ontario, Canada
3. ³McGill University, Montreal, Quebec, Canada

Correspondence: KYK Ng, Defence R&D Canada, Department of National Defence, National Defence Headquarters, 101 Colonel By Drive, Ottawa, Ontario K1A OK2, Canada. E-mail: kevin.ng@drdc-rddc.gc.ca

Received January 2007; Accepted July 2007; Published online 3 October 2007.

Abstract

Mission planning for surveillance coverage is of both practical and theoretical interest. In brief, regional surveillance involves planning the search of certain given regions in the minimum possible time. The surveillance problem can therefore be described as a variant of the classical travelling salesman problem. The uniqueness of the problem lies in the different allowed entry and exit points. Additionally, the mission schedule has to ensure the probability of target detection must not be compromised. From the practical perspective, any reduction in travelling time provides immediate cost savings to the defence department. A dynamic programming formulation is derived for the regional surveillance problem. An example is included to illustrate the methodology.