Generating Shared Transportation Plans Under Varying Preferences: Ridesharing Models and Mechanisms

We introduce and test computational methods that provide a principled approach to ridesharing. We address several challenges with collaboration and coordination among self-interested people aimed at minimizing the cost of transportation and the impact of travel on the environment. The work investigates the problem of applying mechanism design ideas to a dynamic, real-life problem, and evaluates different VCG-like payment schemes in terms of their computational efficiency, budget-balance, incentive compatibility and strategy-proofness in this domain. The Agent-based Carpooling (ABC) methodology employs planning, optimization, and payment mechanisms that provide fair and efficient solutions to the rideshare collaboration challenge. We review the behavior of a working ABC prototype that learns about destinations and preferences from GPS traces and calendars, and considers time, gas, and cognitive costs. ABC identifies beneficial ridesharing plans by performing cost-benefit analyses. The system provides incentives to collaborate in ridesharing by introducing a VCG-based payment mechanism. The ABC methods and prototype have been applied to precomputed, scheduled contexts as well as dynamic settings where requests are handled on the fly, and evaluated on hundreds of real-life GPS traces collected from a community of commuters. The evaluations show promise for reducing the number of vehicles on the road, thus reducing CO2 emissions and fuel expenditures.