A branch-and-price algorithm for emergency humanitarian logistics with a mixed truck-drone fleet

Humanitarian aid distribution often prioritizes rapid relief operations or emergency services under time constraints, as opposed to commercial transportation problems, where the primary objective is to minimize operational costs. Drones can offer immense potential to achieve this goal by leveraging their aerial mobility. Specifically, drones can surpass ground transportation and navigate directly through disrupted or inaccessible roads, ensuring the quickest path to deliver aid where the ground vehicle may face obstacles. However, drones have limitations in terms of flying range and load capacity. To effectively provide time-sensitive emergency services, combining a ground vehicle with one or more aerial vehicles enhances coverage. Our approach integrates a truck as a mobile depot for multiple drones, where a drone battery is replenished on landing after a flight, and the fleet operates in tandem to serve the locations visited. We formulate a mixed-integer linear programming (MILP) model to maximize the weighted sum of locations served by this mixed truck-drone fleet under time constraints. We further develop a branch-and-price algorithm to solve this problem, where the pricing subproblem is solved using dynamic programming recursions with dominance rules. Our results demonstrate the computational superiority of this method compared to a commercial optimization solver and its potential for expediting aid distribution during an emergency.