GraC 2 Allocator: An RL-Based Hypergraph k -Cut and Coloring Approach to UAV-Assisted Last-Mile Urban Logistics

Unmanned Aerial Vehicles (UAVs) have emerged as a promising solution for urban logistics due to their flexibility, cost-efficiency, and rapid responsiveness. However, the spatial and temporal heterogeneity of large-scale parcel orders, combined with the neglect of critical post-delivery steps such as UAV hovering, returning, and recipient confirmation, poses major challenges to coordinated task scheduling and hinder system scalability. To address these challenges, we propose GraC²Allocator, a comprehensive two-phase framework for UAV-assisted last-mile urban logistics network. It covers the full service chain from the city-level transit center, through courier stations, to parcel recipients. In Phase 1, Parcel-to-Station Allocation is formulated as a hypergraph k-cut problem and optimized via a reinforcement learning (RL) strategy enhanced by Graph Neural Networks (GNNs) and the multi-head attention mechanism, thereby minimizing inter-group cutting cost and enhancing the spatio-temporal coherence of parcel clusters. In Phase 2, Parcel-to-UAV Allocation is modeled as a pruning theory based dynamic graph coloring problem: 1) Edge reconfiguration guarantees an inter-task conflict-free scheduling result; 2) Lightweight recoloring achieves a near-100% task execution rate (TER), approaches the theoretical lower bound on the number of required UAVs (i.e., the smallest chromatic number), and reduces computation complexity. Extensive evaluations based on real-world logistics data from Hangzhou City demonstrate that the proposed GraC²Allocator framework achieves up to about 130% improvement in delivery efficiency, 60% reduction in UAV deployment, and 70% reduction in end-to-end transmission delay compared with baselines, thereby enabling highly efficient, scalable, and full-life-cycle on-demand delivery in dense urban environments.