Generalized Periodic Vehicle Routing and Maritime Surveillance

Maria Fleischer Fauske (), Carlo Mannino () and Paolo Ventura ()
Additional contact information
Maria Fleischer Fauske: Norwegian Defence Research Establishment, NO-2027 Kjeller, Norway;
Carlo Mannino: SINTEF ICT Applied Mathematics, NO-0314 Oslo, Norway; University of Oslo, NO-0316 Oslo, Norway;
Paolo Ventura: Istituto di Analisi dei Sistemi ed Informatica “A. Ruberti” (IASI) del CNR, 00185 Rome, Italy

Transportation Science, 2020, vol. 54, issue 1, 164–183

Abstract: Planning maritime surveillance activities in military operations and long-term defense planning is a huge task that is done manually today. Because maritime surveillance resources are extremely expensive, the potential cost savings of using optimization models to do such planning are large. In this paper, we developed a methodology for making maritime surveillance planning more efficient. The purpose of our tool is to find routes for the force elements involved in maritime surveillance operations, where the goal is to keep a maritime picture sufficiently updated. Our problem may be viewed as a variant of the classical periodic vehicle routing problem, but it differs from this problem in some major aspects. To cope with the specific issues of our problem, we introduce a novel time-indexed formulation, where each variable is associated with a set of contiguous time periods. We defined and implemented a branch-and-price procedure to solve this formulation to exact optimality. Moreover, to tackle instances of practical size, we defined and applied efficient and effective heuristic techniques for solving the pricing problem. We show how our approach can plan up to 72-hour realistic missions with routing ships.

Keywords: mixed integer linear programming; dynamic programming; column generation; maritime surveillance; military operations planning (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/trsc.2019.0899 (application/pdf)

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:inm:ortrsc:v:54:y:2020:i:1:p:164-183

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().