Unmanned aerial vehicles (UAVs) have proven themselves indispensable in providing intelligence, reconnaissance, and
surveillance (ISR). We foresee a future where constellations of multi-purpose UAVs will be tasked to provide ISR in an
unpredictable environment. Automated systems will process imagery and other sensor data gathered by the
constellations to provide continuous situational awareness for the warfighter on the ground. In this paper, we present a
tool that generates coordinated mission plans for constellations of UAVs with multiple goals and objectives. We call this
tool Spatially Produced Airspace Routes from Tactical Evolved Networks, or SPARTEN. SPARTEN uses evolutionary
algorithm (EA)-based, multi-objective optimization to generate coordinated sortie routes for constellations of UAVs.
These sortie routes maximize sensor coverage, avoid conflicts between UAVs, minimize the latency of sensor data, and
avoid areas of poor weather to provide valid route solutions. We use an Air Maneuver Network (AMN) based on terrain
reasoning to constrain the solution space. We make two contributions to the field of UAV route planning. We develop a
tool to optimize planning across multiple objectives for constellations of UAVs, and we explore the performance of this
tool on a battlefield scenario.