Generating Topologically Different Weather Avoidance Routes Using Mincut as Constraints
Jit-Tat Chen, Rafal Kicinger, Matthias Steiner, James O. Pinto · 2013
This paper introduces an algorithm for generating a set of dynamic weather avoidance routes that are topologically different. The algorithm consists of two main components: pathfinding and constraints formulation. Pathfinding can be accomplished with any standard pathfinding algorithms such as Dijkstra’s or A* search. The main contribution of this paper is the constraints formulation component which uses mincut as constraints to steer the pathfinding algorithm towards generating topologically different routes. In this application, the mincut of an airspace segment effectively models the bottleneck of flows due to weather constraints for a prescribed flow direction (e.g., east to west flow). Thus, by sequentially incorporating mincuts as constraints into the pathfinding algorithm, a set of topologically different routes can be found.