Stochastic aircraft routing (SAR) plays a critical role in defining the routing plans of airlines, which include assigning the aircraft to flight legs and determining the time and location of performing the maintenance to the aircraft. Based on the routing plan designed by airlines, the maintenance providers should schedule their workforce to perform maintenance operations by solving the maintenance staffing problem (MSP). MSP helps maintenance providers to build their staffing plans, which include the assignment of manpower to each aircraft, so that aircraft receive the maintenance operations as planned. Practically, to airlines, the routing plan will be interrupted (e.g. flight will be delayed) if an aircraft cannot be released from the maintenance station punctually. Similarly, for maintenance providers, if an aircraft missed the scheduled appointment at the maintenance station, this will also cause a huge interruption to their staffing plan. Therefore, there is an interrelationship between SAR and MSP. In the literature, the focus of each problem has been traditionally limited to independent scope, yet with limited consideration of their interrelationship. In this paper, we study SAR along with MSP, with an objective of investigating the interrelationship between SAR and MSP. For this purpose, we propose a coordinated configuration of SAR and MSP that is formulated as a leader-follower Stackelberg game, in which SAR acts as a leader and MSP acts as a follower. This game is enacted through a bi-level optimization model, which is solved by a bi-level nested ant colony optimization (ACO) algorithm. A case study of major airline and maintenance provider located in the Middle East is presented to demonstrate the feasibility and potential of the proposed model. The results demonstrate significant saving in the costs of both companies.