4 Presentations

• 
  10:30 AM - 10:55 AM

  Iterated local search for coverage path planning in mine countermeasure operations

  • Dominik Richard, presenter, Université Laval
  • Michael Morin, Assistant Professor at the Department of Operations and Decision Systems, Université Laval, Québec, Canada
  • Claude-Guy Quimper, Université Laval

  Naval mines, many being remnants of past conflicts, still threaten the safety of ships and wildlife while posing environmental problems. To remove those mines, autonomous minesweepers, equipped with side-scan sonars, can be used. We frame the minesweeping task as a combinatorial coverage path planning problem with imperfect extended detection (CPPIED). An efficient solution to the CPPIED minimizes both the sweeping path length and its number of turns,
  while enforcing the required probabilistic coverage of the map. To solve the CPPIED, we propose an iterated local search heuristic inspired by the covering salesman problem. We show that our approach improves on the solutions
  of various algorithms, including the ones of the best-known heuristic for the CPPIED, DpSweeper. Our algorithm significantly reduces the sweeping path lengths, hence improving planning methods for mine countermeasure operations and bridging coverage tour and coverage path problems.

• 
  10:55 AM - 11:20 AM

  Optimizing submarine operations in the Arctic near and under ice

  • Mounir Ait Hamou, presenter, University of Ottawa
  • Jean-Denis Caron, Defence Research Development Canada
  • François-Alex Bourque, Defence Research and Development Canada Centre for Operational Research and Analysis

  One role of Defence Research and Development Canada (DRDC) is to provide scientific and technical advice to the Department of National Defence (DND) and the Canadian Armed Forces (CAF). In 2024, DRDC supported DND/CAF options analysis of diesel-submarines replacement, to include operating in the Arctic near and under ice. Given the very limited knowledge of operating in the Arctic, DRDC investigated the different challenges that would be faced by a notional diesel-submarine. An interactive visualization tool illustrating and explaining the challenges and complexities of diesel-submarine operations in the Arctic was developed. The tool uses a custom Dijkstra-based pathfinding algorithm implemented to optimize submarine navigation through the Canadian Arctic Archipelago islands, accounting for ice conditions, bathymetry, travel distance limits, as well as for land masses and navigable passages. This presentation provides background and context on the problem, discusses the main operating challenges, provides an overview of the algorithm, and shows a few examples.

• 
  11:20 AM - 11:45 AM

  Bringing Model-and-Solve Back into Maritime Search and Rescue Mission Planning

  • Amirhossein Esmaeilpour, presenter, Ph.D. Student at the Department of Operations and Decision Systems, Université Laval, Québec, Canada
  • Michael Morin, Université Laval
  • Irène Abi-Zeid, Full Professor at the Department of Operations and Decision Systems, Université Laval, Québec, Canada

  Optimization-based decision support systems, such as SAR Optimizer, can assist search mission coordinators in planning maritime search operations. Computing the objective value, here the probability of finding the lost search object, requires lengthy simulations which complexify the direct use of mathematical programs. As such, SAR Optimizer relies on problem-specific algorithms, not on models and general-purpose solvers. We discuss how we can still use a model-and-solve approach to propose maritime aerial search plans. Formulating a model, instead of using problem-specific algorithms, facilitates the introduction of operational constraints such as airspace deconfliction to prevent potential collisions. We implemented our model for the Hexaly solver with an external function calling SAR Optimizer and used a surrogate to estimate the simulation results and accelerate the solving process. By doing so, we were able to enforce constraints not yet implemented in SAR Optimizer, which could pave the way to better search plans.

• 
  11:45 AM - 12:10 PM

  An Optimal Multi-Searcher Search Problem with Deconfliction Constraints

  • Saeid Abbasiparizi, presenter, PhD Candidate, Department of Operations and Decision Systems, Faculty of Business Administration, Université Laval
  • Michael Morin, Associate Professor, Department of Operations and Decision Systems, Faculty of Business Administration, Université Laval
  • Irene Abi-Zeid, Full Professor, Department of Operations and Decision Systems, Faculty of Business Administration, Université Laval

  Search and rescue incidents involving aircraft overland can sometimes develop into major search operations requiring rigorous planning and search resources allocation. In such situations, search and rescue decision support systems are vital to save lives. We address the problem of deploying a team of fixed wings or helicopters to maximize the probability of finding the search object. In search operations planning, deconfliction constraints, which prevent searchers from flying over the same region at the same time, are often introduced for safety purposes. Instead of modeling deconfliction solely based search areas overlap, as in existing models, we add decision variables for the altitude so that our model can allow searchers to fly over the same area if there is sufficient altitude separation between them, as per operational standards. We develop several mathematical models for that specific problem and compare their performance on a set of plausible search environments in southeast Canada.