research-article

Open access

Real-Time Rideshare Driver Supply Values Using Online Reinforcement Learning

Authors:

Sébastien MartinAuthors Info & Claims

KDD '22: Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

Pages 2968 - 2976

https://doi.org/10.1145/3534678.3539141

Published: 14 August 2022 Publication History

Abstract

In this paper, we present Online Supply Values (OSV), a system for estimating the return of available rideshare drivers to match drivers to ride requests at Lyft. Because a future driver state can be accurately predicted from a request destination, it is possible to estimate the expected action value of assigning a ride request to an available driver as a Markov Decision Process using the Bellman Equation. These estimates are updated using temporal difference and are shown to adapt to changing marketplace conditions in real-time. While reinforcement learning has been studied for rideshare dispatch, fully-online approaches without offline priors or other guardrails had never been evaluated in the real world. This work presents the algorithmic changes needed to bridge this gap. OSV is now deployed globally as a core component of Lyft's dispatch matching system. Our A/B user experiments in major US cities measure a +(0.96±0.53)% increase in the request fulfillment rate and a +(0.73±0.22)% increase to profit per passenger session over the previous algorithm.

References

[1]

Juan Camilo Castillo, Dan Knoepfle, and Glen Weyl. 2017. Surge Pricing Solves the Wild Goose Chase. In Proceedings of the 2017 ACM Conference on Economics and Computation (Cambridge, Massachusetts, USA) (EC '17). Association for Computing Machinery, New York, NY, USA, 241--242.

Digital Library

[2]

Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall, and Werner Vogels. 2007. Dynamo: amazon's highly available key-value store. In SOSP. ACM, 205--220.

[3]

Benjamin Han. 2020. Open Source Implementation using TD(0). https://www.biendata.xyz/forum/view_post_category/1048/

[4]

Benjamin Han and Carl Arndt. 2021. Budget Allocation as a Multi-Agent System of Contextual & Continuous Bandits. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining (KDD '21). 2937--2945.

Digital Library

[5]

Geoffrey Hinton. 2014. rmsprop: Divide the gradient by a running average of its recent magnitude. https://www.cs.toronto.edu/ tijmen/csc321/slides/lecture_slides_lec6.pdf

[6]

Zhiwei (Tony) Qin, Hongtu Zhu, and Jieping Ye. 2021. Reinforcement Learning for Ridesharing: A Survey. CoRR, Vol. abs/2105.01099 (2021).

[7]

Jaein Song, Yun Ji Cho, Min Hee Kang, and Kee Yeon Hwang. 2020. An Application of Reinforced Learning-Based Dynamic Pricing for Improvement of Ridesharing Platform Service in Seoul. Electronics, Vol. 9, 11 (2020).

[8]

Richard S. Sutton and Andrew G. Barto. 2018. Reinforcement Learning: An Introduction second ed.). The MIT Press. http://incompleteideas.net/book/the-book-2nd.html

Digital Library

[9]

Xiaocheng Tang, Fan Zhang, Zhiwei Qin, Yansheng Wang, Dingyuan Shi, Bingchen Song, Yongxin Tong, Hongtu Zhu, and Jieping Ye. 2021. Value Function is All You Need: A Unified Learning Framework for Ride Hailing Platforms. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining (KDD '21). 3605--3615.

Digital Library

[10]

Uber Technologies. 2021. Hexagonal hierarchical geospatial indexing system. https://h3geo.org/

[11]

Jacob van Gogh, Benjamin Han, and Alex Contryman. 2020. Team Hail Mary 2020 KDD Cup Submission. https://github.com/jrvangogh/kddcup-2020/blob/master/model/agent.py

[12]

Erich Veach, Jesse Rosenstock, Eric Engle, Robert Snedegar, Julien Basch, and Tom Manshreck. 2021. S2 Geometry. http://s2geometry.io/

[13]

Yansheng Wang, Dingyuan Shi, Maoxiaomin Peng, Yi Xu, and Yongxin Tong. 2020. 1st solution for KDD Cup 2020 (RL track). https://github.com/maybeluo/KDDCup2020-RL-1st-solution

[14]

Fanyou Wu and Yang Liu. 2020. 1st solution for KDD Cup 2020 (RL track). https://wufanyou.github.io/assets/pdf/kdd-cup-2020-rl-solution.pdf

[15]

Zhe Xu, Zhixin Li, Qingwen Guan, Dingshui Zhang, Qiang Li, Junxiao Nan, Chunyang Liu, Wei Bian, and Jieping Ye. 2018. Large-Scale Order Dispatch in On-Demand Ride-Hailing Platforms: A Learning and Planning Approach. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD '18). 905--913.

Digital Library

[16]

Cheng Zeng and Nir Oren. 2014. Dynamic taxi pricing. Frontiers in Artificial Intelligence and Applications, Vol. 263 (01 2014), 1135--1136.

Cited By

Schmidt CGammelli DPereira FRodrigues F(2024)Learning to Control Autonomous Fleets from Observation via Offline Reinforcement Learning2024 European Control Conference (ECC)10.23919/ECC64448.2024.10590895(1399-1406)Online publication date: 25-Jun-2024
https://doi.org/10.23919/ECC64448.2024.10590895
Zheng YHao QWang JGao CChen JJin DLi Y(2024)A Survey of Machine Learning for Urban Decision Making: Applications in Planning, Transportation, and HealthcareACM Computing Surveys10.1145/369598657:4(1-41)Online publication date: 22-Nov-2024
https://dl.acm.org/doi/10.1145/3695986
Yue XLiu YShi FLuo SZhong CLu MXu ZSerra ESpezzano F(2024)An End-to-End Reinforcement Learning Based Approach for Micro-View Order-Dispatching in Ride-HailingProceedings of the 33rd ACM International Conference on Information and Knowledge Management10.1145/3627673.3680013(5054-5061)Online publication date: 21-Oct-2024
https://dl.acm.org/doi/10.1145/3627673.3680013
Show More Cited By

Index Terms

Recommendations

Understanding Safety Concerns and Protection Behaviors of Rideshare Drivers
SIGMIS-CPR '19: Proceedings of the 2019 on Computers and People Research Conference

Rideshare drivers provide rides for strangers and are exposed to safety-related issues as much as passengers. We used a qualitative research approach to understand the safety concerns of rideshare drivers. The questions investigated were: What makes ...
Balancing the Tradeoff between Profit and Fairness in Rideshare Platforms during High-Demand Hours
AIES '20: Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society

Rideshare platforms, when assigning requests to drivers, tend to maximize profit for the system and/or minimize waiting time for riders. Such platforms can exacerbate biases that drivers may have over certain types of requests. We consider the case of ...
Individual and Collaborative Behaviors of Rideshare Drivers in Protecting their Safety

The safety of passengers of rideshare apps has received attention from researchers, yet there is a lack of research on safety of rideshare drivers in the context of CSCW and HCI. As drivers are also an important user in the ecosystem of the ridesharing ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

KDD '22: Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

August 2022

5033 pages

ISBN:9781450393850

DOI:10.1145/3534678

General Chairs:
Aidong Zhang
University of Virginia
,
Huzefa Rangwala
Amazon/George Mason University

Copyright © 2022 Owner/Author.

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives International 4.0 License.

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 August 2022

Check for updates

Author Tags

Qualifiers

Research-article

Conference

KDD '22

Sponsor:

KDD '22: The 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

August 14 - 18, 2022

Washington DC, USA

Acceptance Rates

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Upcoming Conference

KDD '25

Sponsor:
sigkdd
sigkdd

The 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining

August 3 - 7, 2025

Toronto , ON , Canada

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
1,623
Total Downloads

Downloads (Last 12 months)623
Downloads (Last 6 weeks)38

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Schmidt CGammelli DPereira FRodrigues F(2024)Learning to Control Autonomous Fleets from Observation via Offline Reinforcement Learning2024 European Control Conference (ECC)10.23919/ECC64448.2024.10590895(1399-1406)Online publication date: 25-Jun-2024
https://doi.org/10.23919/ECC64448.2024.10590895
Zheng YHao QWang JGao CChen JJin DLi Y(2024)A Survey of Machine Learning for Urban Decision Making: Applications in Planning, Transportation, and HealthcareACM Computing Surveys10.1145/369598657:4(1-41)Online publication date: 22-Nov-2024
https://dl.acm.org/doi/10.1145/3695986
Yue XLiu YShi FLuo SZhong CLu MXu ZSerra ESpezzano F(2024)An End-to-End Reinforcement Learning Based Approach for Micro-View Order-Dispatching in Ride-HailingProceedings of the 33rd ACM International Conference on Information and Knowledge Management10.1145/3627673.3680013(5054-5061)Online publication date: 21-Oct-2024
https://dl.acm.org/doi/10.1145/3627673.3680013
Ge SZhou XQiu T(2024)MADRL-based Order Dispatching in MoD Systems with Bipartite Graph SplittingIEEE Transactions on Services Computing10.1109/TSC.2024.3495538(1-14)Online publication date: 2024
https://doi.org/10.1109/TSC.2024.3495538
Ge SZhou XQiu TWu GWang X(2024)Towards Supply-Demand Equilibrium With Ridesharing: An Elastic Order Dispatching Algorithm in MoD SystemIEEE Transactions on Mobile Computing10.1109/TMC.2023.330309023:5(5229-5244)Online publication date: May-2024
https://doi.org/10.1109/TMC.2023.3303090
Zhang ZYang LYao JMa CWang J(2024)Joint Optimization of Pricing, Dispatching and Repositioning in Ride-Hailing With Multiple Models Interplayed Reinforcement LearningIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.346456336:12(8593-8606)Online publication date: Dec-2024
https://doi.org/10.1109/TKDE.2024.3464563
Sun JJin HYang ZSu L(2024)Optimizing Long-Term Efficiency and Fairness in Ride-Hailing Under Budget Constraint via Joint Order Dispatching and Driver RepositioningIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.334849136:7(3348-3362)Online publication date: Jul-2024
https://doi.org/10.1109/TKDE.2023.3348491
Chin AQin ZDamiani MRenz MEldawy AKröger PNascimento M(2023)A Unified Representation Framework for Rideshare Marketplace Equilibrium and EfficiencyProceedings of the 31st ACM International Conference on Advances in Geographic Information Systems10.1145/3589132.3625581(1-11)Online publication date: 13-Nov-2023
https://dl.acm.org/doi/10.1145/3589132.3625581

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents