Convective weather poses a major threat that compromises the safe operation of flights while inducing delay and cost. The aircraft trajectory optimization problem under thunderstorms is addressed, proposing a novel heuristic approach that incorporates uncertainties in the evolution of convective cells. Namely, the Augmented Random Search (ARS) algorithm is used to deform a directed graph iteratively in the search of an optimal path. Flight time and fuel consumption are optimized while avoiding unsafe regions. By means of parallel programming on graphical processing units (GPUs), the computational times are reduced to enable near-real time operation. The suggested method is tested considering a dynamic model of an aircraft flying between two waypoints at constant flight level; the test scenario consists of a real weather forecast described by an ensemble of equiprobable members. The influence of the maximum number of iterations and the relative weights between optimization objectives is analyzed. Results show that the methodology is able to avoid dangerous regions and find the balance between total time of flight and fuel consumption.