Abstract
Ride-sharing, or carpooling, systems with autonomous vehicles will provide efficient and reliable urban mobility on demand. In this work we present a method for dynamic vehicle routing that leverages historical data to improve the performance of a network of self-driving taxis. In particular, we describe a constrained optimization method capable of assigning requests to autonomous vehicles in an informed way, to minimize the expected cost of serving both current and future travel requests. We allow several passengers with independent trips to share a vehicle and allow vehicles to pick additional passengers as they progress through their route. Based on historical data, we compute a probability distribution over future demand. Then, samples from the learned probability distribution are incorporated into a decoupled vehicle routing and passenger assignment method to take into account the predicted future demand. This method consists of three steps, namely pruning of feasible trips, assignment of trips to vehicles and rebalancing of idle vehicles. We show the benefits and trade-offs of this predictive approach in an experimental evaluation with over three million rides extracted from a dataset of taxi trips in New York City. Our method produces routes and assignments that, in expectation, reduce the travel and waiting times for passengers, with respect to a purely reactive approach. Besides the mobility on demand application, the method we present is general and could also be applied to other multi-task multi-vehicle assignment and routing problems.
Original language | English |
---|---|
Title of host publication | Proceedings 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) |
Editors | A. Bicchi, T. Maciejewski |
Place of Publication | Piscataway, NJ, USA |
Publisher | IEEE |
Pages | 3583-3590 |
ISBN (Print) | 978-1-5386-2682-5 |
DOIs | |
Publication status | Published - 2017 |
Event | IROS 2017: IEEE/RSJ International Conference on Intelligent Robots and Systems - Vancouver, Canada Duration: 24 Sept 2017 → 28 Sept 2017 http://www.iros2017.org/ |
Conference
Conference | IROS 2017: IEEE/RSJ International Conference on Intelligent Robots and Systems |
---|---|
Country/Territory | Canada |
City | Vancouver |
Period | 24/09/17 → 28/09/17 |
Internet address |