The coastal seaspace patrol sector design and allocation problem

The coastal seaspace patrol sector design and allocation problem

0.00 Avg rating0 Votes
Article ID: iaor20126358
Volume: 9
Issue: 4
Start Page Number: 483
End Page Number: 514
Publication Date: Nov 2012
Journal: Computational Management Science
Authors: , ,
Keywords: programming: multiple criteria, programming: integer, allocation: resources
Abstract:

In this paper, we model and solve the problem of designing and allocating coastal seaspace sectors for steady‐state patrolling operations by the vessels of a maritime protection agency. The problem addressed involves optimizing a multi‐criteria objective function that minimizes a weighted combination of proportional measures of the vessels’ distances between home ports and patrol sectors, the sector workload, and the sector span. We initially assure contiguity of each patrol sector in our mixed‐integer programming formulation via an exponential number of subtour elimination constraints, and then propose three alternative solution methods, two of which are based on reformulations that suitably replace the original contiguity representation with a polynomial number of constraints, and a third approach that employs an iterative cut generation procedure based on identifying violated subtour elimination constraints. We further enhance these reformulations with symmetry defeating constraints, either in isolation or in combination with a suitable perturbation of the objective function using weighted functions based on such constraints. Computational comparisons are provided for solving the problem using the original formulation versus either of our three alternative solution approaches for a representative instance. Overall, a model formulation based on Steiner tree problem (STP) constructs and enhanced by the reformulation‐linearization technique (RLT) yielded the best performance.

Reviews

Required fields are marked *. Your email address will not be published.