The coastal seaspace patrol sector design and allocation problem

Brian Lunday (), Hanif Sherali and Kevin Lunday

Computational Management Science, 2012, vol. 9, issue 4, 483-514

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. Copyright Springer-Verlag 2012

Keywords: Sector design; Sector allocation; Contiguity; Spanning aborescence; Steiner tree problem; Reformulation-linearization technique (RLT); Symmetry defeating constraints; Cut generation; Objective perturbation (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10287-012-0152-4 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:comgts:v:9:y:2012:i:4:p:483-514

Ordering information: This journal article can be ordered from
http://www.springer. ... ch/journal/10287/PS2

DOI: 10.1007/s10287-012-0152-4

Access Statistics for this article

Computational Management Science is currently edited by Ruediger Schultz

More articles in Computational Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().