Unmanned Aerial Vehicles (UAVs) are being increasingly considered to enhance humanitarian response operations. Beyond regulations, vehicle range and integration with the humanitarian supply chain inhibit their deployment. To address these technical issues, we present a novel bi-stage approach consisting of a trajectory optimisation algorithm that considers multiple flight stages, and a hub selection-routing algorithm that incorporates a unique battery management heuristic. We apply the algorithm to the earthquake response in Taiwan after the Chi-Chi earthquake of 1999 considering mission duration and distribution fairness. Results indicate that UAV fleets can be used for rapid relief provision to affected population groups.