The operational aircraft maintenance routing problem with flight delay consideration (OAMRPFD) determines the route to be flown by each aircraft in real aspect life. It is observed that OAMRPFD related studies was formulated based on the expected value of the non-propagated delay, which is any delay caused by non-routing issues such as bad weather, technical problems, passengers delays, etc. However, a drawback of this formulation is that the expected value approach may not adequately reflect the final realization of non-propagated delay, as it is characterized by high level of uncertainty. This would result in facilitating the propagation of the delay and increasing its related cost paid by the airline companies. In this paper, we study OAMRPFD with an objective of developing an OAMRPFD that reflects appropriately the final realization of non-propagated delay. For this purpose, a new scenario-based stochastic framework for OAMRPFD (SOAMRPFD) is proposed. In order to solve the proposed model, an Ant Colony Optimization (ACO) algorithm is proposed. A case study of major airline company located in the Middle East is presented to demonstrate the potential of the proposed model.