SMF-GA: Optimizing the Sharing Economy via Intelligent Multi-Task Allocation

TL;DR

Urban transport crowdsourcing is more than just "finding the nearest ride." It’s about complex multi-point routing and capacity management. This paper presents SMF-GA, a hybrid algorithm that combines a novel "Saving Most First" heuristic with Genetic Algorithms to solve the combinatorial nightmare of carpooling and package delivery, significantly reducing city-wide travel distances.

Problem & Motivation: Beyond Single-Point Crowdsourcing

Most crowdsensing research treats tasks as static dots on a map. However, in the Sharing Economy, a task is a vector: you have a pickup point $s_n$ and a drop-off point $d_n$.

The challenges are three-fold:

1. Temporal Constraints: The worker must be available before the task starts.
2. Order Constraints: You cannot drop off a package before you pick it up.
3. Capacity Constraints: A vehicle has finite seats/space.

Standard "Nearest First" (NF) logic often fails because picking up the closest person might force a massive detour in the opposite direction later. The authors realized we need a strategy that looks at the Total Saved Distance—the difference between everyone driving separately versus sharing a single route.

Methodology: Saving Most First (SMF) meets GA

The authors introduce a dual-layered strategy to tackle the optimization:

1. The SMF Heuristic

Instead of distance, the algorithm calculates the Saved Distance ($sv$). For a route $x_m$ and a task $y_n$, the saved distance is: $sv(x_m,y_n)=dis(s_m,d_m)+dis(s_n,d_n)-[dis(s_m,s_n)+dis(s_n,d_n)+dis(d_n,d_m)]$ This formula captures the efficiency of merging two separate trips into one.

2. The SMF-GA Hybrid

Genetic Algorithms (GA) are great at global searching but often get lost in massive solution spaces. By using the SMF result as the "Seed" (initial population), the GA starts much closer to the global optimum.

Figure 1: The mathematical foundation for distance calculation in urban grids using the taxicab metric.

Key Operators:

• Crossover: Exchanging task-assignment "genes" between potential solutions.
• Mutation: Randomly re-assigning a task to a different route to maintain diversity.

Experiments: Real-World Performance

The study used the famous T-Drive dataset (Beijing taxi trajectories). The results were definitive:

• Convergence Speed: SMF-GA reached its peak performance in approximately 400 cycles, while standard Genetic Algorithms required over 1,200 cycles to catch up.
• Efficiency: As the number of tasks increased, the "Nearest First" method actually led to negative returns (longer distances than separate travel), whereas SMF-GA maintained positive efficiency.

Figure 2: Saved distance comparison showing SMF-GA's dominance over NF and pure GA baselines.

Critical Insights & Takeaways

The brilliance of this work lies in the Inductive Bias given to the Genetic Algorithm. Pure GA is blind; it explores the space randomly. By injecting the SMF heuristic, the authors provide the "evolution" with a head start.

Limitations:

• The current model uses Manhattan distance, which may not perfectly reflect real urban traffic delays or one-way streets.
• It assumes a "static" set of tasks; in the real world, tasks arrive dynamically (on-demand).

Future Outlook: Integrating this SMF logic into a Deep Reinforcement Learning (DRL) agent could allow for real-time, second-by-second re-allocation as traffic conditions change.