Cited By
View all- Chang MChi YDing ZTian JZheng Y(2021)A Continuous Taxi Pickup Path Recommendation under The Carbon Neutrality ContextISPRS International Journal of Geo-Information10.3390/ijgi1012082110:12(821)Online publication date: 4-Dec-2021
dFDA-VeD: A Dynamic Future Demand Aware Vehicle Dispatching System
Authors: 
Yang Guo, Tarique Anwar, 
jian yang, Jia WuAuthors Info & Claims
Pages 366 - 375
Abstract
With the rising demand of smart mobility, ride-hailing service is getting popular in the urban regions. These services maintain a system for serving the incoming trip requests by dispatching available vehicles to the pickup points. As the process should be socially and economically profitable, the task of vehicle dispatching is highly challenging, specially due to the time-varying travel demands and traffic conditions. Due to the uneven distribution of travel demands, many idle vehicles could be generated during the operation in different subareas. Most of the existing works on vehicle dispatching system, designed static relocation centers to relocate idle vehicles. However, as traffic conditions and demand distribution dynamically change over time, the static solution can not fit the evolving situations. In this paper, we propose a dynamic future demand aware vehicle dispatching system. It can dynamically search the relocation centers considering both travel demand and traffic conditions. We evaluate the system on real-world dataset, and compare with the existing state-of-the-art methods in our experiments in terms of several standard evaluation metrics and operation time. Through our experiments, we demonstrate that the proposed system significantly improves the serving ratio and with a very small increase in operation cost.
References
[1]
Abubakr O Al-Abbasi, Arnob Ghosh, and Vaneet Aggarwal. 2019. Deeppool: Distributed model-free algorithm for ride-sharing using deep reinforcement learning. IEEE Transactions on Intelligent Transportation Systems 20, 12(2019), 4714–4727.
[2]
Shanzhi Chen, Jinling Hu, Yan Shi, Ying Peng, Jiayi Fang, Rui Zhao, and Li Zhao. 2017. Vehicle-to-everything (V2X) services supported by LTE-based systems and 5G. IEEE Communications Standards Magazine 1, 2 (2017), 70–76.
[3]
Florian Dandl and Klaus Bogenberger. 2018. Comparing future autonomous electric taxis with an existing free-floating carsharing system. IEEE T-ITS 20, 6 (2018), 2037–2047.
[4]
George B Dantzig and John H Ramser. 1959. The truck dispatching problem. Management science 6, 1 (1959), 80–91.
[5]
Yang Guo, Weiliang Zhao, Jian Yang, Zizhu Zhang, Jia Wu, and Anwar Tarique. 2020. FDA-VeD: A Future-Demand-Aware Vehicle Dispatching Service. In 2020 IEEE International Conference on Services Computing (SCC). IEEE.
[6]
J. Holler, R. Vuorio, Z. Qin, X. Tang, Y. Jiao, T. Jin, S. Singh, C. Wang, and J. Ye. 2019. Deep Reinforcement Learning for Multi-driver Vehicle Dispatching and Repositioning Problem. In 2019 IEEE International Conference on Data Mining (ICDM). 1090–1095.
[7]
John E. Hopcroft and Richard M. Karp. 1973. An n5/2 Algorithm for Maximum Matchings in Bipartite Graphs. SIAM J. Comput. 2, 4 (1973), 225–231.
[8]
Xin Jin and Jiawei Han. 2010. K-Medoids Clustering. Springer US, Boston, MA, 564–565. https://doi.org/10.1007/978-0-387-30164-8_426
[9]
Leonard Kaufman and Peter J Rousseeuw. 2009. Finding groups in data: an introduction to cluster analysis. Vol. 344. John Wiley & Sons.
[10]
Beomjun Kim, Jeongho Kim, Subin Huh, Seungil You, and Insoon Yang. 2020. Multi-Objective Predictive Taxi Dispatch via Network Flow Optimization. IEEE Access 8(2020), 21437–21452.
[11]
Wouter Kool, Herke Van Hoof, and Max Welling. 2018. Attention, learn to solve routing problems!arXiv preprint arXiv:1803.08475(2018).
[12]
Yexin Li, Yu Zheng, and Qiang Yang. 2018. Dynamic bike reposition: A spatio-temporal reinforcement learning approach. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 1724–1733.
[13]
Frank Lin and William W. Cohen. 2010. Power Iteration Clustering. In Proceedings of the 27th International Conference on International Conference on Machine Learning (Haifa, Israel) (ICML’10). Omnipress, Madison, WI, USA, 655–662.
[14]
Yifang Liu, Will Skinner, and Chongyuan Xiang. 2019. Globally-optimized realtime supply-demand matching in on-demand ridesharing. In The World Wide Web Conference. 3034–3040.
[15]
Zhidan Liu, Zengyang Gong, Jiangzhou Li, and Kaishun Wu. 2020. Mobility-Aware Dynamic Taxi Ridesharing. In 2020 IEEE 36th International Conference on Data Engineering (ICDE). IEEE, 961–972.
[16]
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, 2015. Human-level control through deep reinforcement learning. Nature 518, 7540 (2015), 529–533.
[17]
Hae-Sang Park and Chi-Hyuck Jun. 2009. A simple and fast algorithm for K-medoids clustering. Expert systems with applications 36, 2 (2009), 3336–3341.
[18]
David Pisinger and Stefan Ropke. 2007. A general heuristic for vehicle routing problems. Computers & operations research 34, 8 (2007), 2403–2435.
[19]
Erich Schubert and Peter J Rousseeuw. 2019. Faster k-Medoids clustering: improving the PAM, CLARA, and CLARANS algorithms. In International Conference on Similarity Search and Applications. Springer, 171–187.
[20]
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. 2017. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347(2017).
[21]
Xiaocheng Tang, Zhiwei Qin, Fan Zhang, Zhaodong Wang, Zhe Xu, Yintai Ma, Hongtu Zhu, and Jieping Ye. 2019. A deep value-network based approach for multi-driver order dispatching. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining. 1780–1790.
[22]
Paolo Toth and Daniele Vigo. 2002. The vehicle routing problem. SIAM.
[23]
M. M. Vazifeh, P. Santi, G. Resta, S. H. Strogatz, and C. Ratti. 2018. Addressing the minimum fleet problem in on-demand urban mobility. Nature 557, 7706 (2018), 534–538.
[24]
Mikhail Volkov, Javed Aslam, and Daniela Rus. 2012. Markov-based redistribution policy model for future urban mobility networks. In 2012 15th International IEEE Conference on Intelligent Transportation Systems. IEEE, 1906–1911.
[25]
Ulrike Von Luxburg. 2007. A tutorial on spectral clustering. Statistics and computing 17, 4 (2007), 395–416.
[26]
Alex Wallar, Menno Van Der Zee, Javier Alonso-Mora, and Daniela Rus. 2018. Vehicle Rebalancing for Mobility-on-Demand Systems with Ride-Sharing. In IEEE/RSJ IROS. 4539–4546.
[27]
Hai Wang and Hai Yang. 2019. Ridesourcing systems: A framework and review. Transportation Research Part B: Methodological 129 (2019), 122–155.
Recommendations
A robust deep reinforcement learning approach to driverless taxi dispatching under uncertain demand
AbstractWith the progressive technological advancement of autonomous vehicles, taxi service providers are expected to offer driverless taxi systems that alleviate traffic congestion and pollution. However, it is challenging to maintain the ...
Graphical abstractHighlights- A novel RL model integrated with robust optimization is proposed to control driverless taxi fleets under uncertainty.
Spatio-Temporal Capsule-based Reinforcement Learning for Mobility-on-Demand Network Coordination
WWW '19: The World Wide Web ConferenceAs an alternative means of convenient and smart transportation, mobility-on-demand (MOD), typified by online ride-sharing and connected taxicabs, has been rapidly growing and spreading worldwide. The large volume of complex traffic and the uncertainty of ...
Spatio-temporal Adaptive Pricing for Balancing Mobility-on-Demand Networks
Survey Papers and Regular PapersPricing in mobility-on-demand (MOD) networks, such as Uber, Lyft, and connected taxicabs, is done adaptively by leveraging the price responsiveness of drivers (supplies) and passengers (demands) to achieve such goals as maximizing drivers’ incomes, ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
December 2020
493 pages
ISBN:9781450388405
DOI:10.1145/3448891
Copyright © 2020 ACM.
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 ACM 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: 09 August 2021
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Conference
MobiQuitous '20
Acceptance Rates
Overall Acceptance Rate 26 of 87 submissions, 30%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 72Total Downloads
- Downloads (Last 12 months)11
- Downloads (Last 6 weeks)0
Reflects downloads up to 21 Nov 2024
Other Metrics
Citations
Cited By
View all- Chang MChi YDing ZTian JZheng Y(2021)A Continuous Taxi Pickup Path Recommendation under The Carbon Neutrality ContextISPRS International Journal of Geo-Information10.3390/ijgi1012082110:12(821)Online publication date: 4-Dec-2021
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML Format