The climate impact of non-CO2 emissions, which are responsible for two-thirds of aviation radiative forcing, highly depends on the atmospheric chemistry and weather conditions. Hence, by planning aircraft trajectories to reroute areas where the non-CO2 climate impacts are strongly enhanced, called climate-sensitive regions, there is a potential to reduce aviation-induced non-CO2 climate effects. Weather forecast is inevitably uncertain, which can lead to unreliable determination of climate-sensitive regions and aircraft dynamical behavior and, consequently, inefficient trajectories. In this study, we propose robust climate-optimal aircraft trajectory planning within the currently structured airspace considering uncertainties in standard weather forecasts. The ensemble prediction system is employed to characterize uncertainty in the weather forecast, and climate-sensitive regions are quantified using the prototype algorithmic climate change functions. As the optimization problem is constrained by the structure of airspace, it is associated with hybrid decision spaces. To account for discrete and continuous decision variables in an integrated and more efficient manner, the optimization is conducted on the space of probability distributions defined over flight plans instead of directly searching for the optimal profile. A heuristic algorithm based on the augmented random search is employed and implemented on graphics processing units to solve the proposed stochastic optimization computationally fast. An open-source Python library called ROOST (V1.0) is developed based on the aircraft trajectory optimization technique. The effectiveness of our proposed strategy to plan robust climate-optimal trajectories within the structured airspace is analyzed through two scenarios: a scenario with a large contrail climate impact and a scenario with no formation of persistent contrails. It is shown that, for a nighttime flight from Frankfurt to Kyiv, a 55ĝ€¯% reduction in climate impact can be achieved at the expense of a 4ĝ€¯% increase in the operating cost.