Air movement operations planning heuristic improvement

US Army units solicit helicopter support from Army Aviation units using an Air Mission Request (AMR) process (Department of the Army [DA], 2020a) to support air movement operations which move personnel, supplies, and equipment throughout an area of operations (Department of the Army [DA], 2020b). The unit requesting support routes the AMR through their chain of command where higher echelons conduct quality control and consolidates the requests for onward submittal to the next echelon. At the brigade level, the brigade aviation element (BAE) provides aviation subject matter expertise for filtering and prioritizing the AMRs to best employ helicopter assets. The BAE submits the final AMRs to the next headquarters, usually a division. The division tasks the AMRs to the aviation unit for execution. Standard processing times from the BAE’s receipt of the tasking to the planned air movement is 96 h, though dynamic requirements often involve requests submitted within 24 h of the desired movement.

The aviation unit tasks the AMRs to the appropriate subordinate aviation battalions and/or task forces based on mission type, required equipment, aircraft needed, and other factors. These aviation battalions must task each AMR to an aircraft team and generate routes for the aircraft team to complete all assigned AMRs and associated requirements. No later than 12 h prior to the desired time of air movement, the aviation unit publishes a daily air movement table to convey the results of the planning process back to the unit requesting aviation support.

Aviation mission planners have 12 h (although often less) to task and route aircraft teams to support the AMRs based on AMR priority levels, locations, number of personnel and pickup/drop-off time windows. According to a current general support aviation battalion commander, the current process can take a team of planners over five hours to generate a plan for a single day (Espinoza, 2022). Nelson et al. (2023a) introduce two models to task air mission requests (AMRs) to rotary wing aircraft teams and generate the required routes in order to minimize unsupported AMRs by priority level, number of helicopter teams used by utilization penalty and total flight hours. A mixed integer linear program (MILP) is developed which generates optimal solutions but proves intractable for application-sized instances with 30–100 AMRs. A heuristic approach is developed which generates feasible solutions within a tactically useful time, but the authors note future work to potentially improve the heuristic. In this paper we investigate methodologies to improve the aviation air movement operations planning heuristic in order to generate superior solutions in less time. We make improvements by incorporating several alternative modular methodologies and optimizing heuristic parameters. The findings result from data collected during a rigorous design of experiments (DOE). This paper demonstrates its value in its final presentation of solution quality and time for various application-sized problems and compares the performance to Nelson et al. (2023a).

This research is not the first to envision new systems or tools to improve military decision-making, planning and dynamic re-planning, or resource-allocation with automation (McQueary et al., 2005; Rogers et al., 2018; Schwartz et al., 2019; McConnell et al., 2021) including aviation support use cases (Ghigliotti et al., 2022; Nelson et al., 2022). Much of the military aviation planning literature centers on flight and maintenance planning (FMP) to identify which aircraft to fly and which aircraft should enter maintenance over a given planning horizon with the stated objective to maximize fleet availability and meet both flight and maintenance requirements (Pippin, 1998; Kozanidis et al., 2010; Marlow and Dell, 2017). MILP approaches are common (Pippin, 1998; Kozanidis et al., 2014; Verhoeff et al., 2015; Marlow and Dell, 2017; Verhoeff and Verhagen, 2023) though some use heuristics and metaheuristics (Steiner, 2006; Winata, 2011; Kozanidis et al., 2014; Balakrishnan et al., 2021), simulation (Marlow et al., 2019), or approximate dynamic programming (Powell, 2014). Notably in our problem, the planners are not concerned with the maintenance or future demand planning.

The most closely related literature is the dial-a-ride problem (DARP) (Ho et al., 2018b; Nasri et al., 2021) and military studies assigning assets to missions while considering the associated operational capacities, demands, routes, time windows, etc. These studies examine heterogeneous mobility rotary-wing units (Kim and Kim, 2011; Mogensen, 2014; Nelson et al., 2023a; Nelson, 2023), fixed-wing fleets (Brown et al., 2013), amphibious ready groups with multiple ship types, marines and different aircraft (Yakıcı et al., 2018), and matching air assets to tactical air requests (Noble et al., 2015). Common approaches in these problems include MILP models (Brown et al., 2013; Yakıcı et al., 2018; Nelson et al., 2023a), heuristics (Kim and Kim, 2011; Mogensen, 2014; Yakıcı et al., 2018; Nelson et al., 2023a), and metaheuristics (Cordeau and Laporte, 2003; Noble et al., 2015; de Alvarenga Rosa et al., 2016; Ho et al., 2018a); mixed approaches are common.

In a closely related study, Kim and Kim (2011) also focus on the air movement operations problem, but they minimize the time by which all missions are completed and assume aircraft have the fuel capacity to handle all assigned missions for the day. Their experimentation includes problem instances of 5–20 aircraft and 5–25 missions per day; however, their problem instances use randomly generated mission start/end points using the uniform distribution in a square plane. Brown et al. (2013) address a fixed-wing DARP problem over both single day and seven day time horizons for Iraq and Afghanistan-based scenarios, assuming that airplanes may refuel at any landing node.

The MILP model in Nelson et al. (2023a) solves the US Army aviation air movement operations planning problem (Nelson et al., 2022) by formulating it as a DARP where refueling is available at some but not all helicopter landing zones (HLZs). The paper’s research draws heavily on DARP research from Cordeau and Laporte (2007), Ho et al. (2018b), and Nasri et al. (2021). The MILP includes additional features such as capacitated helicopter routing and multi-node refueling (de Alvarenga Rosa et al., 2016; Sundar and Rathinam, 2012; Sundar et al., 2016). However, Nelson et al. (2023a) show that optimal solutions cannot be found in a reasonable amount of time for more than around three aircraft teams and 10 AMRs. The air movement operations planning heuristic is an adaptation of the insertion algorithm for the single vehicle DARP (Häme, 2011) into a multi-helicopter team heuristic to find quality feasible solutions to application-sized instances of the problem with 10 aircraft teams and 90–100 AMRs.

The purpose of this research is to improve the air movement operations planning heuristic solution quality and computation time. In this paper, we demonstrate improvement through parameter tuning. Research in parameter tuning involves numerous methods, including teacher–learner optimizing algorithms (Yang et al., 2018; Rao and Kalyankar, 2013), robust observer approaches (Beelen et al., 2020), and data analysis parameter approximation techniques (Wang et al., 2020).

Similar to this paper’s methodology, there is ample research using DOE to tune model parameters. Lujan-Moreno et al. (2018) use DOE to screen the most important machine learning hyperparameters followed by a response surface methodology to fine-tune the hyperparameters. Shankar et al. (2022) use DOE and response surface design to ascertain the key synthesis parameters and develop synthesized O-doped boron nitride models. O’Connor and English (2021) demonstrate a systematic factorial-design DOE to estimate optimal parameters of empirical water models. We use a methodology adapted from Gunawan et al. (2011) in creating a DOE approach to fine-tune algorithm parameters.

Nelson et al. (2023a) employ a heuristic that terminates when no improvement is made to the objective in subsequent improvement cycles, which then returns the best solution found. To compare performance for varying heuristic settings, Figure 1 presents the heuristic modified to run for a fixed amount of time.

Similar to the heuristic in Nelson et al. (2023a), the fixed time heuristic starts with loading model inputs and determining which helicopter teams can support each AMR through the AMR assignment filter. The set of individually feasible AMRs per aircraft team is then sent to the initial AMR assignment module where it generates a set number of random assignments. In the original heuristic, the initial AMR assignment module randomly assigns AMRs to any helicopter team in the feasible AMR set. In this paper, we introduce a parameter to control the percentage of initial assignments that allow for unsupported AMRs or assignments to high-cost helicopter teams. High-cost aircraft teams are defined by the user when evaluating each aircraft team’s utilization penalty, β. This parameter is further discussed in Section 4.2. The set of initial assignments then goes through the aircraft team routing algorithm adapted from the single vehicle DARP adaptive insertion algorithm (Häme, 2011). This paper introduces an additional aircraft team routing algorithm that has the capability of inserting refueling stops at HLZs that do not have an associated AMR pickup or drop-off. Section 4.3 goes into further detail regarding the differences in the two aircraft team routing algorithms considered. Additionally, Section 4.4 evaluates the performance of the feasible route limit objectives described in Nelson et al. (2023a).

For each initial assignment, the aircraft team routing algorithm outputs either a feasible routing for each aircraft team or determines that the AMR assignment is infeasible. If there are no feasible assignments, the heuristic returns to the initial AMR assignment module and generates a new set of random assignments. If there is at least one assignment with a feasible routing solution, the heuristic then sets the number of feasible solutions y to the minimum of the initial y value and the number of assignments with feasible routing solutions.

During the first improvement cycle, the stopping criteria are met if the assignment and routing solution with the lowest objective value supports all AMRs and the high-cost aircraft teams are not utilized. If the stopping criteria are not met during the first improvement cycle, the heuristic attempts to improve y assignments by redistributing unsupported AMRs to aircraft teams. The aircraft team routing module attempts to generate feasible routes for the improved assignments. The improved assignments with feasible routes are evaluated to determine objective values. Upon completion of the first improvement cycle, the stopping criteria are met when the lowest objective value of the improved assignments is the same as seen in the previous improvement cycle. For the fixed time heuristic, once the stopping criteria are met, the best solution is saved and the heuristic returns to the initial AMR assignment module. Upon every full iteration of the heuristic, the lowest objective value solution is maintained. As the predetermined computation time elapses, the heuristic outputs the solution with the lowest objective value. This solution consists of AMR assignments and aircraft team routing that meets all feasibility constraints from Nelson et al. (2023a).

Performance of the air movement operations planning heuristic compared to optimal solutions is addressed in Nelson et al. (2023a). A key takeaway from the paper’s analysis is that the MILP model failed to generate a feasible solution for problems consisting of 20 or more AMRs after 96 h of run time. In contrast, the heuristic generated feasible solutions to support all AMRs for the same-sized problems in an average of 16 min. The paper demonstrated the heuristic’s ability to generate quality solutions within a time frame that is useful for aviation mission planners within the air movement operations planning process.

In order to generate quality feasible solutions in near real-time, the heuristic must decrease the decision space using two key methods. These reductions may generate non-optimal but feasible and potentially useful solutions for mission planning applications. The first reduction involves assigning AMRs to aircraft teams. With n AMRs and |K| aircraft teams, there are |K|ⁿ ways to assign AMRs to helicopter teams. For a military application, the full enumeration of assignments is not achievable. Even after the heuristic’s AMR assignment filter, large-scale problems still retain a set of potentially feasible assignments too large to evaluate comprehensively. Consequently, the heuristic can only attempt to generate feasible routing solutions for a sample of potential feasible assignments.

The second reduction in decision space occurs during the aircraft team routing module after AMRs have been assigned to each helicopter team. The heuristic’s AMR insertion algorithm constructs routes through numerous iterations of adding AMRs to feasible routing solutions. At each insertion step, the algorithm generates every possible combination of pickup and drop-off insertions for the new AMR into a set of feasible routes from the previous insertion. While considering every past feasible route ensures the optimal route for the AMR assignment, this approach becomes impractical as the number of AMRs assigned to aircraft teams increases. To address this scalability challenge, the air movement operations planning heuristic introduces a feasible route limit, τ, to limit the number of feasible routes to carry forward after every insertion. This enables the heuristic to reduce the routes considered while still producing quality feasible routes.

The purpose of this paper is to improve the air movement operations planning heuristic by tuning heuristic parameters in order to produce the solutions with the lowest objective values. There are six heuristic parameters that are considered. In order of heuristic execution, the heuristic parameters are as follows: initial AMR assignment quantity, unrestricted assignment percent parameter, aircraft team routing algorithm, feasible route limit, feasible route objective and assignment improvement quantity ratio. To assist the reader,  Table A1 in  Appendix A provides a notation guide.

The intent of the initial AMR assignment is to conduct a broad search of the feasible assignment space established by the AMR assignment filter. An increase in the initial AMR assignment quantity, $ζ∈Z+={1,2,3,…}$⁠, increases the likelihood of the aircraft team routing algorithm receiving sufficient assignments to generate feasible routes. Only assignments with feasible routes can enter the improvement cycle. On the other hand, an increase in ζ increases computation time in the aircraft team routing algorithm that might be more efficiently used in the heuristic’s improvement cycle.

For the Army aviation air movement mission assignment, utilization, and routing problem, the best case solution is to support all AMRs with only low-cost helicopter teams. Of course, this is not possible for all scenarios. However, in an effort to explore the assignment space with an emphasis on assignments with all AMRs supported on low-cost helicopter teams, we introduce the unrestricted assignment percent parameter, η ∈ [0, 100]. This parameter specifies a percentage of the initial AMR assignment quantity, ζ, to allow random AMR assignment to any individually feasible helicopter team or to leave the AMR unsupported. For example, for an initial AMR assignment quantity ζ = 1,000 and unrestricted assignment percent parameter η = 25, only 250 of the initial AMR assignments would have the ability to assign AMRs to any individually feasible helicopter team, regardless of cost class, or leave some AMRs unsupported. The remaining 750 assignments would be restricted to assigning AMRs to only individually feasible low-cost helicopter teams.

The two aircraft team routing algorithms considered are the AMR insertion algorithm discussed in Nelson et al. (2023a) and the AMR insertion algorithm with fuel insertion presented in this paper. The latter algorithm is an adaptation of the AMR insertion algorithm to increase refueling options. Both algorithms build on the advanced insertion algorithm described in Häme (2011). At each AMR insertion in the AMR insertion algorithm, the route’s feasibility of AMR time windows, maximum passenger ride time, aircraft flight duration, aircraft capacity, aircraft latest return to the airport, and aircraft fuel level is checked. If one of these constraints is deemed infeasible, the route is not considered in the next AMR insertion. The AMR insertion algorithm assumes helicopter teams fully refuel at every HLZ with refuel capabilities. The algorithm creates a route with refuel stops only if an associated AMR pickup or drop-off at an HLZ with refuel capabilities exists. This feature reduces potential feasible routes and possible feasible AMR assignments.

The AMR insertion algorithm with fuel insertion (see Algorithm 1) introduced in this paper addresses the rigid refueling feature by allowing for refuel stops at HLZs with refuel capabilities regardless if there is an associated AMR pickup or drop-off at the HLZ. The AMR insertion algorithm with fuel insertion introduces two separate feasibility checks. Similar to the AMR insertion algorithm, the first-stage feasibility occurs after each AMR insertion. Unlike the AMR insertion algorithm, this adapted algorithm does not verify aircraft fuel level feasibility in the first-stage feasibility check. Instead, the first-stage feasibility check includes AMR time windows, maximum passenger ride time, aircraft flight duration, aircraft capacity, and aircraft’s latest return to the airport feasibility. Only feasible routes are considered for the next AMR insertion. Upon insertion of all AMR pickups and drop-offs for the assigned AMRs to helicopter team k ∈ K, the algorithm produces a set of complete first-stage feasible routes $S|Nk|k$⁠, where N^k is the set of AMRs assigned to helicopter team k.

For each complete first-stage feasible route $s∈S|Nk|k$⁠, the algorithm checks for aircraft team fuel feasibility. This is accomplished by ensuring that at every node j in complete route s, there is sufficient fuel to travel to node j + 1. If there is insufficient fuel to travel to the next node, the algorithm inserts a refueling stop between nodes j and j + 1. The algorithm selects the HLZ with refuel capabilities, not at node j or j + 1 which minimizes the travel time from node j to the refuel node plus the travel time from the refuel node to node j + 1 as the refuel stop. If there is not sufficient fuel at node j to travel to any HLZs with refueling capabilities, the complete route s is removed from $S|Nk|k$⁠.

The fuel insertion function generates a set of fuel-feasible complete routes, but the potential fuel insertions may have changed the time structure of the route. The fuel-feasible complete routes must go through a second-stage feasibility check to ensure the feasibility of AMR time windows, maximum passenger ride time, aircraft flight duration and aircraft’s latest return to the airport. Notice that the second-stage feasibility differs from the first in that the aircraft capacity need not be checked. The algorithm assumes no passengers board or deplane at the refuel insertions. Upon completion of the second-stage feasibility check, the algorithm either has a set of fully feasible complete routes to calculate routing costs or an empty set of fully feasible complete routes in which the algorithm assigns infinite cost to the route associated with the AMR assignment.

Both the AMR insertion algorithm (Nelson et al., 2023a) and the AMR insertion algorithm with fuel insertion in Section 4.3 have the ability to create the optimal helicopter team routing for a given AMR assignment. This is due to the fact that both algorithms can generate and evaluate every possible AMR route sequencing. However, the number of routes to evaluate becomes intractable as the number of assigned AMRs increases. The largest instances encountered in practice correspond to approximately 100 AMRs (Nelson et al., 2023a). Including fuel insertion does not add to the time complexity of the original AMR insertion algorithm because it occurs outside of its main iterative loop. In order to solve larger problems, it is necessary to limit the number of feasible routes carried forward for the next AMR insertion.

The methodology in which we select τ feasible routes after each AMR insertion iteration to carry forward to the next iteration builds on the work done by Häme (2011) and is discussed in Nelson et al. (2023a). As the value of τ increases, so does the probability of generating a feasible route with a lower routing cost, but at an increased computational cost. We chose three candidate feasible route objectives to select the τ feasible routes to build upon at the next AMR insertion iteration. The first method chooses the τ routes with the smallest flight times. This is aligned with the third term of the problem’s overall objective (Nelson et al., 2023a, see Equation (1)) simplified here as,

and is shown in Equation (2). The other two feasible route objectives attempt to allow more flexibility in subsequent AMR insertions by choosing τ routes with either the maximum total slack time (3) or the maximum of the minimum slack times (4).

Given the routing sequence, r = (r₁, …, r_m), we wish to minimize the time of flight (TOF),

maximize the total slack time (TST),

or maximize the minimum slack time (MST),

where $tj,j′k$ is the time between nodes j and j′ for helicopter team k, l_j is the latest arrival time for the AMR j, and $Ajk(r)$ is the calculated time of arrival at node j.

The improvement cycle attempts to improve y assignments with the lowest overall objective values by attempting to shift unsupported AMRs to helicopter teams. An increase in y provides a greater opportunity to improve more initial assignments and therefore increase the potential to result in a better overall solution. A larger y also results in increased computation time and potentially less of the assignment space explored. We control the value of y by using parameter θ ∈ [0, 1] such that y = ⌊θζ⌋, where ζ is the initial AMR assignment quantity and $⌊x⌋=max{z∈Z|z≤x}$⁠.

Gunawan et al. (2011) describe a sequential experimental approach to tune algorithm parameters. The approach includes screening, exploration, and exploitation phases to further tune parameters in order to improve algorithm performance. Figure 2 illustrates the air movement operations planning heuristic parameter tuning DOE procedure. The purpose of the DOEs is to analyze heuristic performance while varying the heuristic parameters in order to identify the best heuristic parameter settings. We design two scenarios with dissimilar HLZ networks and AMR demand to represent utility helicopter unit air movement operations. We tune the heuristic parameters (see Table 1) under each scenario and compare the resulting heuristic with tuned parameter settings performance. The interested reader can find the DOEs, phase results, and additional details in Nelson (2023) (see Ch. 3 and App C).

The heuristic improvement DOE is a controlled set of tests designed to model and explore the relationship between the heuristic parameters and response variable (JMP and Proust, 2017; Montgomery, 2017). The primary response variable is the resulting overall objective value. Further analysis of the components of the overall objective value includes quantity and priority level of unsupported AMRs, aircraft team utilization penalty, and total flight time. The DOE sizes allow for 80% power for all main effects, second-degree interactions, and quadratic effects of all discrete numeric and continuous effects with 95% confidence for each phase.

The objective of the heuristic is to minimize the sum of weighted penalties of unsupported AMRs, helicopter team utilization and flight time. A heuristic objective formula that represents the mixed integer linear programming objective in Nelson et al. (2023a) is shown in Equation (5). The first summation in the objective accounts for the penalty of leaving AMRs unsupported. Let α be the unsupported penalty weight, b_i be the transformed AMR priority for AMR i, and Π_i be the binary variable with value 1 if AMR i is unsupported and 0 if supported. The second summation in the objective describes the penalties for helicopter team utilization and total flight time. Let β^k represent the utilization penalty for helicopter team k and ϒ^k be the binary variable with value 1 if helicopter team k is assigned one or more AMRs and 0 if assigned zero AMRs to support. Let γ^k be the flight hour penalty for helicopter team k and Φ^k be the total flight hours for helicopter team k.

Similar to the practical application in Nelson et al. (2023a), the AMR priority level in this DOE is transformed through an exponential function with base B = 2. This implies that an AMR of one higher level priority is twice as important as an AMR of the priority level below. Let p_i be the priority level of AMR i as referenced in  Table A2. Then $bi=2(9−pi)$⁠. We set the unsupported penalty weight α = 100, which can be interpreted as leaving an unsupported priority level 9 AMR as equivalent to logging 100 flight hours on a helicopter team with γ^k = 1. Setting α at a high value sets a priority of supporting all AMRs. The utilization penalty for each aircraft team β^k is a calculated value used to balance the commander’s assessed cost of committing an aviation asset versus leaving an AMR unsupported. The calculation follows as $αbi=αB(9−pi)=βk$⁠. Given the commander’s AMR priority level threshold to launch a particular aircraft team for support, it is possible to calculate β^k. This concept is discussed further in Section 6.2.2.

We define the expected AMR flight time for a given scenario as

where the HLZs are in the set $H$⁠, P(pickup = j) is the probability an AMR will originate at HLZ j, P(drop = j′|pickup = j) is the conditional probability the AMR drops off at HLZ j′ given the AMR picks up at HLZ j, and t_jj′ is the flight time from HLZ j to HLZ j′.

We design two scenarios to tune the heuristic procedure with key differences in HLZ network scale and overall AMR volume. For each scenario, we define the HLZ network, refuel nodes, helicopter fleets, and AMR demand characteristics with identical distribution assumptions from Nelson et al. (2023a). The first scenario is a low-density operational environment set in Afghanistan whereas the second scenario features a small urban environment set in Baghdad, Iraq, serving a higher AMR volume. The expected AMR flight time of the Baghdad scenario is 0.1335 h, which differs significantly from that of the Afghanistan scenario’s expected AMR flight time of 0.51 h. Table 2 summarizes the major differences between the scenarios with the subsequent sections providing specific details.

The HLZ network is a two-thirds scaled representation of Regional Command North, Afghanistan. The scaling is in order to allow the helicopter fleet to support a larger number of AMRs and thus further test the heuristic’s capabilities. As seen in Figure 3, there are ten HLZs, of which five have refueling capabilities. HLZs M and Z are hubs, serving as the pickup or drop-off HLZ for many AMRs.

The helicopter fleet consists of six UH-60 Blackhawk helicopter teams stationed at HLZ M. Table 3 displays the helicopter team features. All teams have identical maximum passenger capacity, average cruising speed, and fuel capacity. There are two teams designated as AM with a flight window of 0700–1500. The two PM teams have a flight window of 1500–2100. Note that we assume the PM teams fly part of their mission under night vision goggles and therefore have a maximum duration of 6 h as opposed to the day-only AM team with a maximum duration of 8 h. The quick reaction force (QRF) teams straddle the AM and PM teams’ time windows with a flight window from 1100– 1900 and an 8 h maximum duration.

The two helicopter teams designated with QRF can be considered high-cost teams. QRF helicopter teams are commonly used teams held in reserve, with crews that can rapidly react to any commander-directed missions. QRF teams are given air movement operation missions only when the commander deems the mission is of high enough priority to commit the reserve QRF asset. For this reason, the QRF helicopter teams are given a utilization penalty β^k = 400, ∀k. This utilization penalty can be interpreted as the commander setting the QRF launch threshold equivalent to not supporting a level 7 priority (O-6 colonel or equivalent), two priority level 8 AMRs, or four priority level 9 AMRs since β^k = 400 = (100)2^(9–7) = (100)(2)2^(9–8) = (100)(4)2^(9–9), ∀k.

For each run in the DOE, the number of AMRs is n = 30. The number of AMRs is set to stretch the limits of the low-cost helicopter teams in their ability to support the demand in a moderately large HLZ network. While each run has a fixed number of AMRs, the features of each run’s AMRs will differ. HLZs M and Z are hub HLZs serving as the pickup or drop off HLZ for many AMRs. The AMR feature distributions follow the practical application in Nelson et al. (2023a).  Table A3 displays the Afghanistan scenario’s AMR HLZ pickup and drop-off probabilities.

The number of passengers per AMR is equally distributed between the integers from one to eleven. Each AMR has a 25% probability of having a priority level of 9, and a 25% probability of having a priority level of 8, with the remaining probability equally distributed among priority levels 1 to 7. Finally, each AMR is assigned a time window with equal probability for windows 0700–2100, 1200–1700, or 1700–2100. Finally, the maximum passenger ride time L is set at 4 h.

The Baghdad scenario HLZ network is a true-to-scale representation of the Multi-National Division – Baghdad, Iraq. As seen in Figure 4, the network consists of ten HLZs of which HLZs T and B have refueling capabilities. HLZs T, B, and L are hubs, serving as the pickup or drop-off HLZs for many AMRs.

The helicopter fleet consists of six UH-60 Blackhawk helicopter teams stationed at HLZ T. The fleet is identical to the Afghanistan scenario fleet shown in Table 3 with speed as an exception. Due to the condensed nature of the HLZ network, helicopters travel slower on average in Baghdad than in a more spread-out HLZ network with speeds for all aircraft teams set to 185.2 (km/hr).

For each run in the DOEs, the number of AMRs is n = 50. The number of AMRs is set to stretch the limits of the helicopter teams in their ability to support the demand even with high-cost QRF aircraft teams. HLZs T, B, and L are hub HLZs, serving as the pickup and drop-off HLZ for many AMRs. Due to the proximity of HLZs B and L and the fact they share a common forward operating base, there are no AMRs between the two HLZs.  Table A4 depicts the AMR HLZ pickup and drop-off probabilities for the Baghdad scenario. The expected AMR flight time of the Baghdad scenario is 0.1335 h, which differs significantly from that of the Afghanistan scenario’s expected AMR flight time of 0.51 h.

The assignment of the number of passengers, priority level, and flight window for each AMR follows the Afghanistan scenario methodology as discussed in Section 6.2. Additionally, like the Afghanistan scenario, the maximum passenger ride time L is set at 4 h.

The heuristic improvement DOE sought to tune heuristic parameter settings in order to produce superior solutions to the Army aviation air movement mission assignment, utilization, and routing problem and improve on the heuristic presented by Nelson et al. (2023a). During the initial experiments for the Afghanistan scenario, a feasible route limit (τ) of 1 was not considered a good value and thus excluded in the initial screening range. Subsequent exploration phases showed τ = 1 to be the best value. With this in mind, the screening phase for the Baghdad scenario included this value in the initial DOE range for τ. The impact of this change removed any reason to do a second explore phase for the Baghdad scenario.

As shown Tables 4 and 5, the rigorous DOE process arrived at heuristic parameters tuned to two separate scenarios. The heuristic with tuned parameter settings resulted in solutions with lower objective values than those with its original settings. The tuned parameter settings in both scenarios provided statistically significant evidence of superior performance. Furthermore, the tuned parameter settings gained through separate scenario data sets, although slightly different, proved to produce similar solutions for both scenarios. Hence, using parameter settings tuned with Afghanistan scenario or Baghdad scenario training data is equally beneficial (see Table 6). The interested reader may consult  Appendix B for details on solution quality over time.

The motivated reader may find the instances for these DOEs and associated heuristic solutions in Nelson (2023,  Appendix C, pp. 114–136).

To measure the improvement, we measure the objective value of the original heuristic from Nelson et al. (2023a) and the tuned validation settings for each of the 30 validation instances. Let D be the associated difference in objective values using Equation (5) and let μ_D be the true mean difference. The results of a paired t-test (Devore, 2016) for both scenarios strongly support that the objective value of the original settings is greater than the tuned settings (i.e. μ_D > 0). Table 7 provides the paired t-test results showing both sets of parameters result in improvement over the original parameters.

For the Afghanistan scenario, 19 of 30 instances result in the tuned settings using one less high-cost QRF helicopter. The tuned parameters result in a lower objective value overall in 26 instances; in the four instances where this was not the case, the average difference was only 0.867 flight hours. On average the Baghdad-tuned settings supported all AMRs in all 30 instances where the original settings left 2.33 AMRs unsupported on average.

Numerical experiments with both tuned settings show similar performance both in terms of number of AMRs supported and total flight time. Using parameter settings tuned with either the Afghanistan or Baghdad scenario seems to be equally beneficial. The interested reader can review the numerical experiments in Nelson (2023, App C).

Nelson et al. (2023a) provide an application-sized problem as a proof of concept of the heuristic’s ability to generate feasible assignment and routing solutions in a time period useful to aviation mission planners. We now seek to generate comparable solutions in a condensed time period with tuned parameter settings on the identical scenario from Nelson et al. (2023a). The heuristic uses the Afghanistan scenario tuned parameter settings described in Table 4. Actual problem instances are available from Daniels et al. (2023).

Table 8 provides the results and performance of the heuristic with original parameter settings – taken from Nelson et al. (2023a) – and the heuristic with Afghanistan scenario-tuned parameter settings (this paper) on identical application-sized problems. Both heuristics were able to find feasible solutions, supporting all AMRs for all instances in both 90 AMR and 100 AMR quantity-sized problems. The utilization and AMR support were identical for both heuristics. On average, the heuristic with tuned parameter settings arrived at assignment and routing solutions with 1.46 more hours of flight time, a 7.1% average increase. However, the heuristic with tuned parameter settings arrived at a solution in 22 min on average compared to the average 221-min execution time for the heuristic with original parameter settings. The drastically reduced execution time with minimal solution quality degradation provides aviation mission planners with opportunities to generate multiple courses of action (COAs) and perform additional mission analysis in a shortened mission planning cycle.

This paper sought to improve the air movement operations planning heuristic in order to generate superior solutions in less time. Through developing alternative modular methodologies and a rigorous DOE-based heuristic parameter tuning, we arrived at a fine-tuned heuristic with an average 33% objective improvement over the original heuristic described in Nelson et al. (2023a). The bulk of the objective improvement resulted from the reduced utilization of high-cost helicopter teams in the Afghanistan validation data set and through superior AMR support in the Baghdad validation data set. Improvements of this nature preserve costly and scarce army aviation, maintenance, and personnel assets while providing more services to supported units. Reduced high-cost aircraft team utilization frees the teams to conduct other command-directed missions and ultimately provides superior capabilities to the supported ground commanders. Additionally, during the Afghanistan scenario validation phase, the fine-tuned heuristic was able to provide a feasible solution in an average of 8.03 min, which is a 70% reduction in time compared to the original heuristic. Rapidly generated solutions enhance aviation mission planners’ ability to quickly generate COAs to meet the commander’s requirements. The dramatically reduced computation time also makes it feasible to employ distinct parameter sets for the objective function (e.g., α, B, β^k, γ^k) to quickly generate multiple COAs for further analysis and/or refinement by the planners (Nelson et al., 2022).

In lieu of performing a full DOE approach to air movement operations planning heuristic parameter tuning, several general guidelines can be derived from experimentation. In operational scenarios where the number and type of AMRs exceed the support capabilities of the aircraft fleet, planners may encounter challenges in efficiently assigning and routing aircraft to support all AMRs or minimize the number of unsupported AMRs based on priority. The ability of the heuristic to generate feasible solutions would greatly aid in planning. To generate feasible solutions for such operational scenarios, users should configure the parameters to evaluate as many assignments as possible. Consequently, it is advisable to set the initial AMR assignment quantity (ζ) high, the unrestricted assignment percent parameter (η) to 100, the feasible route limit (τ) to 1, and minimize the assignment improvement quantity ratio (y).

Alternatively, if the aircraft fleet can accommodate numerous assignments with feasible routing, it may be advantageous to minimize helicopter team utilization and route time. This can be accomplished by reducing the unrestricted assignment percent parameter (η) and increasing the feasible route limit (τ) and assignment improvement quantity ratio (y).

There are many opportunities to further improve the air movement operations planning heuristic. It is reasonable to believe that the parallelization of the aircraft team routing process would significantly improve computational speed. Additionally, the heuristic should output useful products for the Army aviation mission planner and operator. To add additional sophistication, the heuristic could introduce flight characteristics associated with altitude and air temperature. Future efforts should consider approaches to adapt the heuristic parameters dynamically, or adjust the parameters based on scenario characteristics. Machine learning techniques may be worth exploring to improve heuristic sub-modules shown in Figure 1. Also, meta-heuristic techniques could be used to more effectively utilize improvements to instances found using the insertion algorithm. For example, evolutionary programming could combine the best portions of several instances to generate better solutions, while tabu search could more efficiently use the results of the insertion improvement algorithm. Future research should also consider designing a robust hyperparameter study focused on finding minimal regret hyperparameters for this heuristic across a broad range of operational scenarios (Eldar and Merhav, 2004; Yu and Zhu, 2020).

Finally, beyond solving the Army aviation air movement mission assignment, utilization, and routing problem, this heuristic has the potential to be integrated into additional decision support or planning models where estimating aviation demands or utilization is an important consideration. For example, the heuristic could assist in determining the best allocation of aviation resources to task forces (Nelson et al., 2023b). More generally, future efforts could apply similar types of refueling constraints to problems related to routing battery-powered vehicles that require regular recharging.

The first author was supported by an Omar N. Bradley Officer Research in Mathematics Fellowship. Additionally, Lieutenant Colonel Tyler Espinoza provided relevant and current insights into US Army aviation air movement operations. We also thank the anonymous reviewers for their comments and suggestions which led to improvements in the quality of the paper.

Table A1,Table A2 

Additional scenario descriptions are available in Nelson (2023).

Table A3,Table A4 

During heuristic improvement through parameter tuning design of experiments, we fixed each run at 60 min. Throughout the run time, the heuristic had the ability to update the solution and improve the overall objective. We chose the 60-min run time as a time frame that would be acceptable for an aviation air mission operations planner during typical operational conditions. We also analyze how the quality of the solution improves over a longer period of time. This will give further insight into how the mission planner could choose to use the air movement operations planning heuristic based on mission and planning conditions.

In this analysis, we use the heuristic with Afghanistan scenario tuned heuristic parameter settings as described in Table 6. We allow the heuristic to run for six hours on each of the thirty Afghanistan Scenario validation data runs described in Section 6.2.

Figure A1 displays the results of the quality of solution over time analysis. The lines show the best objective values for each of the 30 runs over the six-hour execution time. An objective value decrease of 400 or more represents a solution that uses one less high-cost QRF helicopter team. Smaller objective value decreases are gained through route time improvements. The graph shows five runs that had significant objective value improvements (a decrease of at least 400) after the 60-min mark. This leaves the heuristic obtaining the best solution for twenty-five of the thirty runs within the first hour. Furthermore, the heuristic obtained its best solution for all runs within 150 min. Following the results of this analysis, the aviation mission planner should have confidence that a 60-min run time will have greater than 83% probability (confidence interval [65.3%, 94.4%]) of finding the best heuristic solution and even greater probability (confidence interval [88.4%, 100%]) with a 150 min run time.

Figure A1