Fleet planning is a complex problem which consists of selecting an optimal fleet of vehicles at the right moment in time to serve a specific demand while subject to different operational constraints. While Operations Research (OR) has mainly focused on long-term strategical fleet planning optimisation, certain operators such as humanitarian air services must make shorter-term decisions due to their operating environments and mission specifications. This research proposes a novel methodology for combining fleet planning and flight scheduling on a tactical time frame, weeks to months, using the United Nations Humanitarian Service's (UNHAS) South Sudan mission as a case study. The scientific approach consists of using two different linear programming models sequentially to divide the decision making process and reduce the computational complexity of the problem at hand. A multi-commodity network flow model is first used to size an initial fleet and investigate the transshipment of passengers throughout a network. The outputs are then used by a Fleet Size and Mix Vehicle Routing Problem (FSMVRP) model to further increase the accuracy of vehicle routes and passenger operations. The main results show that the methodology proposed can reduce the weekly routing costs by 40% compared to expert flight planners who schedule and route humanitarian requests on a daily basis, and reduce the fleet size by 60% from 14 air assets to 6. The research demonstrates that the developed optimisation framework can effectively be used as a decision support tool for both aircraft contracting, and flight routing and scheduling with the main objective to increase the efficiency and effectiveness of humanitarian air operations.