Multi-Objective Mission Route Planning Using Particle Swarm Optimization

The Mission Routing Problem (MRP) is the selection of a vehicle path starting at a point, going through enemy terrain defended by radar sites to get to the target(s) and returning to a safe destination (usually the starting point). The MRP is a three-dimensional, multi-objective path search with constraints such as fuel expenditure, time limits, multi-targets, and radar sites with different levels of risks. It can severely task all the resources (people, hardware, software) of the system trying to compute the possible routes. The nature of the problem can cause operational planning systems to take longer to generate a solution than the time available. Since time is critical in MRP, it is important that a solution is reached within a relatively short time. It is not worth generating the solution if it takes days to calculate since the information may become invalid during that time. Particle Swarm Optimization (PSO) is an Evolutionary Algorithm (EA) technique that tries to find optimal solutions to complex problems using particles that interact with each other. Both Particle Swarm Optimization (PSO) and the Ant System (AS) have been shown to provide good solutions to Traveling Salesman Problem (TSP). PSO_AS is a synthesis of PSO and Ant System (AS). PSO_AS is a new approach for solving the MRP, and it produces good solutions. This thesis presents a new algorithm (PSO_AS) that functions to find the optimal solution by exploring the MRP search space stochastically.