Energy-Aware Task Allocation for Drone Package Delivery

This paper addresses the task allocation problem for a drone package delivery scenario, where a number of warehouses delivery packages to a number of locations using drones. A novel algorithm, namely, Duplicate Agent Hungarian Based Algorithm (DAHBA), is proposed. DAHBA adopts cloned agents and pseudo tasks to build a square cost matrix such that the The Hungarian method can be applied. The same task allocation problem is also implemented and solved by state-of-the-art commercial optimization software, AMMIS, with the CPLEX solver, which is set to generate the global optimal solution. We also proposed a motion planning approach for each drone to find the optimal airspeed using a comprehensive energy consumption model. The simulation results show that the proposed DAHBA is able to produce the global optimal solution for all test cases. The solution time of DAHBA over CPLEX increases when the ratio of the number of tasks to the number of agents increases.