Purpose –The purpose of this study was to create an air movement operations planning model to rapidly generate air mission request (AMR) assignment and routing courses of action (COA) in order to minimizeunsupported AMRs, aircraft utilization and routing cost. Design/methodology/approach –In this paper, the US Army Aviation air movement operations planning problem is modeled as a mixed integer linear program (MILP) as an extension of the dial-a-ride problem (DARP). The paper also introduces a heuristic as an extension of a single-vehicle DARP demand insertion algorithm to generate feasible solutions in a tactically useful time period. Findings –The MILP model generates optimal solutions for small problems (low numbers of AMRs and small helicopter fleets). The heuristic generates near-optimal feasible solutions for problems of various sizes (up to100 AMRs and 10 helicopter team fleet size) in near real time. Research limitations/implications –Due to the inability of the MILP to produce optimal solutions for mid- and large-sized problems, this research is limited in commenting on the heuristic solution quality beyond thenumerical experimentation. Additionally, the authors make several simplifying assumptions to generalize the average performance and capabilities of aircraft throughout a flight.JDAL 7,1 2 © In accordance with section 105 of the US Copyright Act, this work has been produced by a US government employee and shall be considered a public domain work, as copyright protection is notavailable. Published in Journal of Defense Analytics and Logistics . Published by Emerald Publishing Limited. The first author was supported by an Omar N. Bradley Officer Research in Mathematics Fellowship. This paper greatly benefited from feedback provided by helpful and detailed reviewers. Additionally,Lieutenant Colonel Tyler Espinoza provided relevant and current insights into Army aviation airmovement operations. Finally, the authors greatly appreciate the efforts of Rebecca Daniels and JackWerner. Disclaimer: Lieutenant Colonel Russell Nelson ’s contribution was performed as part of his official duties as an employee of the United States Government. The views expressed in this paper are those ofthe authors and do not reflect the official policy or position of the United States Army, the Department ofDefense, or the United States Government.The current issue and full text archive of this journal is available on Emerald Insight at: https://www.emerald.com/insight/2399-6439.htm Received 10 November 2022 Revised 16 March 202323 March 2023Accepted 24 March 2023 Journal of Defense Analytics and Logistics Vol. 7 No. 1, 2023pp. 2-28 Emerald Publishing Limited 2399-6439 DOI10.1108/JDAL-11-2022-0013 Originality/value –This research is the first to solve the US Army Aviation air movement operations planning problem via a single formulation that incorporates multiple refuel nodes, minimization of unsupported demand by priority level, demand time windows, aircraft team utilization penalties, aircraft teamtime windows and maximum duration and passenger ride time limits. Keywords Dial-a-ride problem, Heuristic, Multiple refuel nodes, Demand priority, Helicopter routing, Vehicle utilization, Aircraft, Military aviation Paper type Research paper 1. Introduction 1.1 Air movement operations The United States Army uses Army Aviation helicopters to conduct air movement operations to move personnel, supplies and equipment throughout the depth and breadth of the area of operations (AO) ( Department of the Army, 2020b ). The purpose of air movement operations is to enable the groun d force to sustain the tempo of operations, extend tactical reach, maneuver in areas restricted by threat or terrain and sustain operations to maintain a position of relative advantage over the enemy ( Department of the Army, 2020a ). During military operations in Iraq, the US Army regularly conducted air movements to transport personnel and supplie s between helicopter landing zones (HLZs) on forward operating bases (FOBs) in order t o avoid ground-based enemy threats and the large logistics tail involved in conducting ground convoy operations. In Afghanistan, US air movement operations not only reduced the requirements of convoy operations but also permitted the transportation of personnel a nd supplies over mountainous and seasonally impassible terrain. In large-scale combat op erations, commanders use air movements to preposition forces prior to joint forced entries, move barriers and munitions in the defense and move fuel, ammunition and personnel ov er extended lines of communications in the offense ( Department of the Army, 2020b ). 1.2 Air movement request process The process in which a unit requests helicop ter support from an Army Aviation unit is called an Air Mission Request (AMR). Army Techniques Publication 3 –04.1 Aviation Tactical Employment ( Department of the Army, 2020a ) outlines the AMR processing procedure and general timeline. It is impo rtant for the reader to note that the AMR procedure is not regulatory in nature and therefore can be altered to suit the units ’needs. The AMR process starts with the supported company routing an AMR through their battalion operations shop (S- 3). The supported battalion ’s S-3 conducts quality control and consolidates AMRs to submit to the next higher unit, normally a brigade. The brigade aviation element (BAE) is the supported brigade ’s aviation experts. The BAE is the filter for all air movements and prioritizes all AMR s to optimize the best use of helicopter assets. The BAE then routes AMRs to the next higher c ommand, normally a division. The division tasks AMRs to the aviation headquarters, normally an aviation brigade for approval and execution. The normal processing time from the aviation brigade ’s receipt of the tasking to the desired date of air movement is 96 h. The aviation brigade tasks the AMR to subordinate aviation battalions/task forces based on mission type, AO, special equipment required and other considerations. The aviation battalion S-3 tasks the AMR to an aircraft team and determines a route for the aircraf t team to complete all assigned AMRs meeting all AMR requirements. Once the aviation battalion assigns the AMR to a team and determines a route, the aviation unit publishes a daily air movement table to communicate the means of AMR completion to the supported unit no later than 12 h prior to the desired time of air movement. Figure 1 provides a graphical representation of the AMR process and general timeline.Air movement assignment and routing 3 Following the normal AMR processing timelin e, the aviation briga de should know the AMR demands 96 h prior to execution. However, due to the nature of competing requirements and realities of dynamic conflic ts, the aviation battalion typically tasks and routes aircraft teams 24 h prior to mission execution. This allows the battalion to have the most up-to-date understanding of external de mands (AMRs), internal resources (aircraft teams) and the network (AO). This leaves aviation battalion mission planners approximately 12 h to task and route aircraft teams prior to publishing the air movement table. Currently, mission plan ners use manual methods to task and route aircraft teams. This manual process is time - and/or resource-consuming and produces suboptimal solutions. As reported by a cu rrent general support aviation battalion commander, it is not uncommon for a team of b attalion air movement operations mission planners to dedicate over five hours to generate a plan supporting a day ’s worth of AMRs (Espinoza, 2022 ). These inefficiencies result in unsupp orted AMRs, additional personnel, maintenance and sustainment resource require ments, as well as additional risk to aircrew and passengers. Ultimately, inefficiencies reduce the capacity of the supported unit (Nelson et al., 2022 ). 1.3 Air movement operations air mission request priority The supported unit assigns the AMR a priority based on theater priorities detailed in the Commander ’s Mission Priority List ( Mogensen, 2014 ). The purpose of AMR priorities is to guide aviation mission planners on which AMRs to leave unsupported when aviation assets are unable to meet all AMR demands, despite being approved by the aviation headquarters. If an AMR is unsupported, the requesting unit must submit another AMR or appeal the decision to their higher headquarters. Table 1 depicts an example AMR priority list. The aviation unit, along with their higher headquarters, determines how to weigh the penalty of allowing an AMR to go unsupported by priority level. Ultimately, the aviation unit must weigh the penalty of leaving AMRs unsupported with the options of launching additional aircraft teams and incurring additional flight hours along with the resources required for either action. Figure 1. Air mission request processJDAL 7,1 4 2. Literature review The US Army Aviation air movement operations planning problem is closely related to the dial-a-ride problem (DARP) as described in Cordeau and Laporte (2007) and most recently surveyed in Hoet al.(2018a) andNasri et al.(2021) . DARP consists of creating mvehicle routes forncustomers with pickup and delivery requests between origins and destinations, where n>m. The objective is to plan a set of mminimum cost vehicle routes while supporting as many customers as possible, under a set of constraints. The most common DARP example arises in door-to-door transportation services for the elderly, or patient transport by a fleet of vehicles ( Parragh, 2011 ). Although not immediately obvious, this is similar to a fleet of helicopters providing HLZ-to-HLZ service for Soldiers, though helicopters have unique features not possessed by ground-based vehicles. de Alvarenga Rosa et al.(2016) andMenezes et al.(2010) build on Fiala Timlin and Pulleyblank (1992) to incorporate many of these features in their DARP model, including maximum seat capacity, maximum fuel capacity and maximum route time, among other helicopter-specific features. Their objective also seeks to minimize helicopter fleet utilization as well as minimize the cost of helicopter routes. Unlike the DARP problem, many military applications prioritize other objectives over cost with approaches optimizing mission objectives, readiness, robustness, resilience and other factors (Kirby et al., 2020 ;Longhorn et al., 2021 ;Longhorn and Stobbs, 2021 ). One unique feature of modeling helicopter ro uting is the impact of having a limited set of refueling nodes. In the general DARP model, refu eling is not considered. In fixed-wing DARP problems, such as Brown et al.(2013) , the authors assume that vehicles may refuel at any landing node. This is a valid assumption as fixed-wing ass ets generally land at airports with refueling services. An additional DARP refueling method is to assume refueling is available only at the depot ( Machado et al., 2019 ) which results in each vehicle ’s route consisting of several trips with periodic refueling at the depot. The model in this paper considers a more realistic setting encountered by Army aviation helicopters, in which there is a limited number of HLZs with refueling capabilities. Multiple vehicle routing problems (MVRP) of unmanned aerial vehicles (UAVs) ( Sundar and Rathinam, 2012 ;Sundar et al., 2016 ), service network design optimization for helicopters ( Mogensen, 2014 ) and DARP with electric vehicles (EVs) ( Masmoudi et al., 2020 ;Tekil- Erg €unet al., 2021 ) also share the feature of having a set of refueling nodes. Zeng et al. (2022) provide an additional unique approach to refueling electric UAVs via a nested vehicle routing problem. The refueling component of our model draws from this previous research. The general DARP model does not allow for unsupported demand and therefore does not seek to minimize unsupported demand or maximize supported demand. In order to designate certain demands as more important than others, we use the concept of demand priority. Hanne et al. (2009) use demand priority to weigh penalties for patient inconvenience, defined as patient earliness, lateness, driving time and total transport time. In their work, demandAMR mission Priority Downed Aircraft Recovery 1 (highest) Emergency Leave 2General Officer Movement 3 Military Working Dog 4 Critical Equipment Repair 5Religious Services 6O-6 Colonel or Equivalent 7Rest and Recovery Leave 8Other 9 (lowest) Source(s): Table from Mogensen (2014)Table 1. Air mission request priorityAir movement assignment and routing 5 was always supported, but not necessarily in the desired time window. Souza et al. (2022) use demand priority to prioritize sequencing of demand servicing. In realistic Army Aviation air movement operations, there will often be more demand than the helicopter fleet can accommodate. Therefore, it is more appropriate to maximize the supported demand by priority level as demonstrated in Brown et al. (2013) where they optimize intratheater military fixed-wing airlift. Mogensen (2014) also seeks to maximize supported demand by establishing tiered priority levels for a heterogeneous fleet. An alternative approach is to minimize unsupported demand by priority level as seen in Yak ıcıet al. (2018) in their effort to route rotary wing assets in amphibious-ready groups to transport personnel and cargo. Solution methods for the dial-a-ride-problem vary from tabu search heuristics proposed byCordeau and Laporte (2003) and improved by Hoet al. (2018b) to large neighborhood search algorithms described in Masmoudi et al. (2020) andJain and Van Hentenryck (2011) . Tripathy et al. (2017) use an ant colony approach, while Menezes et al. (2010) and de Alvarenga Rosa et al. (2016) employ a GRASP heuristic. Mogensen (2014) uses a recursive path generation heuristic algorithm to solve their multi-commodity network flow approach. Our paper draws from the single vehicle DARP advanced insertion algorithm described in H€ame (2011) . 3. Mathematical model 3.1 Assumptions In order to develop a model to optimize helicopter routing, we make the following assumptions: /C15Each helicopter team starts and terminates at an airport (node). /C15An air mission request (AMR) is defined as a set of passengers with a shared pickup and drop off HLZ, time window constraints and priority level. /C15Helicopter capacity is solely limited by passenger seats. Cargo weight and volume canbe converted to passenger equivalency. /C15Each AMR has a single time window in which it is to be picked up from its pickup location and delivered to its drop off location. /C15Each passenger has the same maximum amount of time they can be on a helicopter (ride time). /C15Service time (ground delay) is a function of the HLZ and includes the time to refuel atrefueling nodes. /C15Helicopter teams can shut down the aircraft engines at any HLZ to conserve fuel while waiting for an AMR window to open. /C15Reserve fuel is omitted from the maximum fuel capacity, fk. Flight planners create routes that allow helicopters to land at a refueling point prior to falling below a reserve fuel level, dictated by the mission profile. The maximum fuel capacity in this model fk does not include reserve fuel, therefore it replicates the fuel capacity considered by mission planners. /C15Helicopter capacity, flight speed and fuel burn rate are constant throughout the helicopter team ’s flight period. /C15An AMR can be left unsupported at a penalty in proportion with the unsupported AMR ’s priority level.JDAL 7,1 6 3.2 Mathematical model 3.2.1 Mathematical model parameters and variables. This mathematical model follows from the dial-a-ride problem work by Cordeau and Laporte (2007) and capacitated helicopter routing problem considered by de Alvarenga Rosa et al.(2016) . The refueling constraints follow work done in Sundar and Rathinam (2012) ,Masmoudi et al.(2020) andTekil-Erg €unet al.(2021) . The capacitated helicopter routing problem (CHRP) can be represented by a complete graph G(V;A) defined by a set of nodes, V5{P,D,E}, and edges, A.Pis the set of AMR pickup nodes, P5{1, 2, ...,n}.Dis the set of AMR dropoff nodes, D5{nþ1,nþ2,...,2n}.Eis the set of refueling nodes, including the starting node a52nþ1 and the ending node z52nþ2 ,w h i c ha r eb o t hl o c a t e da tt h ea i r p o r t . E5{2nþ1, 2nþ 2,...,2nþjEj}. A passenger load, qi, is associated with each node i∈Vwithqa5qz50,qi≥0f o r i51,...,nandqi5/C0qi/C0nfori5nþ1,...,2n, and a service time dij≥0w i t h diz50. Each helicopter team has the following parameters: Qk: maximum passenger seat capacity of helicopter team k∈K; Tk: maximum mission duration (in hours) of helicopter team k∈K.Tkis defined as the time of final return to the airport minus the time of the first departure to the airport. The value is set by the user, but is usually the minimum of crew duration limitations and aircraft maintenance requirements; sk: average flight speed of helicopter team k∈K; HDk: earliest time of departure from the airport of helicopter team k∈K; HRk: latest time to return to the airport of helicopter team k∈K; fk: maximum fuel capacity (in hours) of helicopter team k∈K. Each node i∈Vhas the following parameters: qi: number of passengers boarding or deplaning at node i∈P∪D,(∀i∈P,qi5/C0qnþi); dij: service time at node jwhen departing node i,(i,j∈P∪D); [ei,li]: time window of node i∈P∪D; bi: transformed priority of AMR associated with node i∈P. The transformation converts AMRs ’priority level into weights that describe the penalty of not supporting AMRs compared to those of different priority levels; L: maximum ride time for each passenger. The graph G(V;A) has the following parameters: cij: distance between nodes iandjfori,j∈V; tk ij¼cij sk: time between nodes iandjfor helicopter team k∈K,i,j∈V. The decision variables for the proposed model are as follows: Xk ijis the binary variable equal to 1 if helicopter team k∈Kflies from node i∈Vto node j∈V. Otherwise, it is equal to 0; Uk iindicates the time the helicopter team k∈Kcompletes service at node i∈V; Wk iindicates the number of occupied seats after helicopter team kvisits node i∈V; Rk iindicates the ride time of passenger i∈Pon helicopter team k∈K; Fk iindicates the amount of fuel (in hours) of helicopter team k∈Kwhen departing node i∈V.Air movement assignment and routing 7 It is important to note that each AMR has a unique pickup node i∈Pand drop off node nþi∈P. Multiple AMRs may have a common pickup or drop off HLZs. In these cases, the nodes will be unique, but the distance between the nodes at the same HLZ will be zero. In other words, each HLZ can be associated with several nodes that have the same geographic location. The service time, dij, can be considered the amount of ground time needed to board or deplane passengers. In this model, we assume the amount of ground time required is a function of the HLZ, not the number of passengers boarding/deplaning or the number of AMRs supported at the HLZ. Therefore, the service time is only included when a helicopter team arrives at an HLZ at a geographically separate location from the previous node. An extremely small time of service is added when a helicopter team supports several AMRs by traveling to nodes in the same geographically located HLZ. Although this small amount of time has no impact on the realistic modeling, it allows Constraints (10) to prevent subtours. 3.2.2 Mathematical model formulation. The following formulation adapts Cordeau and Laporte (2003) to fit the requirements of the US Army Aviation air movement operations planning problem. The model minimizes the overall objective, Eq. (1) , while ensuring. /C15Every route starts and ends at the airport; /C15For every AMR i, nodes iandiþnbelong to the same route and node iþnis visited later than node i; /C15T h el o a do fh e l i c o p t e rt e a m kdoes not exceed the maximum seat capacity Qkat any time; /C15The total duration of route kdoes not exceed the maximum route duration Tk; /C15The service at node ibegins in the interval [ ei,li]; /C15Every helicopter team kleaves the airport and returns to the airport in the interval [ HDk,HRk]; /C15The ride time of any passenger does not exceed L; and /C15The fuel level of helicopter team k, does not drop below 0 at any time. 3.2.3 Mathematical model. Objective: minαX i∈PX j∈VbiX1 ijþX k∈KβkX j∈VXk ajþX k∈KγkX i∈VX j∈Vtk ijXk ij (1) Subject to:X k∈KX j∈Vnfa;zgXk ij¼1ð∀i∈PÞ (2) X j∈VXk ji/C0X j∈VXk ij¼0ð∀i∈Vnfa;zg;k∈KÞ (3) X j∈VXk ij/C0X j∈VXk nþi;j¼0ð∀i∈P;k∈KÞ (4) X i∈VXk ai¼X i∈VXk izð∀k∈KÞ (5) X i∈VXk ia¼0ð∀k∈KÞ (6) X j∈VXk zj¼0ð∀k∈KÞ (7)JDAL 7,1 8 X j∈VXk ij≤1ð∀i∈E;k∈KÞ (8) Xk ij∈f0;1gð∀ði;jÞ∈A;k∈KÞ (9) Uk j≥/C16 Uk iþdijþtk ij/C17 Xk ijð∀ði;jÞ∈V;i≠j;k∈KÞ (10) Uk nþi/C0Uk i≥0ð∀i∈P;k∈KÞ (11) Uk z/C0Uk a≤Tkð∀k∈KÞ (12) Uk a≥HDkX i∈VXk aiðk∈KÞ (13) Uk z≤HRkX i∈VXk izþMU1/C0X i∈VXk iz ! ðk∈KÞ (14) ei≤Uk i≤lið∀i∈V;k∈KÞ (15) Uk nþi/C0Uk i≤Rk i≤Lð∀i∈P;k∈KÞ (16) Wk j≥/C16 Wk iþqj/C17 Xk ijð∀ði;jÞ∈V;k∈KÞ (17) 0≤Wk i≤Qkð∀i∈V;k∈KÞ (18) Wk a¼Wk z¼0ð∀k∈KÞ (19) Fk j/C0Fk iþdijþtk ij≤Mk F/C16 1/C0Xk ij/C17 ð∀i∈V;j∈P∪D;k∈KÞ (20) Fk j/C0Fk iþdijþtk ij≥/C0Mk F/C16 1/C0Xk ij/C17 ð∀i∈V;j∈P∪D;k∈KÞ (21) Fk i¼fkð∀i∈E;k∈KÞ (22) Fk i/C0tk ij≥/C0Mk F/C16 1/C0Xk ij/C17 ð∀i∈V;j∈E;k∈KÞ (23) The objective function, Eq. (1) , is a minimization function represented by three terms. The first term penalizes each unmet demand (AMR) by a penalty α> 0 multiplied by the transformed priority of the air mission request bifori∈P. The model transforms the AMR priority through an exponential function with base Bso that an AMR of one higher level priority is Btimes as important as the AMR one priority level below. For the priority levels listed in Table 1 , the transformed priority is bi¼Bð9/C0piÞ; (24) where piis the priority level of AMR i. The first helicopter team k∈Kis a virtual helicopter, capable of completing all AMRs. An AMR fulfilled by the first helicopter team is equivalent to an unsupported AMR. Hence, the first term in Eq. (1) penalizes each unfulfilled AMR ðX1 ijÞ by the AMR specific transformed priority ( bi) and a penalty weight α. The unsupported AMR penalty weight αis set to enforce the stakeholders ’priority of supporting AMRs versus the use of an additional helicopter team. The second term enforces a utilization penalty βkof using helicopter team k∈K. The model uses the utilization penalty for each aircraft team,Air movement assignment and routing 9 βk¼αbi¼αBð9/C0piÞ; (25) to balance the decision maker ’s assessed cost of committing an aviation asset versus leaving an AMR unsupported. Given the commander ’s AMR priority level threshold to launch a particular aircraft team for support, it is possible to calculate βk. The third term penalizes the total flight time of each helicopter team k∈Kbyγk. Constraints (2) ensure all boarding nodes are served by a helicopter team. Constraints (3) ensure the flow conservation restriction. Constraints (4) define the requirements where the helicopter team k∈Kthat visits the pickup node i∈Pmust visit the associated drop off node nþi∈D. Constraints (5) guarantee that each utilized helicopter team starts and ends its route at the airport. Constraints (6) and (7) ensure a helicopter does not return to the airport starting node or depart from the airport terminal node, respectively. Constraints (8) ensure each refueling node can be used at most once by each helicopter team. Constraints (10) define the completion of service time at node j. Note, the helicopter team moving from node to node within the same geographic location will incur a very small service time ( dij50.001) with no travel time ðtk ij¼0Þ. Constraints (11) define the precedence constraints where the helicopter team kmust first visit a demand pickup node i∈Pbefore the associated demand drop off node j5iþn,j∈D. Constraints (12) ensure the time helicopter team k∈Kis on a mission does not exceed the maximum allowed duration for the helicopter team. Constraints (13) and (14) ensure each helicopter team departs the airport after the earliest time of departure and returns prior to the latest time to return, where MU¼max k∈KðHRkÞ. Constraints (15) ensure the passenger is picked up and dropped off within the AMR time window. Constraints (16) define the total ride time for the passengers picked up at node i. Note that the ride time of passenger Rk iis defined as the time incurred between the helicopter team departing the passenger ’s pickup node and departing the passenger ’s drop off node. The ride time of a passenger may include a ground service time at the passenger drop off node. Additionally, Constraints (16) ensure the passenger ride time does not exceed the maximum ride time. Constraints (17) define the number of passengers on helicopter team kwhen departing node j. Constraints (18) define the domain of the number of occupied seats to ensure the helicopter team k∈Kdoes not exceed the maximum seat capacity. Constraints (19) guarantee the helicopter team departs the airport and returns to the airport without passengers. Constraints (20) and (21) define the fuel remaining for helicopter team kwhen departing a pickup or drop off node j.L e t Mk F¼fkþmax i;j∈Vðtk ijÞ. This ensures that the remaining fuel in helicopter team kafter departing node jisFk j¼Fk i/C0dij/C0tk ij. Constraints (22) ensure helicopter team kdeparts the refuel nodes with maximum fuel. Constraints (23) require a helicopter team k to have sufficient fuel to fly from a pickup or drop off node to a refuel node. Constraints (22) ensure helicopter team kdeparts the refuel node with maximum fuel. Constraints (23) require a helicopter team kto maintain sufficient fuel to fly to the nearest refuel node. 3.2.4 Constraint linearization. Since Constraints (10) and (17) are nonlinear they are reformulated as linear constraints, similar to the formulation in de Alvarenga Rosa et al. (2016) . Let LU¼HRkþdijþtk ijandLW5max{ Qk,Qkþqi}. Uk j≥Uk iþdijþtk ij/C0LU/C16 1/C0Xk ij/C17 ði;j∈V;k∈KÞ (26) Wk j≥Wk iþqj/C0LW/C16 1/C0Xk ij/C17 ði;j∈V;k∈KÞ (27) Constraints (26) and (27) replace (10) and (17), respectively.JDAL 7,1 10 4. Heuristic 4.1 Heuristic overview The mathematical model outlined in Section 3.2.1 provides an optimal solution to the US Army Aviation air movement operations planning problem. However, as the number of AMRs or helicopter teams increases, the mathematical model becomes intractable. This paper proposes an air movement operations planning heuristic to provide quality feasible solutions in a time period useful to the air movement operations mission planner. The heuristic consists of sequenced modular functions with decision modules, as seen in Figure 2 . The heuristic seeks to find the AMR assignment and team routing that results in the best objective while not violating the formulation described in Section 3.2.2 . 4.2 Initial solutions 4.2.1 AMR assignment filters. With nAMRs and jKjaircraft teams, there are jKjnways to assign AMRs to helicopter teams. For any problem of scale, this full enumeration of assignments is not achievable. The first attempt to reduce the number of possible assignments is to filter AMRs that can be feasibly supported by each aircraft team. The three assignment filter criteria are capacity, time windows and total duration. For the capacity criteria, we ensure the number of passengers for the AMR does not exceed the maximum capacity of the helicopter team, qi≤Qk. The time window filter considers both the AMR time window and the aircraft team time window to ensure there is sufficient overlap. We first ensure the helicopter team is able to depart the airport with sufficient time to travel to the pickup HLZ prior to the AMR ’s latest pickup time HDk≤li/C0tk ai. Next, we ensure it is possible to pick up the AMR within its time window, travel to the drop off HLZ, include the service time at the drop off HLZ, and travel to the airport prior to the latest time to return to the airport, eiþtk i;iþnþdi;iþnþtk iþn;z≤HRk. Lastly, we ensure the total time to support the AMR, including travel and service times, is less than the helicopter team ’s maximum total duration, tk aiþdaiþtk i;iþnþdi;iþnþtk iþn;z≤Tk. The output of the assignment filter is a feasible set of AMRs for each aircraft team. 4.2.2 Initial AMR assignment. The AMR assignment filter outputs a set of AMRs for each aircraft team, which are individually feasible. In other words, for each aircraft team, there is a list of AMRs the team can support when considering only supporting the individual AMR. The initial AMR assignment module generates a set numbe r of random assignments based on this set of AMRs for each aircraft team. The intent of the initial AMR assignment is to generate a broad Figure 2. Heuristic conceptAir movement assignment and routing 11 search of the assignment space. The initial AMR a ssignments are then passed to the aircraft team routing procedure. 4.2.3 Aircraft team routing. After the AMR assignment step, we now have a list of assignments with AMRs assigned to helicopter tea ms or left unsupported. The goal of the aircraft team routing step is to find the lowest cost feas ible route for each aircraft team, given the AMR assignment. This section describes the aircraft team routing procedure by first giving an overview of the AMR insertion algorithm. Next, it goes into further detail on how each potential routing sequence is evaluated after each AMR insertion using the AMR routing feasibility criteria. Finally, an insertion function heuristi c is introduced in order to allow problem scaling. 4.2.3.1 AMR insertion algorithm. For each assignment, let Nkbe the set of AMRs assigned to aircraft team k∈K, with Nk¼fnk 1;...;nk jNkjg. To solve the helicopter team routing given an AMR assignment for each helicopter team, we adapt the advanced insertion algorithm that H€ame (2011) uses to solve the static single vehicle dial-a-ride problem. The AMR insertion algorithm creates routes by considering all possible AMR pickup and drop off sequences through an insertion function. The insertion function adds an AMR ’s pickup and drop off placement into an existing feasible sequence one AMR at a time while ensuring pickup and drop off precedence. After each AMR insertion, the route is checked for feasibility. Only feasible routes are considered for the next AMR insertion. See the following subsection for a discussion on routing feasibility. If at any point in the AMR insertion algorithm, there is no feasible sequence to add the current AMR into consideration, the route is given an infinite cost and the algorithm terminates. If it is possible to sequence all AMRs in a feasible sequence, the completion of the AMR insertion algorithm results in a set of feasible routes for evaluation. We then save the routing cost and route (sequence of AMR pickup/ drop off) for the feasible route that results in the lowest routing cost. See Algorithm 1 for the AMR Insertion Algorithm pseudocode. 4.2.3.2 AMR routing feasibility criteria. At each AMR insertion, the feasibility of the new sequence is verified. The AMR insertion Algorithm accounts for every route starting and stopping at the airport and the precedence constraint outlined in Section 3.2.2 . Therefore, we only need toJDAL 7,1 12 check feasibility with respect to AMR time windows, maximum passenger ride time, aircraft team flight duration, capacity, latest return to the airport and fuel level AMR time windows . LetAk jðrÞbe the time aircraft team karrives at node jin sequence r5 (r1,r2,...,rm). In order for a sequence to be feasible, Ak jðrÞ≤lrj∀jin the sequence, where lrjis the latest arrival time at node rj. We calculate Ak jðrÞrecursively with Ak jðrÞ¼maxn Ak j/C01ðrÞ;erj/C01o þtk rj/C01;rj;forj¼1; (28) Ak jðrÞ¼maxn Ak j/C01ðrÞþdrj/C02;rj/C01;erj/C01o þtk rj/C01;rj;forj≥2; (29) where Ak 0ðrÞ¼HDk, which is the earliest departure time from the airport for helicopter team k. This is different from the MILP formulation, where Uk acan take values other than HDk. The heuristic makes a simplifying assumption that each aircraft team will start the route at the earliest departure time. We denote di,jas the ground time at node jwhen arriving from node i. Note that there is no ground time at the airport. We assume that a helicopter team can arrive at a node early and wait for the earliest arrival time to depart. If erj/C01>Ak j/C01ðrÞþdrj/C02;rj/C01, the helicopter will wait at node j/C01 until erj/C01. Maximum passenger ride time . Let Rnk ibe the ride time for the passengers on AMR i assigned to helicopter team k. In order for a sequence to be feasible Rnk i≤L;∀i∈Nk.W e define passenger ride time as the time between departure after passenger pickup and passenger drop off at the destination. We calculate Rnk iby subtracting the maximum of the earliest pickup time for AMR iand the arrival time for AMR ipickup plus the service time from the drop off time of AMR i. Aircraft flight duration. In order for the sequence rto be feasible, the route duration must be less than or equal to the maximum route duration for helicopter team k. We calculate the route duration by subtracting the time of the first airport departure from the time of the last arrival to the airport, Ak 2jNkjþ1ðrÞ/C0Ak 0ðrÞ≤Tk. Aircraft capacity . We define Wk jto be the total number of passengers on board the aircraft team kwhen departing the jth node of the route. In order for the route to be feasible, Wk j≤QK∀jin the route, where Qkis the maximum capacity for helicopter team k.W e calculate Wk jrecursively with Wk j¼Wk j/C01þqrj; (30) where Wk 0¼0 and qrjis the number of passengers loading or unloading at node rj. Aircraft latest return to airport . Under current assumptions, the helicopter team departs at the earliest departure time and the maximum flight duration is less than or equal to the difference between the earliest and latest time to depart/return to the airport. Therefore, it is not necessary to check if the sequence allows for the helicopter team to arrive at the airport no later than the latest time for arrival, HRk. Aircraft fuel level . We define Fjto be the level of fuel (in hours) of the helicopter team when arriving at the jth node of the route. In order for the route to be feasible, Fj≥0∀jin the route. We calculate Fjrecursively with Fj¼Fj/C01/C0drj/C02;rj/C01/C0tk rj/C01;rj; (31)Air movement assignment and routing 13 where drj/C02;rj/C01is the ground time at the last HLZ and tk rj/C01;rjis the time of flight from the node j/C01 to node jin the route. Helicopter teams depart the airport at maximum fuel capacity, that isFk 0¼fk. We assume that helicopter teams refuel and depart with the maximum fuel level fk when at an HLZ with refuel capabilities. Additionally, when helicopter teams wait at an HLZ for more than the required ground time, they shut down and do not burn additional fuel while waiting. 4.2.3.3 Insertion function heuristic. The insertion algorithm, as depicted in Algorithm 1 ,i s a means to determine the optimal helicopter team routing given an AMR assignment. This is due to the fact that at every insertion step, the algorithm generates every possiblecombination of pickup and drop off insertions of the new AMR into the set of feasible routes from the last insertion. The only possible feasible routing solutions derive from the set of feasible solutions to the last insertion. Therefore the algorithm is effectively evaluating every possible feasible routing solution to determine the optimal. This algorithm does not scale well as the number of AMRs increases. Thus, it is imperative to limit the number of feasible routes considered at each insertion. Inspired by H€ame (2011) , we modify the insertion algorithm such that after each AMR insertion, we limit the number of feasible routes to consider with the parameter τ≥1. That is, if after inserting AMR i, we have jSk ij>τ, the insertion algorithm heuristic will only carry forward τfeasible routes to be considered in the next AMR insertion (line 2 in Algorithm 1 ). This heuristic adaptation allows for global routing optimality when τ≥ð2jNkjÞ! 2jNkj, as no feasible routes are discarded. When τis smaller, the insertion algorithm heuristic results in locally optimal solutions with reduced computational effort. We chose several objective functions to determine the τfeasible routes to carry forward to the next AMR insertion. The most obvious objective to consider is minimizing the total time offlight. However, choosing the feasible routes with the shortest time of flight might remove routing sequences that would more easily allow the insertion of the remaining assigned AMRs. Under certain inputs, choosing an objective that enhances flexibility to insert additional AMRs will have a better opportunity to generate feasible routes for all AMRs assigned to the helicopter team. The other two objectives we consider are maximizing total slack time and maximizing the minimum slack time. Given the routing sequence, r5(r 1,..., rm), we wish to optimize the time of flight, ftofðrÞ¼Xm j¼1tk rj/C01;rj; (32) the total slack time, ftstðrÞ¼Xm j¼1n lj/C0Ak jðrÞo ; (33) and the minimum slack time, fmstðrÞ¼ min j∈f1;...;mgn lj/C0Ak jðrÞo ; (34) where ljis the latest arrival time for node jandAk jðrÞis the calculated time of arrival at node j.JDAL 7,1 14 4.3 Improvement 4.3.1 Feasible solution count and evaluation. The aircraft team routing procedure determines the best aircraft team routes for each initial assignment. Let ybe the number of initial solutions to improve. The yinitial solutions with the lowest objective values are then passed to the improvement procedure. If there are not yfeasible initial solutions, the feasible solutions are stored and another fixed number of initial assignments are generated. 4.3.2 Stopping criteria and assignment generation. During the first improvement cycle, if the solution with the lowest objective value supports all AMRs and the high-cost aircraft teams are not utilized the stopping criteria are met. The heuristic then outputs the solution with the lowest objective value. If the stopping criteria are not met, the heuristic attempts to improve yassignments by redistributing unsupported AMRs to aircraft teams. Those improved assignments are then sent through the aircraft team routing procedure. 4.3.3 Aircraft team routing. The team routing procedure in the improvement procedure differs in that it searches for previous routing solutions with the same AMR set on the same aircraft team. If the team routing procedure finds a previous routing solution, the previous routing solution is set as the new solution. This prevents computationally expensive redundant routing. The best routes for each assignment are then passed to find the minimum objective value of yfeasible solutions. 4.3.4 Subsequent improvement cycles. During subsequent improvement cycle(s), we add additional stopping criteria. If the solution with the lowest objective value is the same as the solution seen in the previous ysolutions, the stopping criteria are met. The improvement procedure continues until meeting the stopping criteria and outputting the best solution, consisting of AMR assignment and aircraft team routing that meets all of the constraints outlined in Section 3.2.2 . 5. Practical application 5.1 Purpose The purpose of the practical application is to compare the performance of the heuristic under a given setting with the mathematical model proposed in Section 3.2.1 . The mathematical model will produce an optimal solution, but not in real-time, whereas, the heuristic generates a feasible solution in near real-time. The experiment provides evidence to measure the gap in the heuristic ’s solutions to the mathematical model ’s optimal solution. 5.2 Scenario The practical application scenario is based on an Army aviation task force based out of Mazar-I-Sharif (MIS), Regional Command Nort h, Afghanistan during Operation Enduring Freedom. The helicopter landing zone network consists of ten HLZs, five of which have helicopter refueling capabilities. The network, as seen in Figure 3 , is relatively spaced out for helicopter operations. The large st distance between any two HLZs is over 530 kilometers, which would require any helicopter in the fleet to stop for refuel. MIS and Kunduz are considered hubs, serving as the pickup and drop off locations for many of the AMRs. The helicopter task force consists of three UH-60 Blackhawk teams stationed in MIS. The helicopter team parameters are displayed in Table 2 . Each team has a maximum capacity Qk of 22 passengers, an average speed skof 222 kilometers per hour and a maximum fuel capacity fkof two hours. The scenario assumes sunrise prior to 0700 and sunset between 1900 and 2100. This assumption affects the maximum duration Tkof the teams by reducing from 8 to 6 if a team has a flight window that includes time before sunrise or after sunset. It isAir movement assignment and routing 15 standard for Army helicopter crews to fly with night vision goggles under periods of darkness while conducting combat operations. The use of night vision goggles increases pilot fatigue. It is common for commanders ’crew endurance management policies to reduce the maximum duration for crews who use night vision goggles for any period of their flight (Department of the Army, 2018 ). All helicopter teams have a flight hour penalty γ51. The utilization penalty βof the first two helicopter teams is set to one. Setting the utilization penalty to one can be interpreted as the aviation task force leadership expecting to use the helicopter team under normal operations. The last helicopter team is marked as a quick reaction force (QRF) team, which is held in reserve to react to unforeseen missions. The utilization penalty for the QRF team is set to 400. Recall that the first term in the objective function penalizes each unmet demand by a penalty αmultiplied by the transformed priority of the air mission request bifor each AMR i. For this scenario, the AMR priority is transformed through an exponential function with base B52 so that an AMR of one higher level priority is two times as important as the AMR one priority level below. For the priority levels as described in Table 1 the transformed priority is calculated using Eq. (24) . In this scenario, we set the unmet demand penalty α5100, which can be interpreted as not supporting an AMR of priority level 9 equivalent to 100 flight hours, αbi¼αBð9/C0piÞ¼ð100Þ2ð9/C09Þ¼100. This will encourage the model to prioritize supporting all AMRs possible even at the expense of additional flight hours. The higher utilization penalty for the QRF team can be interpreted as the threshold to launch in order to support an AMR of a certain priority or multiple AMRs of a lower priority. In this scenario, the QRF team utilization penalty is set to serve as a threshold to support a priority level 7 (O-6 Colonel or Equivalent) AMR, two priority level 8 AMRs, four priority level 9 AMRs, or a combination of multiple priority AMRs. β54005(100)2(9–7)5(100) (2)2(9–8)5 (100) (4)2(9–9). It is important to note that the solutions are dependent on penalty weights ( α,βk, and γk) and the AMR transformed priority ( bi).Nelson (2023) explores how varying penalty weights can lead to multiple solutions for decision makers to evaluate. Team HRkHDkTkQkskfkβγ UH_A 7 15 8 22 222 2 1 1 UH_B 15 21 6 22 222 2 1 1UH_QRF 11 19 8 22 222 2 400 1 Source(s): Table by authors Table 2. Practical application helicopter fleetFigure 3.Regional command north, AfghanistanJDAL 7,1 16 Each AMR ihas a 25% probability of pickup at MIS, and a 25% probability of pickup at Kunduz, with the remaining AMR pickup location probability equally distributed among the other eight HLZs. If the AMR pickup is at MIS or Kunduz, the drop off location is equally probable among the other nine HLZs. If the AMR pickup location is not at one of the hubs, it has 25% probability of drop off at MIS, 25% probability of drop at Kunduz, with the remaining AMR drop off location probability equally distributed among the other seven HLZs. 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 Lis set at 4 h. 5.3 Experimental design The heuristic is set with the following parameters. The number of initial AMR assignments is 5,000, with the number of initial feasible solutions to improve set at y550. The aircraft team routing heuristic limits the number of feasible routes to consider after each insertion to τ510. The objective function to determine the τfeasible routes is the time of flight ( Eq. 32 ). The experiments increase in AMR quantity nfrom three to nine and then from ten to thirty in steps of ten. Each nvalue has 10 instances I, each drawing from the AMR parameter distributions explained in Section 5.2 . The metrics recorded for the mathematical model and the heuristic are overall objective value, number and priority of unsupported AMR(s), aircraft teams utilized and route time. Problem instance data available from Daniels et al. (2023) . 5.4 Results Table 3 shows the average results for the ten instances at each AMR quantity reached by Gurobi 9.5.2 running the MILP model and for the air movement operations planning heuristic. The heuristic was run on a Dell OptiPlex 7060 Intel 6 Core i7-8700 CPU @ 3.2 GHz with 16 GB memory running Windows 10. The column ndenotes the AMR quantity, column Time denotes the average execution time in seconds. Columns UB and LB denote the average upper bound and lower bound, respectively. The UBs and LBs were found after Gurobi reached the optimal solution or the 6 h (21600 s) time limit. The column Gap states the average percent Gap51003(UB/C0LB)/UB. Columns Un and Un Pen describe the average number of unsupported AMRs and unsupported AMR penalties per instance, respectively. Column QRF states the number of instances in which a high-cost QRF helicopter team is used in the solution out of ten total instances. Finally, column Route is the average time of flight per instance in hours. The full results for each instance and AMR quantity are displayed in Table A2 . For AMR quantities n56, 7, 8, 9 and 10 we used an alternative MILP solution method for the majority of the instances. The alternative method involved identifying which AMRs were individually feasible for each low-cost helicopter team and then creating all possible assignments based on the individual feasibility. We then solved a single helicopter team MILP for each assignment and chose the solution with the lowest objective value as the optimal. We are able to claim this solution as optimal because we evaluated every feasible assignment on the low-cost helicopter teams. Any feasible solution using only the low-cost helicopter teams is better than a solution using the high-cost QRF team or leaving an AMR unsupported due to the scenario ’s weighted penalties. Therefore, the low-cost helicopter team assignment and routing solution with the lowest objective value is optimal. Due to the alternative MILP solution method ’s significant pre-processing and numerous single- helicopter team MILP solution runs, it is not possible to quantify run times for eachAir movement assignment and routing 17 nMILP (solved with Gurobi) Heuristic Time UB LB Gap Un Un pen QRF Route Time Obj Un Un pen QRF Route 3 23 5.19 5.19 0 0.0 0 0/10 3.79 3 5.35 0.0 0 0/10 3.95 4 1,455 5.94 5.94 0 0.0 0 0/10 4.24 7 5.99 0.0 0 0/10 4.29 5 9,278 6.68 6.68 0 0.0 0 0/10 4.88 9 6.68 0.0 0 0/10 5.03 6 * 7.51 7.51 0 0.0 0 0/10 5.71 14 47.64 0.1 40 0/10 5.847 * 8.77 8.77 0 0.0 0 0/10 6.77 18 8.99 0.0 0 0/10 6.998 * 18.74 18.74 0 0.1 10 0/10 6.84 41 79.28 0.2 30 1/10 7.489 * 49.37 8.91 82 0.0 0 1/10 7.05 56 69.08 0.5 60 0/10 7.0810 * 49.66 9.15 82 0 0 1/10 7.66 84 60.31 0.1 10 1/10 8.4120 21,600 – 1.98 –– – – – 789 2976.45 0.1 2,560 10/10 14.45 30 21,600 – 0.90 –– – – – 2,554 609.40 1.1 190 10/10 17.40 Note(s): * Alternative MILP solution method used /C0Gurobi was not able to find values SeeTable A2 for instance-level details Source(s): Table by authors Table 3. Average MILP and heuristic performanceJDAL 7,1 18 instance. For AMR quantities n520, 30, we used a 72-core Intel Xeon processor (running a maximum of 32 threads) with 128 GB memory to solve each instance with a maximum execution time of 21600 s. For all instances in AMR quantities n53, 4, 5, both the MILP model and heuristic solved the problem by supporting all AMRs using only low-cost helicopter teams. The heuristic provided quality solutions in a fraction of the time required by the MILP using Gurobi. We used an alternative MILP solution method to arrive at optimal solutions for most instances in AMR quantities n56, 7, ..., 10. Using this alternative method the exact time to solve each instance is not known, but it is safe to assume the time exceeded that of practical use to an aviation mission planner. Alternatively, the heuristic solved each of the associated instances in two minutes or less. Gurobi failed to determine an optimal solution for Instance 2 of n59 and Instance 7 of n510. For these two instances, we use the feasible UB solutions for comparison. The unit- less objective values serve only as an entry point in the comparative analysis. In this practical application, the failure to support AMRs and the use of the high-cost QRF helicopter team are heavily penalized compared to route costs. For the n56, 7, ..., 10 instances, the heuristic solutions ’route times did not differ greatly from the MILP solutions ’route times nor did they contribute heavily to the overall objective values. Instead, we will focus analysis on AMR support and QRF utilization. For the ten n56 instances the average number of unsupported AMRs per instance is 0.1. Considering there are ten instances, it follows that the heuristic failed to support only one AMR out of the sixty total AMRs in the ten instances while the MILP supported all sixty total AMRs. For all n57 instances, the heuristic arrived at the same optimal AMR support and QRF utilization as the MILP. For the n58 instances, the heuristic failed to support 2 out of the 80 total AMRs, only one more than the MILP solutions. Additionally, one n58 instance heuristic solution required a QRF team. Considering all of the n59 instance solutions, the heuristic failed to support 5 more AMRs than the MILP, but used one less QRF team. Finally, the heuristic and MILP differed in only one n510 instance in terms AMR support, with the heuristic supporting one less AMR. When considering all fifty n56, 7, ..., 10 instances, the heuristic supported only eight fewer AMRs and utilized the same number of QRF teams as the MILP. Furthermore, the heuristic generated a worse solution in terms of AMR support or QRF utilization in only five of the fifty n56, 7, ..., 10 instances. The MILP model failed to generate a feasible solution for the n520, 30 instances after 6 h of run time. In contrast, the heuristic solved the n520, 30 instances in less than 14 and 43 min on average, respectively. Furthermore, the heuristic was able to find solutions that supported 199/200 and 289/300 of the AMRs associated with the n520 and n530 instances, respectively. Additionally, we attempted to generate feasible solutions through Gurobi ’s internal general-purpose MILP heuristic on a limited set of instances ( n520 instances 1,3,5). We set Gurobi parameters to prioritize finding feasible solutions (MIPFocus 51a n d Heuristics 50.95) and allowed a 96 h run time ( Gurobi, 2023 ). Even with the selected parameter settings and extended run time, Gurobi failed to find feasible solutions for the three instances. Any solution found after 96 h would have no value to an air mission planner due to the air mission request timeline. For the same instances, the air movement operations planning heuristic generated feasible solutions for all AMRs in an average of fewer than 16 min per instance. Further evidence to show that the air movement operations planning heuristic provides a quality feasible solution in a tolerable time frame is displayed in Table 4 . As previously stated, Gurobi failed to find feasible solutions for larger problems ( n≥20). We solved the n510 instances with a 60-min maximum run time to compare the speed and quality of solutions provided by Gurobi and the heuristic for smaller problems. We noted the value ofAir movement assignment and routing 19 Gurobi ’s first feasible solution and the computation time required to find a feasible solution (in seconds) as well as Gurobi ’s solution value at the 60-min run time expiration. On average, the heuristic arrived at a solution in 32.8% of the time Gurobi used to find a feasible solution. Furthermore, the heuristic solution was on average 66.4% better than the 60-min run time solution. The end goal of this research is to provide Army aviation air movement mission planners a tool to assist in assigning AMRs and routing helicopter teams. The tool is only useful to planners if it provides quality solutions in a timely manner. Table 3 provides evidence of the quality of the air movement operations planning heuristic solution. Additionally, the table describes the average heuristic computation time for each AMR quantity n. Even at n530, the heuristic provided a solution in less than 43 min on average. This computation time is acceptable for planning missions with execution start times of 12 –24 h in the future. More importantly, we have shown the air movement operations planning heuristic can provide quality solutions in much less time than aviation mission planners ’current methods. 6. Application-sized problem 6.1 Overview Section 5 demonstrates the heuristic ’s ability to generate quality solutions within a practical time period. This section seeks to test the scale of the problem the heuristic is able to generate feasible solutions in a timely manner. 6.2 Scenario The scenario described in Section 5 was restricted by the solvable scale of the MILP model. The heuristic is able to find feasible solutions for problems of a much greater scale. This application-sized scenario is the same as that described in Section 5 , with the following exceptions. The HLZ network has been reduced to 1/3 the scale. The aviation task force based out of MIS consists of ten UH-60 teams as described in Table 5 . Although the AMR feature distributions are identical, the total number of AMRs nare greatly increased to 90 and 100 in order to replicate large-scale air movement operations planning. 6.3 Results Table 6 provides the results and performance of the heuristic on application-sized problems. The heuristic was able to find feasible solutions, supporting all AMRs for all instances in bothInstanceMILP (solved with Gurobi) Heuristic First feasible time (s)First feasible value60-Minute valueHeuristic time (s)Heuristic value 1 201 11 8.75 73 109.20 2 257 84,400 409.52 99 10.91 3 206 23,500 412.70 81 12.844 235 33,300 10.40 84 11.725 205 61,500 412.82 62 11.686 552 408 6.76 108 6.767 172 12,400 408.75 93 409.97 8 151 46,303 107.10 66 9.24 9 204 60,503 7.72 76 10.2410 373 24,301 10.11 98 10.53 Source(s): Table by authorsTable 4. 60-Minute run time experiment ( n510)JDAL 7,1 20 90 AMR and 100 AMR quantity-sized problems. The heuristic solved the n590 and 100 sized problems in an average of 2.6 and 4.8 h, respectively. The ability of the heuristic to solve large-scale Army aviation air movement operations problems in a reasonably timely manner shows great promise for future real-world use. 7. Conclusion and future work The work presented in this paper contributes to the field of military operations research by developing a model that solves the US Army Aviation air movement operations planning problem while incorporating the following real-world considerations: (1) multiple refuel nodes, (2) minimization of unsupported demand by priority level, (3) demand time windows,Team HRkHDkTkQkskfkβγ UH_AM_A 7 15 8 22 222.2 2 1 1 UH_AM_B 7 15 8 22 222.2 2 1 1UH_AM_C 7 15 8 22 222.2 2 1 1 UH_AM_D 7 15 8 22 222.2 2 1 1 UH_AM_E 7 15 8 22 222.2 2 1 1UH_PM_A 15 21 6 22 222.2 2 1 1UH_PM_B 15 21 6 22 222.2 2 1 1UH_PM_C 15 21 6 22 222.2 2 1 1UH_PM_D 15 21 6 22 222.2 2 1 1 UH_PM_E 15 21 6 22 222.2 2 1 1 Source(s): Table by authors n Instance Time (s) Objective Unsupported Utilization Route time 90 1 13,326 30.80 0 10 20.80 90 2 10,364 29.87 0 10 19.87 90 3 5,086 31.15 0 10 21.1590 4 12,134 29.10 0 10 19.1090 5 100,085 30.51 0 10 20.5190 6 3,654 31.73 0 10 21.7390 7 11,996 30.48 0 10 20.4890 8 7,375 29.77 0 10 19.77 90 9 11,304 29.36 0 10 19.36 90 10 8,280 28.88 0 10 18.88100 1 14,755 31.59 0 10 21.59100 2 19,265 30.81 0 10 20.81100 3 15,124 30.57 0 10 20.57100 4 19,538 29.11 0 10 19.11 100 5 19,929 33.83 0 10 23.83 100 6 20,680 30.23 0 10 20.23100 7 20,360 32.17 0 10 22.17100 8 8,531 32.52 0 10 22.52100 9 15,634 31.28 0 10 21.28100 10 17,654 29.49 0 10 19.49 Source(s): Table by authorsTable 5. Application-sized problem helicopter fleet Table 6. Application-sized problem heuristic resultsAir movement assignment and routing 21 (4) aircraft team utilization penalties, (5) aircraft team time windows and maximum duration and (6) passenger ride time limits. Additionally, the paper introduces an air movement operations planning heuristic that generates feasible solutions in near real time. This heuristic is a vast improvement to the manual air movement operations planning used currently by US Army Aviation. Implementation of this heuristic has the potential to reduce air movement operations planning time, reduce resource burden on army aviation and ultimately improve lift capacity to the supported commanders at echelon. Future work includes further analysis and im provement of the air movement operations planning model and heuristic. The model ’s solutions are dependent on hyperparameters and penalty weights. Further analysis is needed to determine how the model ’s sensitivity to these values affects solutions and informs decision makers. Improvements include incorporating a means to insert refueling stops mid-route, improved initial assignment methodology and parameter tuning. To add additional sophistication, the heuristic could introduce flight characteristics associated wi th altitude and air temper ature. Additionally, further work is needed to output solutions as u seful products for the Army aviation mission planner and operator. Finally, this heuristic has the potential to be integrated into additional decision su pport models, includin g determining the best allocation of aviation resources to task forces.