By Marcus McNabb
Most discussions on the use of unmanned aerial systems (UAS) in military roles have centered on combat missions. But these types of missions account for only a fraction of Air Force missions. For example, the US Air Force flew twice as many airlift sorties as strike sorties in support of Operation Inherent Resolve over the course of 2016. The use of UAS in an airlift role executing logistics missions is under-represented in discussions yet represents a large opportunity for the Air Force to capitalize on a radical new technology. This article will examine the challenges involved in implementing UAS in logistics operations from a routing perspective. The article focuses on developing an algorithm for calculating the optimal routes; actual UAS capabilities are not addressed.
Civilians, in both the corporate and academic sectors, have investigated a wide assortment of logistics problems. Of particular interest to this case is the Vehicle Routing Problem (VRP). Such a problem seeks an optimal solution for constructing delivery routes given a depot, a fleet of vehicles, and some number of geographically dispersed customers, each having a supply demand that must be fulfilled. The inventory routing problem (IRP) is a combination of the vehicle routing problem (VRP) and inventory management. The military inventory routing problem (MILIRP) is a special case of the IRP in which the delivery vehicles operate in a hostile environment and the risk of loss of vehicles must be taken into account. Risk consideration is a novel approach to the IRP, untouched by the larger research community because typical commercial logistics companies are not concerned with the threat to the delivery vehicle. This characteristic is rather unique to the military environment.
However, much of the work in academia can be modified to satisfy military requirements. An IRP solution identifies which customers are scheduled for a delivery during the current time period, how much supply will be carried to each of those customers, routes for each vehicle, and a delivery schedule for each route. A particular IRP can be defined by seven characteristics:
- Time horizon: The time horizon considered by the problem may be finite or infinite, meaning the problem can have a pre-determined stopping point or not.
- Structure: The problem may contain one depot and one customer (one-to-one), one depot and many customers (one-to-many), or many depots and many customers (many-to-many).
- Routing: Possibilities are direct in the case of only direct deliveries (e.g., a vehicle visits a single customer before returning to the depot), multiple in the case that vehicles visit multiple customers, or continuous in the case that no central depot exists.
- Inventory policy: The policy governing the customers’ inventory levels may be a maximum level in which the customer has a maximum capacity that may not be exceeded or an order-up-to level in which a delivery to a customer always contains the quantity required to fill the customer’s inventory.
- Inventory decisions: In some cases, inventories may be allowed to go into the negative, resulting in a shortage. Shortages may be modeled as back-orders, in which case the shortage is fulfilled in a later time period, or lost sales, in which case the shortage is not filled. Alternatively, the inventory may be restricted to be non-negative. In this case, if the inventory reaches zero, a direct delivery is made to the customer at the expense of a cost penalty.
- Fleet composition: The vehicle fleet may be homogeneous or heterogeneous.
- Fleet size: The fleet may consist of a single vehicle, multiple vehicles, or be unconstrained.
One final property is that of customer demand. If the demand is known a priori for each time period, then the problem is deterministic. Alternatively, the demand may be unknown, in which case the problem is stochastic and is generally modeled using a probability distribution.
The first seven characteristics can adequately describe the MILIRP just as they do the IRP. However, the final property does not adequately describe the MILIRP. The MILIRP models the customer demand in a deterministic fashion (i.e., it is known in advance). However, the property above implicitly assumes a deterministic supply because corporate logistics companies work in environments in which deliveries most often arrive at the intended destination. This assumption is plainly untrue for the military problem. Instead, the MILIRP assumes a stochastic supply from the depot because it takes hostile threats to the vehicles into account, meaning a vehicle dispatched on a route may reach none, some, or all of the customers. Therefore, the supply is stochastic based upon the probability of success associated with a vehicle’s route. Some civilian work has focused on the use of spares in the case of a vehicle breaking down, but only fairly recently was the notion of stochastic supply within the context of an IRP entertained.
To illustrate the points mentioned above as well as to highlight further challenges, consider an example in which customers are combat outposts (COP), the depot is a brigade support battalion (BSB), and the vehicles are UAS. The solution to this problem typically involves truck convoys or manned helicopters making deliveries. Each has drawbacks. The truck convoys are restricted to roadways, meaning their route choices are finite and at least somewhat predictable. A UAS would theoretically have many similar restrictions to a manned helicopter, but in the case of a non-permissive air environment with legitimate threats to air assets, it would hold obvious advantages. Also of note, this aspect of the problem unfolds similarly irrespective of whether the UAS is remotely piloted or autonomous.
One way to translate risk onto a physical map is to impose a hex grid onto the geography and assign a threat level to each hex (high or low). The figure below is an example of such a depiction where the red hexes are the high threat areas and white hexes are low threat. Also, the green dot is the BSB (i.e., the depot) and black dots represent COPs (i.e., customers). The threat map is assumed static within each time period but may change over time periods. Transitions between hexes are assigned a probability based on the threat level of the current hex and the hex into which the vehicle is moving. The development of such a mapping of the operational environment highlights a strong dependency on reliable intelligence. Based on the intelligence limitations as well as delivery timelines, this mapping also implicitly requires a decision on how long the time periods are and how big the hexes are as well as the threshold for what constitutes high and low threat environments.
Given this hex map, one can then use the well-known shortest path algorithm to construct paths between each customer and the depot in which the shortest path is the path with the maximum probability of survival. It is important to note that this route is not necessarily the shortest physical path. Instead, the shortest path is a balance between risk and physical distance. For example, the algorithm instead seeks to balance the time spent at risk with the risk level. This risk level is dependent on a variety of factors such as the specific UAS platform and the threat environment (e.g., probability of kill), but ultimately boils down to a probability of survival. In other words, what is the probability that the UAS will successfully traverse the hex?
Another way of the MILIRP that strays from typical routing concepts is that demand almost always outstrips the delivery capability in some fashion. Therefore, the algorithm must also determine how much of each COP’s demand to fill for a given time period. This differs from the concept of stochastic demand because the demand for each COP is fixed within the current time period but the set of deliveries chosen for that time period may satisfy all, part, or none of this demand.
This problem feature can be modeled by representing customer demand with a curve to account for the diminishing returns of deliveries. While delivering any amount to a COP may be beneficial when viewed as an individual delivery, it may be detrimental in the overall scheme because of the risk incurred with deliveries. More specifically, the risk may outweigh the reward of making a small delivery to a well-stocked COP, yielding a decrease in the overall value of the solution when including that delivery. Given these functions, the total delivery amount to each COP from all routes is calculated and then the future value of each COP’s inventory is calculated in the same fashion as for a single delivery. The value of the total solution is then the sum of these future COP inventory values. The goal of the routing portion is to return a solution with both a high value and secure routes.
Of particular note, the function defining the value of a delivery can be easily manipulated based on real-world priorities and requirements. In essence, this allows the algorithm to reflect the desired risk strategy by setting the criticality of deliveries based on the stock level of each customer. For example, use of a linear function yields the same value for a delivery regardless of the customer’s current stock. Consider instead a curve representing a lower value if the customer’s stock is high. This simply represents the law of diminishing returns, but in turn skews deliveries toward customers with lower stocks, effectively giving customers with lower stocks a priority. The slope of the curve determines the degree of prioritization. In the above case of the risk of a delivery outweighing the reward (e.g., the customer is well-stocked and the current threat level surrounding the customer is high), the curve would then have a negative slope and deter deliveries to that customer.
This idea was examined in a case where the value of the logistics solution outweighed the security of the routes. In this case, the algorithm generated the best routes possible and then adjusted the routes to make them as secure as possible without sacrificing routing efficiency. This particular implementation used four kilometer wide hexes (when measured from the center of a side to the center of the opposite side) and a time period of eight hours. These parameters were chosen based on rudimentary data and require further optimization.
This implementation also accounted for a number of real-world planning factors. Each UAS has a limit on both range and weight, thereby accounting for platform limitations. While not accounted for in this particular implementation, maintenance needs could be accounted for by only availing a percentage of the UAS platforms based on maintenance rates.
This is merely one example in which the military can extend a “commercial-off-the-shelf” mindset beyond physical products into real-world problems. Military problems are unique, but there is often progress on which we can build if we just take the time to look and make the necessary connections. As Winston Churchill once famously said, “We have run out of money, now we have to think.” However, this author is also fond of the “work smarter, not harder” idiom.
Marcus McNabb is an Air Force officer with over 13 years of academic and operational experience as an operations research analyst. He holds a PhD in Operations Research from the Air Force Institute of Technology and has worked in a variety of jobs including test and evaluation, staff of US Air Forces in Europe, the Air Force Nuclear Weapons Center, and the 609th Air and Space Operations Center.
The views expressed are those of the author and do not necessarily reflect the official policy or position of the Department of the Air Force or the U.S. Government.