Solution to a Multicriteria Aircraft Routing Problem Utilizing Parallel SearchTechniques

摘要

Pilots select routes based on factors such as threats, fuel, time on target,distance, and refueling points. This is a time consuming task. This thesis presents the software engineering synthesis of a software tool, based on a parallelized A* search algorithm, to select routes. For simplicity only threats and distance are used. A centralized open list is used with one processor managing the list while the other processors perform the node expansions. This decomposition results in a dynamically load balanced system. A number of parameters are changed to study their impact on the execution time. The use of a branch and bound technique and its impact on the execution time is studied. Other parameters examined are the size of the supercomputer and granularity of the algorithm. It is important to match the software granularity to the architecture to ensure maximum utilization of the supercomputer and minimize execution time. Tests were run on both an iPSC/2 and iPSC/860 to determine the effects of the architecture upon the execution time. In conjunction with execution time, the efficient usage of the parallel computer was also examined.