Minimum-risk routing through a mapped minefield

Christopher Richards, Christopher Odom, David Morton, Alexandra Newman*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


We embed a directed graph G(V, E) in a representation of a naval minefield; vertices V represent waypoints and edges E denote possible segments for ship transit. A new model identifies a simple s-t path through the minefield that minimizes the risk of incurring unacceptable damage from threats, that is, mine detonations. Traditional “edge-additive” models rely on shortest-path algorithms that over-accumulate risk along a path. Our “threat-additive” approach accumulates risk based upon the path's closest point of approach to each mine. We formulate and solve this model (1) using an integer program (IP) and its stronger variant, and (2) via an A * search algorithm. Preprocessing routines are key to reducing run times. We investigate the relative merits, both with respect to solution quality and requisite computational effort, of two types of graphs, one based on a rectilinear scheme and one based on Voronoi diagrams. We find that graphs based on Voronoi diagrams provide higher quality solutions with less computational effort, and that the A * search procedure requires less computational effort than solving instances of our models as IPs.

Original languageEnglish (US)
Pages (from-to)358-376
Number of pages19
Issue number3
StatePublished - Apr 2019


  • U.S. Navy
  • Voronoi graphs
  • heuristics
  • integer programming
  • risk
  • routing
  • shortest path

ASJC Scopus subject areas

  • Information Systems
  • Computer Networks and Communications


Dive into the research topics of 'Minimum-risk routing through a mapped minefield'. Together they form a unique fingerprint.

Cite this