Planning routes with wiggle room in en route weather-impacted airspaces

We investigate a form of robust route planning by imbedding path-stretch zones into routes that avoid hazardous weather constraints in en route airspace. Along every path, every so often, we plan for "wiggle room" - a constraint-free triangular area whose purpose is to control the delay of a flight by executing a path-stretch maneuver at these locations. We designed and implemented an algorithm that computes the paths by searching an underlying disk packing in the "bottommost" fashion. Our solution allows the user to specify the constraints for the flights, the size of the path-stretch zones, and the maximum and minimum distance between the consecutive zones along a path. The paths computed by our algorithm fulfill a number of additional requirements, e.g., we take care of never placing the path-stretch zones on top of the sector boundaries. We present theoretical guarantees provided by the algorithm and outputs produced on sample airspaces.