Predictive routing for autonomous mobility-on-demand systems with ride-sharing

Javier Alonso-Mora, Alex Wallar, Daniela Rus

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

25 Citations (Scopus)
247 Downloads (Pure)

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 languageEnglish
Title of host publicationProceedings 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)
EditorsA. Bicchi, T. Maciejewski
Place of PublicationPiscataway, NJ, USA
PublisherIEEE
Pages3583-3590
ISBN (Print)978-1-5386-2682-5
DOIs
Publication statusPublished - 2017
EventIROS 2017: IEEE/RSJ International Conference on Intelligent Robots and Systems - Vancouver, Canada
Duration: 24 Sep 201728 Sep 2017
http://www.iros2017.org/

Conference

ConferenceIROS 2017: IEEE/RSJ International Conference on Intelligent Robots and Systems
CountryCanada
CityVancouver
Period24/09/1728/09/17
Internet address

Fingerprint

Dive into the research topics of 'Predictive routing for autonomous mobility-on-demand systems with ride-sharing'. Together they form a unique fingerprint.

Cite this