VNS: Optimizing the Last Mile in Urban Crowdsourcing through Advanced Path Planning

TL;DR

Addressing the inherent inefficiencies in "last mile" urban delivery, this research proposes a mathematics-driven scheduling scheme. By combining a Variable Neighborhood Search (VNS) algorithm with dynamic selection probabilities and a greedy heuristic, the authors achieved significant reductions in total distribution distances while respecting strict cargo load and delivery time constraints.

Problem & Motivation: The Last Mile Bottleneck

The rise of e-commerce has turned the "last mile" into a logistics nightmare. While platforms like Amazon Flex and Uber Rush utilize crowdsourced couriers, the Order Dispatching Mode remains suboptimal. Most platforms assign tasks based on simple proximity or earnings, ignoring the complex pathing required once a courier has multiple pickups and deliveries.

The authors identify two critical gaps in prior work:

1. Static Logic: Traditional methods often treat task assignment and path planning as decoupled problems.
2. Local Optima: Standard greedy or heuristic solvers often get stuck in local optima, failing to find the global "shortest path" for a fleet of couriers.

Methodology: Variable Neighborhood Search (VNS)

The paper formalizes the problem as an optimization task: Minimize the sum of distribution path lengths for all couriers subject to Real-time Load Capacity and Time Windows (Pickup/Delivery limits).

1. The Heuristic Foundation (HSA)

To jumpstart the process, a Heuristic Solving Algorithm (HSA) is used for initialization. It employs a greedy strategy, sorting couriers by service quality and tasks by the ratio of "earnings to distance increase."

2. The Four Neighborhood Operations

To refine the solution, the VNS algorithm iteratively explores four "neighborhoods" (structural changes to the schedule):

• Migration Task: Moving a task from one courier to another or assigning an unassigned task.
• Exchange Task: Swapping tasks between two couriers.
• Exchange Consigner Point: Swapping pickup locations within a single courier's route.
• Exchange Customer Point: Swapping delivery locations within a single courier's route.

3. Adaptive Selection Probability

Unlike standard VNS, this paper introduces a Selection Probability ($P_n$). If a specific neighborhood operation successfully improves the solution, its probability increases; if it fails, it decreases. This "warm-reboot" style mechanism ensures the algorithm doesn't waste time on unproductive search spaces.

(Note: Refer to Figures 3-7 in the original paper for detailed diagrams of task migration and exchange operations.)

Experiments & Results: Performance at Scale

The researchers tested the VNS against HSA and a modified TAAP (Ant Colony Algorithm) across scenarios involving up to 80 consigners and 200 tasks.

Key Findings:

• Solution Quality: VNS consistently outperformed TAAP and HSA in minimizing the total path length.
• Efficiency: While HSA is faster due to its simple greedy nature, VNS is more efficient than TAAP, making it viable for real-time dispatching.
• Ablation (Neighborhood Impact): The "Migration Task Operation" (Operation 1) was found to be the most critical for optimization; removing it led to the largest degradation in solution quality.

(Note: Refer to Figures 8 and 9 in the paper for the specific comparison of path lengths and running times.)

Critical Insight & Conclusion

The true value of this work lies in its holistic modeling. By treating the "pickup-delivery" pair as a single task that occupies load and time intervals, the algorithm moves beyond simple point-to-point routing.

Limitations: The paper currently assumes static conditions. Future iterations would benefit from accounting for dynamic traffic conditions and stochastic task arrival, which are common in real-world urban environments. However, as it stands, this VNS framework provides a robust mathematical foundation for any platform looking to reduce its carbon footprint and logistics costs.

Final Takeaway

Optimization in crowdsourcing isn't just about who gets the task—it's about the sequence in which they execute it. Dynamic VNS provides the flexibility needed to manage that complexity.