Autonomous Mobility-on-Demand (AMoD) systems—fleets of self-driving, electric vehicles—promise to revolutionize urban transportation by reducing congestion and emissions. However, the success of these systems hinges on efficient ridesharing, which presents a significant challenge: how to group selfish passengers in real-time while ensuring they report their travel needs truthfully.
Existing theoretical models often rely on "offline" auctions or batch processing, which require passengers to wait for a quote or reveal complex valuation data. This paper, presented at IJCAI-16, introduces IORS (Integrated Online Ridesharing), a practical, real-time mechanism that uses a "posted-price" model to balance system efficiency with realistic human behavior.
The IORS Mechanism
The IORS framework is designed to provide immediate gratification to users through a three-step algorithmic process:
- Fare Estimation: When a request arrives, the system immediately generates a fare quote. This quote acts as an upper bound. Crucially, a new passenger is only added to a "coalition" (a shared ride) if their presence decreases the cost per unit of demand for the entire group.
- Pickup Assignment: A greedy-style algorithm assigns requests to vehicles with available seats (up to 4 passengers) to minimize the operational cost per unit of distance.
- Payment Calculation: Once the ride is complete, the final payment is calculated. Because the system is "budget-balanced," the total operational cost is split among the passengers.
A key innovation of IORS is its ex-post incentive compatibility. The authors provide mathematical proofs showing that a passenger cannot lower their fare by delaying their request or misreporting their latest possible departure time. By tying fares to the actual marginal cost added to the fleet, the system aligns individual savings with global efficiency.
Experimental Evaluation
The researchers evaluated IORS using a custom-built AMoD simulator representing a 101 x 101 grid city with a fleet of 1,000 autonomous vehicles. The simulation ran for 500 rounds with demand generated via a normal distribution. IORS was benchmarked against two extremes:
- Optimal Assignment: An NP-hard benchmark calculating the absolute best theoretical outcome using linear programming.
- Auction-Based Mechanism: A state-of-the-art offline mechanism that processes requests in batches.
Key Results and Insights
IORS demonstrated remarkable performance, achieving 93.62% of the social welfare score of the theoretical "Optimal" solution while significantly outperforming the offline auction-based benchmark by 22.73%.
Beyond efficiency, the primary advantage of IORS is its computational speed. The mechanism required 79.35% less computational time than the optimal solver. This is due to the fare estimation algorithm's $O(n^3)$ complexity, which is far more scalable than NP-hard solutions. Furthermore, IORS requires zero knowledge of future demand, making it a truly "online" solution ready for unpredictable real-world scenarios.
Limitations and Future Work
While highly effective, IORS is a "myopic" mechanism; its greedy nature means it may occasionally fall into local minima by accepting a request now that prevents a better grouping later. The current model also assumes a simplified grid environment with uniform speeds. Future research aims to incorporate more complex routing variables, explore advanced coalition structure generation, and address the privacy concerns inherent in sharing rides with strangers in a non-grid, realistic simulation platform.
Summary updated