Abstract
We develop and test computational methods for guiding collaboration that demonstrate how shared plans can be created in real-world settings, where agents can be expected to have diverse and varying goals, preferences, and availabilities. The methods are motivated and evaluated in the realm of ridesharing, using GPS logs of commuting data. We consider challenges with coordination among self-interested people aimed at minimizing the cost of transportation and the impact of travel on the environment. We present planning, optimization, and payment mechanisms that provide fair and efficient solutions to the rideshare collaboration challenge. We evaluate different VCG-based payment schemes in terms of their computational efficiency, budget balance, incentive compatibility, and strategy proofness. We present the behavior and analyses provided by the ABC ridesharing prototype system. The system learns about destinations and preferences from GPS traces and calendars, and considers time, fuel, environmental, and cognitive costs. We review how ABC generates rideshare plans from hundreds of real-life GPS traces collected from a community of commuters and reflect about the promise of employing the ABC methods to reduce the number of vehicles on the road, thus reducing CO2 emissions and fuel expenditures.
Introduction: The Challenge of Open-World Collaboration
While ridesharing offers significant environmental and economic benefits, implementing it at scale remains a complex challenge. This research addresses ridesharing as an "open-world" collaboration problem involving self-interested participants with diverse priorities. Commuters value their time differently, have varying schedules, and experience different levels of stress from driving.
Existing platforms often act as passive bulletin boards, leaving the burden of negotiation, routing, and fair cost-sharing to the users. This paper introduces an active, automated system—the ABC prototype—designed to learn user preferences, optimize complex routes, and provide financial incentives that encourage fair participation and truthful reporting.
The ABC Prototype: Learning and Optimization
The authors introduce the ABC (Agent-Based Carpool) prototype, which integrates three core components to facilitate automated coordination:
- User Modeling: Instead of assuming uniform costs, the system learns individual preferences. It uses GPS traces to identify routes and scans digital calendars to estimate the "cost of time." For example, the cost of a delay is significantly higher if it conflicts with a scheduled meeting.
- Optimization Engine:
- Plan Generation: Routing is treated as a search problem using A* search to find the most efficient way to pick up and drop off passengers while minimizing total travel time and fuel.
- Group Assignment: This is framed as a Set Cover problem. To handle the computational complexity of large-scale coordination, the authors utilize a greedy approximation algorithm.
- Payment Mechanism: To ensure fairness, the system employs Vickrey-Clarke-Groves (VCG) payments. Users pay or receive amounts based on the "externality" they impose on the group, encouraging honest preference reporting. A threshold-based version is used to maintain budget balance.
Evaluation: Real-World Impact in Seattle
The study is grounded in a massive real-world dataset consisting of Seattle GPS logs from 215 subjects collected over five years, containing over 1.4 million data points. The authors extracted 7,377 individual trips, narrowing them down to 215 consistent commute patterns to test the system's efficiency.
Using the Seattle dataset, the ABC system achieved:
- 41% Reduction in Commutes: The system successfully consolidated nearly half of the individual trips into shared rides.
- 14% Total Cost Savings: This includes the combined value of fuel, time, and "cognitive effort" (the stress of driving).
- Environmental Impact: For the test group, the system projected a reduction of 84.16 tons of CO2 per year.
Key Insights and Discussion
The research highlights several critical factors for successful ridesharing:
- The Multi-Dimensional Cost of Collaboration: Success depends on accounting for "cognitive costs" and "delay costs" alongside fuel savings. A system must balance the stress of driving against the annoyance of being a passenger.
- Time Sensitivity: As the "cost of time" for participants increases, the efficiency of the ridesharing system drops. If time is extremely valuable, the cost of picking up a neighbor may outweigh fuel savings.
- Density is a Superpower: The system’s efficiency grows logarithmically with the number of participants. A higher density of users increases the probability of finding optimal matches with minimal detours.
While the results are promising, future work aims to address psychosocial barriers, such as the preference for riding with friends, by integrating social network data into utility functions. Additionally, extending the model to handle dynamic, "on-the-fly" requests remains a key area for development.
Summary updated