Minimum Cost Matching for Autonomous Carsharing

Josiah P. Hanna, Michael Albert, Donna Chen, Peter Stone

Research output: Contribution to journalArticlepeer-review


Carsharing programs provide an alternative to private vehicle ownership. Combining car-sharing programs with autonomous vehicles would improve user access to vehicles thereby removing one of the main challenges to widescale adoption of these programs. While the ability to easily move cars to meet demand would be significant for carsharing programs, if implemented incorrectly it could lead to worse system performance. In this paper, we seek to improve the performance of a fleet of shared autonomous vehicles through improved matching of vehicles to passengers requesting rides. We consider carsharing with autonomous vehicles as an assignment problem and examine four different methods for matching cars to users in a dynamic setting. We show how applying a recent algorithm (Scalable Collision-avoiding Role Assignment with Minimal-makespan or SCRAM) for minimizing the maximal edge in a perfect matching can result in a more efficient, reliable, and fair carsharing system. Our results highlight some of the problems with greedy or decentralized approaches. Introducing a centralized system creates the possibility for users to strategically mis-report their locations and improve their expected wait time so we provide a proof demonstrating that cancellation fees can be applied to eliminate the incentive to mis-report location.
Original languageEnglish
Pages (from-to)254 - 259
Number of pages6
Issue number15
Publication statusPublished - 9 Aug 2016
Event9th IFAC Symposium on Intelligent Autonomous Vehicles - Messe Leipzig, Germany
Duration: 29 Jun 20161 Jul 2016


  • Autonomous vehicles
  • autonomous mobile robots
  • Minimal-makespan matching
  • Intelligent Transportation Systems
  • Multi-Vehicle Systems
  • Car-sharing


Dive into the research topics of 'Minimum Cost Matching for Autonomous Carsharing'. Together they form a unique fingerprint.

Cite this