Abstract
The ultimate goal of ridesharing systems is to match travelers who do not have a vehicle with those travelers who want to share their vehicle. A good match can be found among those who have similar itineraries and time schedules. In this way, each rider can be served without any delay and each driver can earn as much as possible without excessive deviation from their original route. We propose an algorithm that leverages biogeography-based optimization (BBO) to solve a multi-objective optimization problem for online ridesharing. It is necessary to solve the ridesharing problem as a multi-objective problem since there are several critical objectives that must be considered simultaneously. We test our algorithm by evaluating performance on the Beijing ridesharing dataset. The simulation results indicate that BBO provides competitive performance relative to state-of-the-art ridesharing optimization algorithms.
Introduction
Ridesharing is a vital tool for reducing urban congestion and fuel consumption, but the underlying mathematical challenge—dynamic ridesharing—is an NP-hard problem. In dynamic environments, riders and drivers appear unpredictably, requiring real-time matching that balances conflicting goals.
Most existing systems focus on single objectives, such as minimizing total distance, or rely on "greedy" local searches that find quick matches but fail to optimize the system globally. This paper addresses the need for a real-time, global optimization approach that can handle multiple conflicting objectives simultaneously—specifically, maximizing the matching rate (the number of successful assignments) and minimizing distance overhead (the extra travel distance required for drivers).
The BBO Framework
The proposed framework utilizes Biogeography-Based Optimization (BBO), an evolutionary algorithm inspired by how species migrate between habitats. In this context, a "habitat" or "island" represents a complete candidate solution consisting of a set of driver-rider matches.
The algorithm operates through two primary mechanisms:
- Migration: High-quality solutions (islands with high suitability) share their matching features with lower-quality solutions. This allows effective matching patterns to propagate through the population of candidate solutions.
- Mutation: Random changes are introduced to maintain diversity and prevent the algorithm from converging prematurely on a "local optimum."
Key Innovations
To adapt BBO for real-time ridesharing, the authors introduced several key innovations:
- Multi-Objective Cost Function: Instead of focusing solely on distance, the authors use a weighted cost function that penalizes both unmatched riders and excessive driver detours.
- Virtual Maps: To overcome simulator limitations and evaluate multiple candidate solutions in parallel, the authors implemented "virtual maps"—duplicates of the road network that allow the algorithm to process different matching strategies in isolation.
- Rolling Horizon: The system batches requests into 30-second windows, solving each batch as a static problem before moving to the next.
Experimental Evaluation
The study used a real-world dataset from the Beijing road network, featuring over 351,000 vertices and 743,000 edges. The authors modified the dataset to reflect peer-to-peer (P2P) ridesharing, where drivers have specific destinations and deadlines. BBO was compared against four other methods: Greedy (GR), Simulated Annealing (SA), T-share (TS), and Kinetic Tree (KT).
Key Insights
- The Randomness Paradox: Surprisingly, initializing BBO with a 100% random population resulted in a lower overall cost than starting with "smarter" greedy-based solutions. This suggests BBO is highly effective at exploring the search space when not limited by local heuristics.
- The Matching/Distance Trade-off: Results highlighted a clear tension between objectives. The T-share algorithm had the lowest distance overhead but also the lowest matching rate because it only accepted the "easiest" matches. BBO found a superior middle ground.
- Roll-back Mechanism: The inclusion of a "roll-back" feature in the migration step—undoing a migration if it leaves a rider unassigned—proved vital for maintaining solution stability.
Results and Conclusion
In performance comparisons, BBO and Kinetic Tree tied for the highest matching rate (~0.48), significantly outperforming T-share (0.32). While T-share performed best in distance overhead (due to fewer matches), BBO maintained a competitive, mid-range overhead. Ultimately, BBO achieved the lowest overall total cost (0.8834), proving it to be the most effective "all-rounder" for dynamic ridesharing.
Future work will address computational complexity, particularly the $O(n^3)$ cost of calculating shortest paths. The authors propose moving toward a distributed BBO framework that partitions the map into smaller domains to handle thousands of concurrent requests in mega-cities.
Summary updated