Premium
Minimum‐risk routing through a mapped minefield
Author(s) -
Richards Christopher,
Odom Christopher,
Morton David,
Newman Alexandra
Publication year - 2019
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21868
Subject(s) - computer science , voronoi diagram , shortest path problem , path (computing) , integer (computer science) , preprocessor , mathematical optimization , graph , representation (politics) , enhanced data rates for gsm evolution , theoretical computer science , mathematics , artificial intelligence , geometry , politics , political science , law , programming language
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.