IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v54y2020i1p164-183.html
   My bibliography  Save this article

Generalized Periodic Vehicle Routing and Maritime Surveillance

Author

Listed:
  • 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)

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.

Suggested Citation

  • Maria Fleischer Fauske & Carlo Mannino & Paolo Ventura, 2020. "Generalized Periodic Vehicle Routing and Maritime Surveillance," Transportation Science, INFORMS, vol. 54(1), pages 164-183, January.
  • Handle: RePEc:inm:ortrsc:v:54:y:2020:i:1:p:164-183
    DOI: 10.1287/trsc.2019.0899
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/trsc.2019.0899
    Download Restriction: no

    File URL: https://libkey.io/10.1287/trsc.2019.0899?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. DYER, Martin E. & WOLSEY, Laurence A., 1990. "Formulating the single machine sequencing problem with release dates as a mixed integer program," LIDAM Reprints CORE 878, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    2. Martinelli, Rafael & Pecin, Diego & Poggi, Marcus, 2014. "Efficient elementary and restricted non-elementary route pricing," European Journal of Operational Research, Elsevier, vol. 239(1), pages 102-111.
    3. Grob, Marcel J.H.B., 2006. "Routing of platforms in a maritime surface surveillance operation," European Journal of Operational Research, Elsevier, vol. 170(2), pages 613-628, April.
    4. Alberto Caprara & Matteo Fischetti & Paolo Toth, 2002. "Modeling and Solving the Train Timetabling Problem," Operations Research, INFORMS, vol. 50(5), pages 851-861, October.
    5. E. DYER, Martin & WOLSEY, Laurence A., 1990. "Formulating the single machine sequencing problem with release dates as a mixed integer program," LIDAM Reprints CORE 917, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    6. Pasquale Avella & Maurizio Boccia & Carlo Mannino & Igor Vasilyev, 2017. "Time-Indexed Formulations for the Runway Scheduling Problem," Transportation Science, INFORMS, vol. 51(4), pages 1196-1209, November.
    7. Roberto Baldacci & Aristide Mingozzi & Roberto Roberti, 2011. "New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem," Operations Research, INFORMS, vol. 59(5), pages 1269-1283, October.
    8. Steven Harrod, 2011. "Modeling Network Transition Constraints with Hypergraphs," Transportation Science, INFORMS, vol. 45(1), pages 81-97, February.
    9. Sanjeeb Dash & Oktay Günlük & Andrea Lodi & Andrea Tramontani, 2012. "A Time Bucket Formulation for the Traveling Salesman Problem with Time Windows," INFORMS Journal on Computing, INFORMS, vol. 24(1), pages 132-147, February.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. José Luis Andrade-Pineda & David Canca & Marcos Calle & José Miguel León-Blanco & Pedro Luis González-R, 2025. "Design and Assessment of Robust Persistent Drone-Based Circular-Trajectory Surveillance Systems," Mathematics, MDPI, vol. 13(8), pages 1-39, April.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Leonardo Lamorgese & Carlo Mannino, 2015. "An Exact Decomposition Approach for the Real-Time Train Dispatching Problem," Operations Research, INFORMS, vol. 63(1), pages 48-64, February.
    2. Daniel Kowalczyk & Roel Leus & Christopher Hojny & Stefan Røpke, 2024. "A Flow-Based Formulation for Parallel Machine Scheduling Using Decision Diagrams," INFORMS Journal on Computing, INFORMS, vol. 36(6), pages 1696-1714, December.
    3. Artur Alves Pessoa & Teobaldo Bulhões & Vitor Nesello & Anand Subramanian, 2022. "Exact Approaches for Single Machine Total Weighted Tardiness Batch Scheduling," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1512-1530, May.
    4. Natashia Boland & Riley Clement & Hamish Waterer, 2016. "A Bucket Indexed Formulation for Nonpreemptive Single Machine Scheduling Problems," INFORMS Journal on Computing, INFORMS, vol. 28(1), pages 14-30, February.
    5. Carlo Mannino & Alessandro Mascis, 2009. "Optimal Real-Time Traffic Control in Metro Stations," Operations Research, INFORMS, vol. 57(4), pages 1026-1039, August.
    6. Leonardo Lamorgese & Carlo Mannino & Mauro Piacentini, 2016. "Optimal Train Dispatching by Benders’-Like Reformulation," Transportation Science, INFORMS, vol. 50(3), pages 910-925, August.
    7. Lu, Jiawei & Nie, Qinghui & Mahmoudi, Monirehalsadat & Ou, Jishun & Li, Chongnan & Zhou, Xuesong Simon, 2022. "Rich arc routing problem in city logistics: Models and solution algorithms using a fluid queue-based time-dependent travel time representation," Transportation Research Part B: Methodological, Elsevier, vol. 166(C), pages 143-182.
    8. Gao, Yuan & Kroon, Leo & Yang, Lixing & Gao, Ziyou, 2018. "Three-stage optimization method for the problem of scheduling additional trains on a high-speed rail corridor," Omega, Elsevier, vol. 80(C), pages 175-191.
    9. Boschetti, Marco Antonio & Maniezzo, Vittorio & Strappaveccia, Francesco, 2017. "Route relaxations on GPU for vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 258(2), pages 456-466.
    10. Jain, A. S. & Meeran, S., 1999. "Deterministic job-shop scheduling: Past, present and future," European Journal of Operational Research, Elsevier, vol. 113(2), pages 390-434, March.
    11. Thibaut Vidal & Rafael Martinelli & Tuan Anh Pham & Minh Hoàng Hà, 2021. "Arc Routing with Time-Dependent Travel Times and Paths," Transportation Science, INFORMS, vol. 55(3), pages 706-724, May.
    12. Diego Pecin & Claudio Contardo & Guy Desaulniers & Eduardo Uchoa, 2017. "New Enhancements for the Exact Solution of the Vehicle Routing Problem with Time Windows," INFORMS Journal on Computing, INFORMS, vol. 29(3), pages 489-502, August.
    13. Francis Sourd, 2009. "New Exact Algorithms for One-Machine Earliness-Tardiness Scheduling," INFORMS Journal on Computing, INFORMS, vol. 21(1), pages 167-175, February.
    14. Pasquale Avella & Maurizio Boccia & Bernardo D’Auria, 2005. "Near-Optimal Solutions of Large-Scale Single-Machine Scheduling Problems," INFORMS Journal on Computing, INFORMS, vol. 17(2), pages 183-191, May.
    15. Huang, Nan & Qin, Hu & Du, Yuquan & Wang, Li, 2024. "An exact algorithm for the multi-trip vehicle routing problem with time windows and multi-skilled manpower," European Journal of Operational Research, Elsevier, vol. 319(1), pages 31-49.
    16. Harrod, Steven & Schlechte, Thomas, 2013. "A direct comparison of physical block occupancy versus timed block occupancy in train timetabling formulations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 54(C), pages 50-66.
    17. Talebian, Ahmadreza & Zou, Bo, 2015. "Integrated modeling of high performance passenger and freight train planning on shared-use corridors in the US," Transportation Research Part B: Methodological, Elsevier, vol. 82(C), pages 114-140.
    18. Fabio D'Andreagiovanni & Carlo Mannino & Antonio Sassano, 2009. "A Power-Indexed Formulation for Wireless Network Design," DIS Technical Reports 2009-14, Department of Computer, Control and Management Engineering, Universita' degli Studi di Roma "La Sapienza".
    19. Sartor, Giorgio & Mannino, Carlo & Nygreen, Thomas & Bach, Lukas, 2023. "A MILP model for quasi-periodic strategic train timetabling," Omega, Elsevier, vol. 116(C).
    20. Nikolaus Furian & Michael O’Sullivan & Cameron Walker & Eranda Çela, 2021. "A machine learning-based branch and price algorithm for a sampled vehicle routing problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(3), pages 693-732, September.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ortrsc:v:54:y:2020:i:1:p:164-183. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.