Fair and Efficient Ridesharing: A Dynamic Programming-based Relocation Approach
Article No.: 105, Pages 1 - 30
Abstract
Recommending routes by their probability of having a rider has long been the goal of conventional route recommendation systems. While this maximizes the platform-specific criteria of efficiency, it results in sub-optimal outcomes with the disparity among the income of drivers who work for similar time frames. Pioneer studies on fairness in ridesharing platforms have focused on algorithms that match drivers and riders. However, these studies do not consider the time schedules of different riders sharing a ride in the ridesharing mode. To overcome this shortcoming, we present the first route recommendation system for ridesharing networks that explicitly considers fairness as an evaluation criterion. In particular, we design a routing mechanism that reduces the inequality among drivers and provides them with routes that have a similar probability of finding riders over a period of time. However, while optimizing fairness the efficiency of the platform should not be affected as both of these goals are important for the long-term sustainability of the system. In order to jointly optimize fairness and efficiency we consider repositioning drivers with low income to the areas that have a higher probability of finding riders in future. While applying driver repositioning, we design a future-aware policy and allocate the areas to the drivers considering the destination of requests in the corresponding area. Extensive simulations on real-world datasets of Washington DC and New York demonstrate superior performance by our proposed system in comparison to the existing baselines.
References
[1]
Lu Chen, Qilu Zhong, Xiaokui Xiao, Yunjun Gao, Pengfei Jin, and Christian S. Jensen. 2018. Price-and-time-aware dynamic ridesharing. In Proceedings of the IEEE 34th International Conference on Data Engineering (ICDE ’18). IEEE, 1061–1072.
[2]
Zhao Chen, Peng Cheng, Lei Chen, Xuemin Lin, and Cyrus Shahabi. 2020. Fair task assignment in spatial crowdsourcing. Proceedings of the VLDB Endowment 13, 12 (2020), 2479–2492.
[3]
Peng Cheng, Hao Xin, and Lei Chen. 2017. Utility-aware ridesharing on road networks. In Proceedings of the 2017 ACM International Conference on Management of Data. 1197–1210.
[4]
Guang Dai, Jianbin Huang, Stephen Manko Wambura, and Heli Sun. 2017. A balanced assignment mechanism for online taxi recommendation. In Proceedings of the 18th IEEE International Conference on Mobile Data Management (MDM ’17). 102–111.
[5]
Nandani Garg and Sayan Ranu. 2018. Route recommendations for idle taxi drivers: find me the shortest route to a customer! In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD ’18). ACM, New York, NY, 1425–1434.
[6]
Nixie S. Lesmana, Xuan Zhang, and Xiaohui Bei. 2019. Balancing efficiency and fairness in on-demand ridesourcing. Proceedings of the Advances in Neural Information Processing Systems, Vol. 32. 5310–5320.
[7]
Yafei Li, Huiling Li, Xin Huang, Jianliang Xu, Yu Han, and Mingliang Xu. 2022. Utility-aware dynamic ridesharing in spatial crowdsourcing. IEEE Transactions on Mobile Computing 23, 2 (2022), 1066–1079.
[8]
Yafei Li, Huiling Li, Baolong Mei, Xin Huang, Jianliang Xu, and Mingliang Xu. 2023. Fairness-guaranteed task assignment for crowdsourced mobility services. IEEE Transactions on Mobile Computing 23, 5 (2023), 5385–5400.
[9]
Yafei Li, Ji Wan, Rui Chen, Jianliang Xu, Xiaoyi Fu, Hongyan Gu, Pei Lv, and Mingliang Xu. 2019. Top-\(k\) k vehicle matching in social ridesharing: A price-aware approach. IEEE Transactions on Knowledge and Data Engineering 33, 3 (2019), 1251–1263.
[10]
Aqsa Ashraf Makhdomi and Iqra Altaf Gillani. 2023a. GNN-based passenger request prediction. Transportation Letters (2023). https://doi.org/10.1080/19427867.2023.2283949
[11]
Aqsa Ashraf Makhdomi and Iqra Altaf Gillani. 2023b. A greedy approach for increased vehicle utilization in ridesharing networks. Expert Systems with Applications 225 (2024), 124670.
[12]
Aqsa Ashraf Makhdomi and Iqra Altaf Gillani. 2023c. Towards a greener and fairer transportation system: A survey of route recommendation techniques. ACM Transactions on Intelligent Systems and Technology 15, 1 (2023). 2157–6904
[13]
The News Minute. 2021. Ola, Uber Score Lowest on Fairness Scale Report, Flipkart Highest. Retrieved from https://www.thenewsminute.com/article/ola-uber-score-lowest-fairness-scale-report-flipkart-highest-159303
[14]
Masato Ota, Yuko Sakurai, Mingyu Guo, and Itsuki Noda. 2022. Mitigating fairness and efficiency tradeoff in vehicle-dispatch problems. In Proceedings of the International Conference on Practical Applications of Agents and Multi-Agent Systems. Springer, 307–319.
[15]
Shiyou Qian, Jian Cao, Frédéric Le Mouël, Issam Sahel, and Minglu Li. 2015. SCRAM: A sharing considered route assignment mechanism for fair taxi route recommendations. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ’15). ACM, New York, NY, 955–964.
[16]
Boting Qu, Wenxin Yang, Ge Cui, and Xin Wang. 2020. Profitable taxi travel route recommendation based on big taxi trajectory data. IEEE Transactions on Intelligent Transportation Systems 21, 2 (2020), 653–668.
[17]
Huigui Rong, Qun Zhang, Xun Zhou, Hongbo Jiang, Da Cao, and Keqin Li. 2020. TESLA: A centralized taxi dispatching approach to optimizing revenue efficiency with global fairness. In Proceedings of the KDD Workshop on Urban Computing (UrbComp ’20).
[18]
Maximilian Schreieck, Hazem Safetli, Sajjad Ali Siddiqui, Christoph Pflügler, Manuel Wiesche, and Helmut Krcmar. 2016. A matching algorithm for dynamic ridesharing. Transportation Research Procedia 19 (2016), 272–285.
[19]
Robert Sedgewick and Kevin Wayne. 2011. Algorithms (4th ed.). Addison Wesley Professional.
[20]
Dingyuan Shi, Yongxin Tong, Zimu Zhou, Bingchen Song, Weifeng Lv, and Qiang Yang. 2021. Learning to assign: Towards fair task assignment in large-scale ride hailing. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining (KDD ’21). ACM, New York, NY, 3549–3557.
[21]
Business Standard. 2022. Uber Brings Back Carpooling Service under New Name ‘UberX Share’ in US. Retrieved from https://www.business-standard.com/article/international/uber-brings-back-carpooling-service-under-new-name-uberx-share-in-us-122062200650_1.html
[22]
Jiahui Sun, Haiming Jin, Zhaoxing Yang, Lu Su, and Xinbing Wang. 2022. Optimizing long-term efficiency and fairness in ride-hailing via joint order dispatching and driver repositioning. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 3950–3960.
[23]
Na Ta, Guoliang Li, Tianyu Zhao, Jianhua Feng, Hanchao Ma, and Zhiguo Gong. 2018. An efficient ride-sharing framework for maximizing shared route. IEEE Transactions on Knowledge and Data Engineering 30, 2 (2018), 219–233.
[24]
Yongxin Tong, Libin Wang, Zhou Zimu, Bolin Ding, Lei Chen, Jieping Ye, and Ke Xu. 2017. Flexible online task assignment in real-time spatial data. Proceedings of the VLDB Endowment 10, 11 (2017), 1334–1345.
[25]
Yongxin Tong, Yuxiang Zeng, Zimu Zhou, Lei Chen, and Ke Xu. 2022. Unified route planning for shared mobility: An insertion-based framework. ACM Transactions on Database Systems 47, 1, Article 2 (2022), 48 pages.
[26]
Jiachuan Wang, Peng Cheng, Libin Zheng, Chao Feng, Lei Chen, Xuemin Lin, and Zheng Wang. 2020. Demand-aware route planning for shared mobility services. Proceedings of the VLDB Endowment 13, 7 (2020), 979–991.
[27]
Benwei Wu, Kai Han, and Enpei Zhang. 2023. On the task assignment with group fairness for spatial crowdsourcing. Information Processing & Management 60, 2 (2023), 103175.
[28]
Chak Fai Yuen, Abhishek Pratap Singh, Sagar Goyal, Sayan Ranu, and Amitabha Bagchi. 2019. Beyond shortest paths: Route recommendations for ride-sharing. In Proceedings of the World Wide Web Conference (WWW ’19). ACM, New York, NY, 2258–2269.
[29]
Yan Zhao, Kai Zheng, Ziwei Wang, Liwei Deng, Bin Yang, Torben Bach Pedersen, Christian S Jensen, and Xiaofang Zhou. 2023. Coalition-based task assignment with priority-aware fairness in spatial crowdsourcing. The VLDB Journal (2023), 1–22.
[30]
Stephen M. Zoepf, Stella Chen, Paa Adu, and Gonzalo Pozo. 2018. The economics of ride-hailing: Driver revenue, expenses and taxes. CEEPR WP 5, 2018 (2018), 1–38.
Index Terms
- Fair and Efficient Ridesharing: A Dynamic Programming-based Relocation Approach
Recommendations
Fair and efficient route recommendation system for ridesharing platforms
CODS-COMAD '24: Proceedings of the 7th Joint International Conference on Data Science & Management of Data (11th ACM IKDD CODS and 29th COMAD)In the realm of ride-hailing platforms, the ability to anticipate passenger demand in various regions and suggest routes with the highest demand to drivers plays a pivotal role. While this mechanism optimizes system efficiency, it causes income disparity ...
A greedy approach for increased vehicle utilization in ridesharing platforms
AbstractRidesharing platforms provide an eco-friendly transportation system by enabling multiple passengers to share a single vehicle. However, the existing approaches, in this direction do not utilize the vehicle capacity efficiently. These approaches ...
Real-Time City-Scale Taxi Ridesharing
We proposed and developed a taxi-sharing system that accepts taxi passengers' real-time ride requests sent from smart phones and schedules proper taxis to pick up them via ride sharing, subject to time, capacity, and monetary constraints. The monetary ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 08 November 2024
Online AM: 29 June 2024
Accepted: 02 June 2024
Revised: 20 February 2024
Received: 18 April 2023
Published in TIST Volume 15, Issue 5
Check for updates
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 198Total Downloads
- Downloads (Last 12 months)198
- Downloads (Last 6 weeks)65
Reflects downloads up to 30 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in