A Heuristic Planning Algorithm For Highly Constrained Maximum on Ground Problems

In military operations, logistics distribution involves the transportation of equipment, people and sustainment (resources) to various physical locations, known as distribution nodes. The quantity of items being transported is often very large and the resources need to be moved as quickly as possible using the available transportation assets. A complicating factor is that the airports at the distribution nodes typically have a limitation on the number of aircraft that can be present at one time. This is known as a Maximum on Ground (MOG) constraint. In simple cases, the MOG problem can be overcome by waiting for aircraft spots to become free. However in larger scenarios where there are more aircraft and more movements, there is a greater likelihood of congestion. In these cases waiting can cause deadlocks, where an aircraft is unable to move because it relies on another aircraft moving first. Starvation can also arise when an aircraft is indefinitely waiting for a spot to become free, but other aircraft are continually using it. This paper presents a Maximum on Ground Algorithm (MGA) for dealing with deadlock and starvation, and resolving congestion in highly constrained scenarios. The MGA uses a combination of heuristics to overcome congestion and find solutions in the presence of MOG constraints. For example, consider the scenario shown in Figure 1. In this case there is only one MOG spot at each airport, so movement between airports is very constrained. The MGA uses the forced move, swap and shuffle heuristics to assist a task aircraft in completing its movement. This is accomplished by reorganizing the other aircraft in the scenario, so that the task aircraft can reach its destination without violating any MOG constraints. Each of these heuristics provides a unique way of reorganizing the scenario, which is applicable in a particular set of cases. On the other hand, the multi-shuffling heuristic focuses on assisting the task aircraft by identifying a utility aircraft to provide assistance. The MGA identifies the constraints in a given scenario, and determines the best combination of heuristics to apply in order to overcome those constraints and find a solution. A series of trials have demonstrated that the MGA is computationally efficient, capable of quickly solving moderate to large scenarios. The most computationally intensive heuristic is multi-shuffling, which involves each aircraft sending a request to every other aircraft. This results in a quadratic worst-case time complexity for the algorithm. In addition to rapid computation, the MGA produces efficient solutions by coordinating aircraft so that each task can be completed as quickly as possible without violating any MOG constraints. This is particularly true for the simpler cases, where the algorithm is able to achieve near-optimal efficiency.