Optimizing the "Last Mile": A Crowdsourcing-Based Path Selection Model for Takeout Delivery

TL;DR

As global food delivery platforms face surging demand, this paper introduces a specialized path-optimization model that treats crowdsourced delivery as an integrated resource allocation problem. By balancing route distance with strict timeout penalties using a Genetic Algorithm, the authors achieve a solution that significantly reduces delivery delays while maintaining low personnel costs.

Background: The Crowdsourcing Shift

The "Internet+" era has transformed takeout from a luxury to a daily necessity. However, the sheer volume of orders during peak hours (e.g., 11:00 AM – 1:00 PM) creates a logistics bottleneck. Crowdsourcing—outsourcing tasks to a distributed network of non-professional drivers—offers a flexible solution, but only if the Dispatch Mode (allocating orders to drivers centrally) is optimized for efficiency.

Problem & Motivation: Beyond Simple Distance

Why is delivery optimization so hard? It’s not just about the shortest path. In the real world, a delivery person must:

1. Pickup first, deliver second: The pair-wise constraint of the restaurant and the customer.
2. Handle time windows: Food quality degrades, and customers lose patience.
3. Manage multiple orders: A driver might carry 5-8 orders at once, each with different priorities.

Previous works often focused solely on distance. This paper argues that timeout duration is a critical "cost" that must be quantified alongside fuel/electricity costs to provide a commercially viable solution.

Methodology: The Core Engine

The authors propose a multi-objective optimization model aimed at minimizing the total "Global Cost."

1. The Cost Function

The objective function is a weighted sum of:

• Distance Cost: Calculation of kilometers traveled scaled by vehicle depreciation and power consumption.
• Time Cost: A progressive penalty mechanism where delays over 15 minutes (severe timeouts) are charged at double the rate of normal delays.
• Reward Incentives: Adjustments based on the number of successfully completed orders.

2. Genetic Algorithm (GA) Implementation

To solve the NP-hard nature of the Vehicle Routing Problem (VRP), the authors used a Genetic Algorithm with a unique strategy:

• Integer Coding: Representing orders as sequences.
• Pair-wise Insertion: Ensuring that a pickup point ($i^{+}$) always precedes the delivery point ($i^{-}$) in any generated chromosome.

Fig 1: The logical flow shows how order allocation acts as the foundation for the subsequent route optimization phase.

Experiments & Results

The model was tested using real-world coordinate data (via Google Maps) for 60 orders in a high-density area.

Key Metrics:

• Environment: 60 Orders, 10 Delivery People (1:6 Ratio).
• Travel Distance: The optimized total distance for the fleet was 96.33 km.
• Timeout Control: Despite the high load, serious delivery timeouts were limited to just 3.15 minutes, proving the model's ability to prioritize urgent orders effectively.

Fig 2 (Placeholder): The iterative graph shows how the total cost drops sharply and stabilizes around the 360th generation.

Critical Insight & Conclusion

The true value of this work lies in its holistic cost definition. By translating "minutes of delay" into "CNY cost," the model allows platform operators to fine-tune the balance between speed and profitability.

Limitations: The model assumes a constant delivery speed and ignores the variable "waiting time" at restaurants. In future work, incorporating real-time traffic data and dynamic restaurant preparation times would make this model even more robust for metropolitan deployment.

Takeaway for Industry: For O2O platforms, the key to efficiency isn't just "more drivers," but the algorithmic intelligence to minimize the overlap of routes and maximize the "utility" of every trip.