Weather obstacles in the airspace can interfere with an aircraft’s flight plan. Pilots, assisted by air traffic controllers (ATCs), perform avoidance maneuvers that can be optimized. This paper addresses the generation of alternative aircraft trajectories to resolve unexpected events. The authors propose a solution based on the RRG algorithm, K-means clustering, and Dynamic Time Warping (DTW) similarity metric to address the problem. The mixed algorithm succeeds in generating a set of paths with diversity in an obstacle constrained airspace between Paris-Toulouse and London-Toulouse airports. This tool could help to reduce the workload of pilots and ATCs when such a situation arises.