The gradually prominent environmental issues require an effective scheme of emission-reducing cruise trajectory optimization for commercial aircraft. However, existing researches have not paid sufficient attention to uncertainties in the dynamic changing environment. Under a comprehensive cost framework that monetizes emission impacts, this paper makes up for this by building a stochastic optimization model with uncertain operational parameters related to meteorological conditions, airspace occupancy as well as human factors. An algorithm combining Monte Carlo simulation and improved simulated annealing processing with wave temperature is developed to solve the model. Working with historical operating data of a typical flight, we have verified that the algorithm has advantage in global search due to the temper operations in temperature controlling. More importantly, the proposed scheme is demonstrated to be feasible and effective in decreasing comprehensive cost, with reduction rates of 17.33%, 16.03%, and 14.80% over a 25, 50 and 100-year time horizon respectively.