US Army Aviation air movement operations assignment, utilization and routing

Abstract

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 minimize unsupported 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 to 100 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 the numerical experimentation. Additionally, the authors make several simplifying assumptions to generalize the average performance and capabilities of aircraft throughout a flight.

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 team time windows and maximum duration and passenger ride time limits.

Citation

Nelson, R., King, R., McConnell, B.M. and Thoney-Barletta, K. (2023), "US Army Aviation air movement operations assignment, utilization and routing", Journal of Defense Analytics and Logistics, Vol. 7 No. 1, pp. 2-28. https://doi.org/10.1108/JDAL-11-2022-0013

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 ground 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 supplies between helicopter landing zones (HLZs) on forward operating bases (FOBs) in order to 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 and supplies over mountainous and seasonally impassible terrain. In large-scale combat operations, 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 over 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 helicopter 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 important 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 AMRs to optimize the best use of helicopter assets. The BAE then routes AMRs to the next higher command, 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 aircraft 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.

Following the normal AMR processing timeline, the aviation brigade should know the AMR demands 96 h prior to execution. However, due to the nature of competing requirements and realities of dynamic conflicts, 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 demands (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 planners 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 current general support aviation battalion commander, it is not uncommon for a team of battalion 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 unsupported AMRs, additional personnel, maintenance and sustainment resource requirements, 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.

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 Ho et al. (2018a) and Nasri et al. (2021). DARP consists of creating m vehicle routes for n customers with pickup and delivery requests between origins and destinations, where n > m. The objective is to plan a set of m minimum 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) and Menezes 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 routing is the impact of having a limited set of refueling nodes. In the general DARP model, refueling 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 assets 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ün et 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, demand 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 by Cordeau and Laporte (2003) and improved by Ho et al. (2018b) to large neighborhood search algorithms described in Masmoudi et al. (2020) and Jain 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äme (2011).

3. Mathematical model

3.1 Assumptions

In order to develop a model to optimize helicopter routing, we make the following assumptions:

• Each helicopter team starts and terminates at an airport (node).

• An 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.

• Helicopter capacity is solely limited by passenger seats. Cargo weight and volume can be converted to passenger equivalency.

• Each 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.

• Each passenger has the same maximum amount of time they can be on a helicopter (ride time).

• Service time (ground delay) is a function of the HLZ and includes the time to refuel at refueling nodes.

• Helicopter teams can shut down the aircraft engines at any HLZ to conserve fuel while waiting for an AMR window to open.

• Reserve fuel is omitted from the maximum fuel capacity, f^k. 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 f^k does not include reserve fuel, therefore it replicates the fuel capacity considered by mission planners.

• Helicopter capacity, flight speed and fuel burn rate are constant throughout the helicopter team's flight period.

• An AMR can be left unsupported at a penalty in proportion with the unsupported AMR's priority level.

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) and Tekil-Ergün et al. (2021). The capacitated helicopter routing problem (CHRP) can be represented by a complete graph G(V; A) defined by a set of nodes, V = {P, D, E}, and edges, A. P is the set of AMR pickup nodes, P = {1, 2, …, n}. D is the set of AMR dropoff nodes, D = {n + 1, n + 2, …, 2n}. E is the set of refueling nodes, including the starting node a = 2n + 1 and the ending node z = 2n + 2, which are both located at the airport. E = {2n + 1, 2n + 2, …, 2n + |E|}. A passenger load, q_i, is associated with each node i ∈ V with q_a = q_z = 0, q_i ≥ 0 for i = 1, …, n and q_i = −q_i−n for i = n + 1, …, 2n, and a service time d_ij ≥ 0 with d_iz = 0.

Each helicopter team has the following parameters:

• Q^k: maximum passenger seat capacity of helicopter team k ∈ K;

• T^k: maximum mission duration (in hours) of helicopter team k ∈ K. T^k is 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;

• s^k: average flight speed of helicopter team k ∈ K;

• HD^k: earliest time of departure from the airport of helicopter team k ∈ K;

• HR^k: latest time to return to the airport of helicopter team k ∈ K;

• f^k: maximum fuel capacity (in hours) of helicopter team k ∈ K.

Each node i ∈ V has the following parameters:

• q_i: number of passengers boarding or deplaning at node i ∈ P ∪ D, (∀i ∈ P, q_i = −q_n + i);

• d_ij: service time at node j when departing node i, (i, j ∈ P ∪ D);

• [e_i, l_i]: time window of node i ∈ P ∪ D;

• b_i: 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:

• c_ij: distance between nodes i and j for i, j ∈ V;

• tijk=cijsk: time between nodes i and j for helicopter team k ∈ K, i, j ∈ V.

The decision variables for the proposed model are as follows:

• Xijk is the binary variable equal to 1 if helicopter team k ∈ K flies from node i ∈ V to node j ∈ V. Otherwise, it is equal to 0;

• Uik indicates the time the helicopter team k ∈ K completes service at node i ∈ V;

• Wik indicates the number of occupied seats after helicopter team k visits node i ∈ V;

• Rik indicates the ride time of passenger i ∈ P on helicopter team k ∈ K;

• Fik indicates the amount of fuel (in hours) of helicopter team k ∈ K when departing node i ∈ V.

It is important to note that each AMR has a unique pickup node i ∈ P and 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, d_ij, 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.

• Every route starts and ends at the airport;

• For every AMR i, nodes i and i + n belong to the same route and node i + n is visited later than node i;

• The load of helicopter team k does not exceed the maximum seat capacity Q^k at any time;

• The total duration of route k does not exceed the maximum route duration T^k;

• The service at node i begins in the interval [e_i, l_i];

• Every helicopter team k leaves the airport and returns to the airport in the interval [HD^k, HR^k];

• The ride time of any passenger does not exceed L; and

• The fuel level of helicopter team k, does not drop below 0 at any time.

3.2.3 Mathematical model

Objective:

(1)minα∑i∈P∑j∈VbiXij1+∑k∈Kβk∑j∈VXajk+∑k∈Kγk∑i∈V∑j∈VtijkXijk

Subject to:

(2)∑k∈K∑j∈V\{a,z}Xijk=1(∀i∈P)

(3)∑j∈VXjik-∑j∈VXijk=0(∀i∈V\{a,z},k∈K)

(4)∑j∈VXijk-∑j∈VXn+i,jk=0(∀i∈P,k∈K)

(5)∑i∈VXaik=∑i∈VXizk(∀k∈K)

(6)∑i∈VXiak=0(∀k∈K)

(7)∑j∈VXzjk=0(∀k∈K)

(8)∑j∈VXijk≤1(∀i∈E,k∈K)

(9)Xijk∈{0,1}(∀(i,j)∈A,k∈K)

(10)Ujk≥(Uik+dij+tijk)Xijk(∀(i,j)∈V,i≠j,k∈K)

(11)Un+ik-Uik≥0(∀i∈P,k∈K)

(12)Uzk-Uak≤Tk(∀k∈K)

(13)Uak≥HDk∑i∈VXaik(k∈K)

(14)Uzk≤HRk∑i∈VXizk+MU1-∑i∈VXizk(k∈K)

(15)ei≤Uik≤li(∀i∈V,k∈K)

(16)Un+ik-Uik≤Rik≤L(∀i∈P,k∈K)

(17)Wjk≥(Wik+qj)Xijk(∀(i,j)∈V,k∈K)

(18)0≤Wik≤Qk(∀i∈V,k∈K)

(19)Wak=Wzk=0(∀k∈K)

(20)Fjk-Fik+dij+tijk≤MFk(1-Xijk)(∀i∈V,j∈P∪D,k∈K)

(21)Fjk-Fik+dij+tijk≥-MFk(1-Xijk)(∀i∈V,j∈P∪D,k∈K)

(22)Fik=fk(∀i∈E,k∈K)

(23)Fik-tijk≥-MFk(1-Xijk)(∀i∈V,j∈E,k∈K)

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 b_i for i ∈ P.

The model transforms the AMR priority through an exponential function with base B so that an AMR of one higher level priority is B times as important as the AMR one priority level below. For the priority levels listed in Table 1, the transformed priority is

(24)bi=B(9-pi),

where p_i is the priority level of AMR i. The first helicopter team k ∈ K is 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 (Xij1) by the AMR specific transformed priority (b_i) 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 β^k of using helicopter team k ∈ K. The model uses the utilization penalty for each aircraft team,

(25)βk=αbi=αB(9-pi),

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 ∈ K by γ^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 ∈ K that visits the pickup node i ∈ P must 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 (d_ij = 0.001) with no travel time (tijk=0). Constraints (11) define the precedence constraints where the helicopter team k must first visit a demand pickup node i ∈ P before the associated demand drop off node j = i + n, j ∈ D. Constraints (12) ensure the time helicopter team k ∈ K is 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=maxk∈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 Rik is 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 k when departing node j. Constraints (18) define the domain of the number of occupied seats to ensure the helicopter team k ∈ K does 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 k when departing a pickup or drop off node j. Let MFk=fk+maxi,j∈V(tijk). This ensures that the remaining fuel in helicopter team k after departing node j is Fjk=Fik-dij-tijk. Constraints (22) ensure helicopter team k departs 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 k departs the refuel node with maximum fuel. Constraints (23) require a helicopter team k to 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+tijk and L_W = max{Q^k, Q^k + q_i}.

(26)Ujk≥Uik+dij+tijk-LU(1-Xijk)(i,j∈V,k∈K)

(27)Wjk≥Wik+qj-LW(1-Xijk)(i,j∈V,k∈K)

Constraints (26) and (27) replace (10) and (17), respectively.

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 n AMRs and |K| aircraft teams, there are |K|ⁿ ways 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, q_i ≤ Q^k. 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-taik. 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+ti,i+nk+di,i+n+ti+n,zk≤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, taik+dai+ti,i+nk+di,i+n+ti+n,zk≤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 number 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 search of the assignment space. The initial AMR assignments 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 teams or left unsupported. The goal of the aircraft team routing step is to find the lowest cost feasible 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 heuristic is introduced in order to allow problem scaling.

4.2.3.1 AMR insertion algorithm

For each assignment, let N^k be the set of AMRs assigned to aircraft team k ∈ K, with Nk={n1k,…,n|Nk|k}. To solve the helicopter team routing given an AMR assignment for each helicopter team, we adapt the advanced insertion algorithm that Häme (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 to 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. Let Ajk(r) be the time aircraft team k arrives at node j in sequence r = (r₁, r₂, …, r_m). In order for a sequence to be feasible, Ajk(r)≤lrj∀j in the sequence, where lrj is the latest arrival time at node r_j. We calculate Ajk(r) recursively with

(28)Ajk(r)=max{Aj-1k(r),erj-1}+trj-1,rjk,for j=1,

(29)Ajk(r)=max{Aj-1k(r)+drj-2,rj-1,erj-1}+trj-1,rjk,for j≥2,

where A0k(r)=HDk, which is the earliest departure time from the airport for helicopter team k. This is different from the MILP formulation, where Uak can take values other than HD^k. The heuristic makes a simplifying assumption that each aircraft team will start the route at the earliest departure time. We denote d_i,j as the ground time at node j when 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-1>Aj-1k(r)+drj-2,rj-1, the helicopter will wait at node j − 1 until erj-1.

Maximum passenger ride time. Let Rnik be the ride time for the passengers on AMR i assigned to helicopter team k. In order for a sequence to be feasible Rnik≤L,∀i∈Nk. We define passenger ride time as the time between departure after passenger pickup and passenger drop off at the destination. We calculate Rnik by subtracting the maximum of the earliest pickup time for AMR i and the arrival time for AMR i pickup plus the service time from the drop off time of AMR i.

Aircraft flight duration. In order for the sequence r to 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, A2|Nk|+1k(r)-A0k(r)≤Tk.

Aircraft capacity. We define Wjk to be the total number of passengers on board the aircraft team k when departing the jth node of the route. In order for the route to be feasible, Wjk≤QK∀j in the route, where Q^k is the maximum capacity for helicopter team k. We calculate Wjk recursively with

(30)Wjk=Wj-1k+qrj,

where W0k=0 and qrj is the number of passengers loading or unloading at node r_j.

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, HR^k.

Aircraft fuel level. We define F_j to 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, F_j ≥ 0 ∀j in the route. We calculate F_j recursively with

(31)Fj=Fj-1-drj-2,rj-1-trj-1,rjk,

where drj-2,rj-1 is the ground time at the last HLZ and trj-1,rjk is the time of flight from the node j − 1 to node j in the route. Helicopter teams depart the airport at maximum fuel capacity, that is F0k=fk. We assume that helicopter teams refuel and depart with the maximum fuel level f^k 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, is 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 possible combination 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äme (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 |Sik|>τ, 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 τ≥(2|Nk|)!2|Nk|, 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 of flight. 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, r = (r₁, …, r_m), we wish to optimize the time of flight,

(32)ftof(r)=∑j=1mtrj-1,rjk,

the total slack time,

(33)ftst(r)=∑j=1m{lj-Ajk(r)},

and the minimum slack time,

(34)fmst(r)=minj∈{1,…,m}{lj-Ajk(r)},

where l_j is the latest arrival time for node j and Ajk(r) is the calculated time of arrival at node j.

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 y be the number of initial solutions to improve. The y initial solutions with the lowest objective values are then passed to the improvement procedure. If there are not y feasible 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 y assignments 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 y feasible 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 y solutions, 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 North, 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 largest 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 Q^k of 22 passengers, an average speed s^k of 222 kilometers per hour and a maximum fuel capacity f^k of two hours. The scenario assumes sunrise prior to 0700 and sunset between 1900 and 2100. This assumption affects the maximum duration T^k of the teams by reducing from 8 to 6 if a team has a flight window that includes time before sunrise or after sunset. It is 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 γ = 1. 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 b_i for each AMR i.

For this scenario, the AMR priority is transformed through an exponential function with base B = 2 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 α = 100, which can be interpreted as not supporting an AMR of priority level 9 equivalent to 100 flight hours, αbi=αB(9-pi)=(100)2(9-9)=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. β = 400 = (100)2^(9–7) = (100) (2)2^(9–8) = (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 (b_i). Nelson (2023) explores how varying penalty weights can lead to multiple solutions for decision makers to evaluate.

Each AMR i has 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 L is 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 y = 50. The aircraft team routing heuristic limits the number of feasible routes to consider after each insertion to τ = 10. The objective function to determine the τ feasible routes is the time of flight (Eq. 32).

The experiments increase in AMR quantity n from three to nine and then from ten to thirty in steps of ten. Each n value 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 n denotes 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 Gap = 100 × (UB − LB)/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 n = 6, 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 each instance. For AMR quantities n = 20, 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 n = 3, 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 n = 6, 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 n = 9 and Instance 7 of n = 10. 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 n = 6, 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 n = 6 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 n = 7 instances, the heuristic arrived at the same optimal AMR support and QRF utilization as the MILP. For the n = 8 instances, the heuristic failed to support 2 out of the 80 total AMRs, only one more than the MILP solutions. Additionally, one n = 8 instance heuristic solution required a QRF team. Considering all of the n = 9 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 n = 10 instance in terms AMR support, with the heuristic supporting one less AMR. When considering all fifty n = 6, 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 n = 6, 7, …, 10 instances.

The MILP model failed to generate a feasible solution for the n = 20, 30 instances after 6 h of run time. In contrast, the heuristic solved the n = 20, 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 n = 20 and n = 30 instances, respectively.

Additionally, we attempted to generate feasible solutions through Gurobi's internal general-purpose MILP heuristic on a limited set of instances (n = 20 instances 1,3,5). We set Gurobi parameters to prioritize finding feasible solutions (MIPFocus = 1 and Heuristics = 0.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 n = 10 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 of 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 n = 30, 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 n are 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 both 90 AMR and 100 AMR quantity-sized problems. The heuristic solved the n = 90 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, (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 improvement 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 with altitude and air temperature. Additionally, further work is needed to output solutions as useful products for the Army aviation mission planner and operator. Finally, this heuristic has the potential to be integrated into additional decision support models, including determining the best allocation of aviation resources to task forces.

Figures

Figure 1

Air mission request process

Figure 2

Heuristic concept

Figure 3

Regional command north, Afghanistan

Table 1

Air mission request priority

AMR mission	Priority
Downed Aircraft Recovery	1 (highest)
Emergency Leave	2
General Officer Movement	3
Military Working Dog	4
Critical Equipment Repair	5
Religious Services	6
O-6 Colonel or Equivalent	7
Rest and Recovery Leave	8
Other	9 (lowest)

Source(s): Table from Mogensen (2014)

Table 2

Practical application helicopter fleet

Team	HRk	HDk	Tk	Qk	sk	fk	β	γ
UH_A	7	15	8	22	222	2	1	1
UH_B	15	21	6	22	222	2	1	1
UH_QRF	11	19	8	22	222	2	400	1

Source(s): Table by authors

Table 3

Average MILP and heuristic performance

n	MILP (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.84
7	*	8.77	8.77	0	0.0	0	0/10	6.77	18	8.99	0.0	0	0/10	6.99
8	*	18.74	18.74	0	0.1	10	0/10	6.84	41	79.28	0.2	30	1/10	7.48
9	*	49.37	8.91	82	0.0	0	1/10	7.05	56	69.08	0.5	60	0/10	7.08
10	*	49.66	9.15	82	0	0	1/10	7.66	84	60.31	0.1	10	1/10	8.41
20	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

− Gurobi was not able to find values

See Table A2 for instance-level details

Source(s): Table by authors

Table 4

60-Minute run time experiment (n = 10)

Instance	MILP (solved with Gurobi)			Heuristic
	First feasible time (s)	First feasible value	60-Minute value	Heuristic 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.84
4	235	33,300	10.40	84	11.72
5	205	61,500	412.82	62	11.68
6	552	408	6.76	108	6.76
7	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.24
10	373	24,301	10.11	98	10.53

Source(s): Table by authors

Table 5

Application-sized problem helicopter fleet

Team	HRk	HDk	Tk	Qk	sk	fk	β	γ
UH_AM_A	7	15	8	22	222.2	2	1	1
UH_AM_B	7	15	8	22	222.2	2	1	1
UH_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	1
UH_PM_A	15	21	6	22	222.2	2	1	1
UH_PM_B	15	21	6	22	222.2	2	1	1
UH_PM_C	15	21	6	22	222.2	2	1	1
UH_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

Table 6

Application-sized problem heuristic results

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.15
90	4	12,134	29.10	0	10	19.10
90	5	100,085	30.51	0	10	20.51
90	6	3,654	31.73	0	10	21.73
90	7	11,996	30.48	0	10	20.48
90	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.88
100	1	14,755	31.59	0	10	21.59
100	2	19,265	30.81	0	10	20.81
100	3	15,124	30.57	0	10	20.57
100	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.23
100	7	20,360	32.17	0	10	22.17
100	8	8,531	32.52	0	10	22.52
100	9	15,634	31.28	0	10	21.28
100	10	17,654	29.49	0	10	19.49

Source(s): Table by authors

Table A1

A summary of acronyms used in alphabetical order

Acronym	Abbreviation
Air Mission Request	AMR
Area of Operation	AO
Assault Helicopter Battalion	AHB
Brigade Aviation Element	BAE
Cargo Helicopter	CH
Combat Aviation Brigade	CAB
Capacitated Helicopter Routing Problem	CHRP
Course of Action	COA
Dial-A-Ride-Problem	DARP
Design of Experiments	DOE
Electric Vehicle	EV
Forward Operating Base	FOB
General Support Aviation Battalion	GSAB
Helicopter Landing Zone	HLZ
Mazar-I-Sharif	MIS
Maximum of Minimum Slack Time	MST
Mixed Integer Linear Program	MILP
Multiple Vehicle Routing Problem	MVRP
Quick Reaction Force	QRF
Restricted Operating Zone	ROZ
Rotary Wing	RW
Time of Flight	TOF
Total Slack Time	TST
Unmanned Aerial Vehicle	UAV
Utility Helicopter	UH

Source(s): Table by authors

Table A2

MILP and heuristic performance

n	I		MILP (solved with Gurobi)							Heuristic
		Time	UB	LB	GAP (%)	# Un	Un penalty	Utilization	Route	Time	Objective	# Un	Un penalty	Utilization	Route
3	1	5.7	5.09	5.09	0.0	0	0	2	3.09	2.7	5.09	0	0	2	3.09
3	2	3.5	3.04	3.04	0.0	0	0	1	2.04	2.9	3.04	0	0	1	2.04
3	3	73.3	8.15	8.15	0.0	0	0	2	6.15	2.2	9.74	0	0	2	7.74
3	4	17.3	6.79	6.79	0.0	0	0	2	4.79	2.2	6.79	0	0	2	4.79
3	5	1.8	3.61	3.61	0.0	0	0	1	2.61	2.8	3.61	0	0	1	2.61
3	6	8.8	4.96	4.96	0.0	0	0	1	3.96	2.5	4.96	0	0	1	3.96
3	7	9.8	4.23	4.23	0.0	0	0	1	3.23	2.6	4.23	0	0	1	3.23
3	8	5.8	4.86	4.86	0.0	0	0	2	2.86	2.6	4.86	0	0	2	2.86
3	9	6.7	5.13	5.13	0.0	0	0	1	4.13	2.7	5.13	0	0	1	4.13
3	10	101.9	6.02	6.02	0.0	0	0	1	5.02	3.0	6.02	0	0	1	5.02
4	1	36.9	5.28	5.28	0.0	0	0	1	4.28	4.8	5.28	0	0	1	4.28
4	2	159.4	6.11	6.11	0.0	0	0	2	4.11	7.3	6.11	0	0	2	4.11
4	3	380.2	7.22	7.22	0.0	0	0	2	5.22	4.3	7.22	0	0	2	5.22
4	4	10262.5	7.49	7.49	0.0	0	0	2	5.49	5.2	7.49	0	0	2	5.49
4	5	119.7	4.70	4.70	0.0	0	0	1	3.70	4.6	5.14	0	0	1	4.14
4	6	601.5	8.20	8.20	0.0	0	0	2	6.20	12.4	8.20	0	0	2	6.20
4	7	444.4	5.49	5.49	0.0	0	0	2	3.49	3.9	5.49	0	0	2	3.49
4	8	26.9	4.77	4.77	0.0	0	0	2	2.77	12.7	4.77	0	0	2	2.77
4	9	2328.9	5.11	5.11	0.0	0	0	1	4.11	5.6	5.11	0	0	1	4.11
4	10	189.1	5.05	5.05	0.0	0	0	2	3.05	8.1	5.05	0	0	2	3.05
5	1	2754.9	7.68	7.68	0.0	0	0	2	5.68	18.0	7.68	0	0	2	5.68
5	2	30089.9	6.97	6.97	0.0	0	0	2	4.97	7.0	6.97	0	0	2	4.97
5	3	26645.5	4.69	4.69	0.0	0	0	1	3.69	10.6	4.69	0	0	1	3.69
5	4	13904.0	7.07	7.07	0.0	0	0	2	5.07	8.2	7.07	0	0	2	5.07
5	5	1848.5	7.37	7.37	0.0	0	0	2	5.37	8.0	7.37	0	0	2	5.37
5	6	3002.4	6.59	6.59	0.0	0	0	2	4.59	5.9	6.59	0	0	2	4.59
5	7	9464.2	8.64	8.64	0.0	0	0	2	6.64	6.8	8.64	0	0	2	6.64
5	8	3252.4	7.71	7.71	0.0	0	0	2	5.71	5.4	9.00	0	0	2	7.00
5	9	1685.5	6.25	6.25	0.0	0	0	2	4.25	6.0	6.25	0	0	2	4.25
5	10	129.0	3.84	3.84	0.0	0	0	1	2.84	9.7	4.07	0	0	1	3.07
6	1	*	5.66	5.66	0.0	0	0	1	4.66	20.0	5.67	0	0	1	4.67
6	2	*	8.57	8.57	0.0	0	0	2	6.57	14.9	8.57	0	0	2	6.57
6	3	*	8.79	8.79	0.0	0	0	2	6.79	6.6	8.79	0	0	2	6.79
6	4	*	9.11	9.11	0.0	0	0	2	7.11	23.5	406.51	1	400	2	4.51
6	5	*	8.08	8.08	0.0	0	0	2	6.08	13.4	8.08	0	0	2	6.08
6	6	*	7.85	7.85	0.0	0	0	2	5.85	14.3	9.15	0	0	2	7.15
6	7	*	7.87	7.87	0.0	0	0	2	5.87	6.7	8.44	0	0	2	6.44
6	8	*	6.53	6.53	0.0	0	0	2	4.53	13.6	7.22	0	0	2	5.22
6	9	*	7.02	7.02	0.0	0	0	2	5.02	13.8	8.02	0	0	2	6.02
6	10	*	5.59	5.59	0.0	0	0	1	4.59	16.8	5.92	0	0	1	4.92
7	1	*	9.25	9.25	0.0	0	0	2	7.25	15.1	9.25	0	0	2	7.25
7	2	*	8.90	8.90	0.0	0	0	2	6.90	21.8	8.90	0	0	2	6.90
7	3	*	10.90	10.90	0.0	0	0	2	8.90	14.5	10.90	0	0	2	8.90
7	4	*	10.12	10.12	0.0	0	0	2	8.12	23.4	10.20	0	0	2	8.20
7	5	*	8.93	8.93	0.0	0	0	2	6.93	14.7	9.21	0	0	2	7.21
7	6	*	7.44	7.44	0.0	0	0	2	5.44	19.3	8.51	0	0	2	6.51
7	7	*	8.77	8.77	0.0	0	0	2	6.77	16.0	9.56	0	0	2	7.56
7	8	*	6.88	6.88	0.0	0	0	2	4.88	20.0	6.88	0	0	2	4.88
7	9	*	8.87	8.87	0.0	0	0	2	6.87	19.4	8.87	0	0	2	6.87
7	10	*	7.65	7.65	0.0	0	0	2	5.65	20.0	7.65	0	0	2	5.65
8	1	*	9.32	9.32	0.0	0	0	2	7.32	28.8	9.75	0	0	2	7.75
8	2	*	109.14	109.14	0.0	1	100	2	7.14	83.2	109.14	1	100	2	7.14
8	3	*	9.49	9.49	0.0	0	0	2	7.49	32.1	10.56	0	0	2	8.56
8	4	*	9.04	9.04	0.0	0	0	2	7.04	39.1	9.04	0	0	2	7.04
8	5	*	8.86	8.86	0.0	0	0	2	6.86	28.5	8.86	0	0	2	6.86
8	6	*	9.09	9.09	0.0	0	0	2	7.09	42.6	209.58	1	200	2	7.58
8	7	*	8.59	8.59	0.0	0	0	2	6.59	33.1	10.16	0	0	2	8.16
8	8	*	7.34	7.34	0.0	0	0	1	6.34	37.5	7.34	0	0	2	5.34
8	9	*	6.43	6.43	0.0	0	0	2	4.4	35.3	7.31	0	0	1	6.31
8	10	*	10.07	10.07	0.0	0	0	2	8.1	48.5	411.10	0	0	401	10.10
9	1	*	7.31	7.31	0.0	0	0	2	5.3	59.4	7.39	0	0	2	5.39
9	2	21,600.0	412.25	7.66	98.1	0	0	402	TBD	68.4	506.89	4	500	2	4.89
9	3	*	10.28	10.28	0.0	0	0	2	8.3	44.0	10.32	0	0	2	8.32
9	4	*	7.88	7.88	0.0	0	0	2	5.9	64.2	7.82	0	0	2	5.82
9	5	*	9.42	9.42	0.0	0	0	2	7.4	54.5	109.15	1	100	2	7.15
9	6	*	10.82	10.82	0.0	0	0	2	8.82	44.5	10.94	0	0	2	8.94
9	7	*	5.47	5.47	0.0	0	0	2	3.47	53.7	5.69	0	0	2	3.69
9	8	*	7.90	7.90	0.0	0	0	2	5.90	49.9	10.24	0	0	2	8.24
9	9	*	11.29	11.29	0.0	0	0	2	9.29	73.4	11.29	0	0	2	9.29
9	10	*	11.10	11.10	0.0	0	0	2	9.10	43.9	11.08	0	0	2	9.08
10	1	*	8.75	8.75	0.0	0	0	2	6.75	72.8	109.22	1	100	2	7.22
10	2	*	10.52	10.52	0.0	0	0	2	8.52	99.0	10.91	0	0	2	8.91
10	3	*	12.84	12.84	0.0	0	0	2	10.84	80.9	12.84	0	0	2	10.84
10	4	*	10.37	10.37	0.0	0	0	2	8.37	84.1	11.72	0	0	2	9.72
10	5	*	11.54	11.54	0.0	0	0	2	9.54	62.4	11.68	0	0	2	9.68
10	6	*	6.76	6.76	0.0	0	0	2	4.76	108.0	6.76	0	0	2	4.76
10	7	21,600.0	408.75	3.63	99.1	0	0	401	7.75	92.6	409.97	0	0	401	8.97
10	8	*	9.23	9.23	0.0	0	0	2	7.23	66.3	9.24	0	0	2	7.24
10	9	*	7.72	7.72	0.0	0	0	2	5.72	76.4	10.24	0	0	2	8.24
10	10	*	10.11	10.11	0.0	0	0	2	8.11	97.5	10.53	0	0	2	8.53
20	1	21,600.0	–	2.23	–	–	–	–	–	1032.9	419.56	0	0	402	17.56
20	2	21,600.0	–	1.82	–	–	–	–	–	646.2	26,014.37	1	25,600	402	12.37
20	3	21,600.0	–	2.43	–	–	–	–	–	868.2	417.18	0	0	402	15.18
20	4	21,600.0	–	2.01	–	–	–	–	–	771.9	416.38	0	0	402	14.38
20	5	21,600.0		1.24	–	–	–	–	–	876.2	419.68	0	0	402	17.68
20	6	21,600.0	–	2.09	–	–	–	–	–	832.1	416.69	0	0	402	14.69
20	7	21,600.0	–	1.48	–	–	–	–	–	874.6	414.25	0	0	402	12.25
20	8	21,600.0	–	1.84	–	–	–	–	–	875.5	415.29	0	0	402	13.29
20	9	21,600.0	–	2.30	–	–	–	–	–	452.8	415.86	0	0	402	13.86
20	10	21,600.0	–	2.31	–	–	–	–	–	663.5	415.26	0	0	402	13.26
30	1	21,600.0	–	0.94	–	–	–	–	–	2614.7	419.64	0	0	402	17.64
30	2	21,600.0	–	0.25	–	–	–	–	–	2963.3	520.18	1	100	402	18.18
30	3	21,600.0	–	1.18	–	–	–	–	–	2935.5	719.16	2	300	402	17.16
30	4	21,600.0	–	1.95	–	–	–	–	–	3099.1	519.52	1	100	402	17.52
30	5	21,600.0	–	0.94	–	–	–	–	–	1930.6	816.81	1	400	402	14.81
30	6	21,600.0	–	0.46	–	–	–	–	–	2125.9	821.17	2	400	402	19.17
30	7	21,600.0	–	0.00	–	–	–	–	–	3282.1	419.93	0	0	402	17.93
30	8	21,600.0	–	1.60	–	–	–	–	–	1933.9	719.08	2	300	402	17.08
30	9	21,600.0	–	0.51	–	–	–	–	–	3198.8	519.53	1	100	402	17.53
30	10	21,600.0	–	1.18	–	–	–	–	–	1452.8	618.99	1	200	402	16.99

Note(s): * Alternative MILP solution method used

− Gurobi was not able to find values

Source(s): Table by authors