Generalized Periodic Vehicle Routing and Maritime Surveillance

Author
Fauske, Maria Fleischer
Mannino, Carlo
Ventura, Paolo
Date Issued
2019-11-18
Keywords
Maritim overvåking
Militære operasjoner
Forsvarplanlegging
Permalink
http://hdl.handle.net/20.500.12242/2701
DOI
10.1287/trsc.2019.0899
Collection
Articles
Description
Fauske, Maria Fleischer; Mannino, Carlo; Ventura, Paolo. Generalized Periodic Vehicle Routing and Maritime Surveillance. Transportation Science 2019
1643013.pdf
Size: 2M
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.
View Meta Data