Distributed and Transferable Task Assignment for Dynamic Pickup-and-Delivery With Time Windows

Abstract

Dynamic task allocation in multi-UAV systems, where pickup-and-delivery tasks arrive randomly with time windows, is challenging due to two main factors: (1) strict temporal and spatial constraints, and (2) reduced allocation optimality caused by unforeseen tasks. This paper proposes a distributed auction algorithm based on potential rewards to maximize total system profit. The algorithm operates in two phases. In the first phase, each UAV independently generates feasible task groups according to temporal and spatial constraints and evaluates candidate tasks by considering selection flexibility, cost-effectiveness, and discounted future value. In the second phase, UAVs engage in a distributed auction, exchanging bids with neighbors to reach consensus and achieve conflict-free assignments. To further enhance flexibility, a task transfer protocol is introduced, allowing idle UAVs to take over assigned but unpicked-up tasks if the tasks can be completed ahead of schedule, thereby freeing the originally assigned UAVs to pursue more profitable opportunities. Simulation results on 30 benchmark instances adapted from the Solomon dataset show that the proposed method outperforms three state-of-the-art online baselines-Consensus-Based Bundle Algorithm (CBBA), CBBA with Partial Replanning (CBBA-PR), and Distributed Group-Based Auction Algorithm (DGAA). Moreover, it achieves near-optimal performance in balanced scenarios and competitive results in high-density cases when compared with the offline solver OR-Tools.