Purpose The purpose of this paper is to improve the air movement operations planning heuristic in the literature to generate better solutions in a shorter time period. Design/methodology/approach Through a rigorous design of experiments (DOEs), we make significant heuristic improvements by evaluating alternative modular methodologies and tuning heuristic parameters for two scenarios. This includes a new approach to considering refueling operations. Findings We find the fine-tuned heuristic averages a 33% objective improvement and 70% reduction in computation time over the heuristic with original parameters for one of the scenarios. Additionally, we analyze the heuristic's quality of solution over time. Research limitations/implications Further analysis is required to generalize heuristic settings, which would require significant access to operational data or a portfolio of scenarios of interest. Practical implications Tuned heuristic parameters reduce the computation time from hours to minutes. This also makes it practically feasible to adjust parameters in the objective function to generate multiple courses of action (COAs) for a given instance. Originality/value This research provides novel vehicle assignment and routing heuristic improvement alternatives and demonstrates a DOEs-based heuristic tuning procedure.