Unmanned Aerial Vehicles have the potential to provide an economical solution to the challenges of post-disaster land-based relief operations. Beyond regulatory concerns, technical and particularly airspace integration limitations inhibit their deployment in practice. To address these issues and ensure uninterrupted optimal operations, we present a novel approach consisting of an integrated trajectory-location-routing algorithm that seeks to determine the optimal location of supporting infrastructure in the distribution supply chain. Unique to this approach is the consideration of dynamic obstacle avoidance and variable battery consumption relationships. An approximate algorithm based on a bi-level Large Neighbourhood Search is used to obtain close to optimal solutions under reasonable runtime. Results show that fleets of small UAVs could quickly distribute relief supplies to affected population groups with minimal reliance on ground infrastructure.