TAGP: Balancing Global Efficiency and Local Fairness in Multi-Center Crowdsourcing

TL;DR

Spatial Crowdsourcing (SC) is the backbone of the "gig economy"—think food delivery and courier services. However, most research treats cities as one giant playground for workers. This paper, published at CIKM '21, introduces a more realistic Multi-Center-based Task Allocation (MCTA) problem. By combining a smart geographic "partitioning" strategy with Reinforcement Learning, the authors achieve nearly 100% task completion while ensuring that no single worker is overwhelmed or left idle.

The "Chain Store" Pain Point: Why Global Optimization Fails

Imagine a city with ten "Hema Xiansheng" fresh food markets. Theoretically, any driver could pick up an order from any store. In reality, stores manage their own local fleets and responsible areas.

Existing SOTA methods struggle with two things:

1. Fixed Boundaries: They often assign tasks to the closest center, even if that center is overloaded.
2. Greedy Allocation: They focus on total tasks but ignore Fairness. If Worker A does 20 tasks and Worker B does 2, Worker B will eventually leave the platform.

The authors argue that we need a way to adaptively redrawn the maps of store responsibility based on real-time demand.

Methodology: From Geometry to Deep Learning

The proposed TAGP framework operates in two distinct phases:

1. Geographic Partition (The "Where")

Standard Voronoi Diagrams partition space based purely on distance. If a delivery point is closer to Center A, it belongs to Center A. The authors propose AWVDA (Adaptive Weighted Voronoi Diagram-based Algorithm). It uses an Adaptive Weight ($a{w}_i$) calculated by the ratio of current tasks to available workers.

• Insight: If Center A has too many tasks, its "territory" effectively shrinks in the algorithm's eyes, pushing peripheral tasks to Center B, which might have more idle workers.

2. RL-based Task Allocation (The "How")

Once the map is divided, each center becomes a sub-graph. The authors use a Compositional Message-passing Neural Network (CMPNN) to create sophisticated embeddings:

• Spatial Relationships: CMPNN ensures delivery points near each other have similar "features."
• Attention Mechanism: A multi-head attention layer determines how important a specific delivery point is to a specific worker's route.

The reward function in their RL model is ingenious—it's a ratio: $Re(A_c)=\frac{|TotalTasks|}{Distanceimes|WorkloadDifference|}$ This forces the agent to maximize tasks while penalizing both long travel distances and unfair distribution among workers.

Figure 1: The Multi-center problem context and partitioned logic.

Experiments & Results

The authors tested their framework against Genetic Algorithms (GA) and Simulated Annealing (SA).

• Efficiency: As the number of delivery points ($|P|$) scales up to 5,000, AWVDA+RL maintains high throughput where others drop off.
• Fairness: The "Average Allocated Task Number Difference" is the killer metric here. While GA and SA resulted in high variance, RL-related methods kept the difference near zero, even as task volume increased.
• Quantity: In synthetic environments, TAGP achieved a staggering 99.9% task completion rate.

Figure 2: Performance metrics showing total tasks vs. scalability.

Critical Insight & Future Outlook

The genius of this paper is not just the RL, but the pre-processing step of Geographic Partitioning. By breaking the "NP-hard" global problem into smaller, adaptive "local" problems using Voronoi logic, they make high-dimensional optimization computationally feasible.

Limitations: The model assumes workers stay within one center's jurisdiction. In future work, allowing workers to "migrate" between centers during peak hours could further optimize city-wide performance. Furthermore, adding real-time traffic variance into the $tc(a,b)$ function would make this production-ready for companies like Meituan or Uber Eats.

Final Takeaway: For spatial crowdsourcing, the map isn't static. It breathes with the data.