Planning dissimilar paths for military units

This paper considers the problem of determining spatially and temporally dissimilar paths for military aircraft during mission ingress. Finding such paths is important to avoid mission detection. The problem is modeled as a combination of the well studied p-dispersion problem and the quadratic semi-assignment problem. We first demonstrate how a network can be generated for a region given terrain information. This network-generation procedure uses a rule-based heuristic. Given the network, a combination of the p-dispersion heuristic and the tabu search procedure is utilized sequentially to arrive at a desirable set of routes. An example problem is presented, and computational results are reported for a case study based on a section of Tioga County, New York.