research-article

Data-driven Distributionally Robust Optimization For Vehicle Balancing of Mobility-on-Demand Systems

Authors:

Abdeltawab Hendawi,

Mohamed E Khalefa,

John A. Stankovic,

George PappasAuthors Info & Claims

ACM Transactions on Cyber-Physical Systems, Volume 5, Issue 2

Article No.: 17, Pages 1 - 27

https://doi.org/10.1145/3418287

Published: 04 January 2021 Publication History

Abstract

With the transformation to smarter cities and the development of technologies, a large amount of data is collected from sensors in real time. Services provided by ride-sharing systems such as taxis, mobility-on-demand autonomous vehicles, and bike sharing systems are popular. This paradigm provides opportunities for improving transportation systems’ performance by allocating ride-sharing vehicles toward predicted demand proactively. However, how to deal with uncertainties in the predicted demand probability distribution for improving the average system performance is still a challenging and unsolved task. Considering this problem, in this work, we develop a data-driven distributionally robust vehicle balancing method to minimize the worst-case expected cost. We design efficient algorithms for constructing uncertainty sets of demand probability distributions for different prediction methods and leverage a quad-tree dynamic region partition method for better capturing the dynamic spatial-temporal properties of the uncertain demand. We then derive an equivalent computationally tractable form for numerically solving the distributionally robust problem. We evaluate the performance of the data-driven vehicle balancing algorithm under different demand prediction and region partition methods based on four years of taxi trip data for New York City (NYC). We show that the average total idle driving distance is reduced by 30% with the distributionally robust vehicle balancing method using quad-tree dynamic region partitions, compared with vehicle balancing methods based on static region partitions without considering demand uncertainties. This is about a 60-million-mile or a 8-million-dollar cost reduction annually in NYC.

References

[1]

B. L. Smith, B. M. Williams, and R. K. Oswald. 2002. Comparison of parametric and nonparametric models for traffic flow forecasting. Transport. Res. C: Emerg. Technol. 10, 4 (2002), 303--321.

[2]

S. S. Jones, R. S. Evans, T. L. Allen, A. Thomas, P. J. Haug, S. J. Welch, and G. L. Snow. 2009. A multivariate time series approach to modeling and forecasting demand in the emergency department. J. Biomed. Inf. 42, 1 (2009), 123--139.

Digital Library

[3]

J. Gubbi, R. Buyya, S. Marusic, and M. Palaniswami. 2013. Internet of Things (IoT): A vision, architectural elements, and future directions. Fut. Gener. Comput. Syst. 29, 7 (2013), 1645--1660.

Digital Library

[4]

S. Ali, A. A. Maciejewski, H. J. Siegel, and Jong-Kook Kim. 2004. Measuring the robustness of a resource allocation. IEEE Trans. Parallel Distrib. Syst. 15, 7 (2004), 630--641.

Digital Library

[5]

Javier Alonso-Mora, Samitha Samaranayake, Alex Wallar, Emilio Frazzoli, and Daniela Rus. 2017. On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment. Proc. Natl. Acad. Sci. U.S.A. 114, 3 (2017), 462--467.

[6]

M. T. Asif, J. Dauwels, C. Y. Goh, A. Oran, E. Fathi, M. Xu, M. M. Dhanya, N. Mitrovic, and P. Jaillet. 2014. Spatiotemporal patterns in large-scale traffic speed prediction. IEEE Trans. Intell. Transport. Syst. 15, 2 (2014), 797--804.

[7]

Rajesh Krishna Balan, Khoa Xuan Nguyen, and Lingxiao Jiang. 2011. Real-time trip information service for a large taxi fleet. In Proceedings of the 9th International Conference on Mobile Systems, Applications, and Services (MobiSys’11). 99--112.

Digital Library

[8]

A. Ben-Tal and A. Nemirovski. 1998. Robust convex optimization. Math. Operat. Res. 23, 4 (1998), 769--805.

Digital Library

[9]

Dimitris Bertsimas, Vishal Bupta, and Nathan Kallus. 2018. Data-driven robust optimization. Math. Program. 167 (2018), 235--292.

Digital Library

[10]

Stephen Boyd and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press, New York, NY.

Digital Library

[11]

Efron Bradley. 1979. Bootstrap methods: Another look at the jackknife. Ann. Stat. 7, 1--26 (1979).

[12]

Ximing Chen, Fei Miao, George Pappas, and Victor Preciado. [n.d.]. Hierarchical data-driven vehicle dispatch and ride-sharing. In Proceedings of the IEEE 56th Conference on Decision and Control.

[13]

Francesco A. Cuzzola, Jose C. Geromel, and Manfred Morari. 2002. An improved approach for constrained robust model predictive control. Automatica 38, 7 (2002), 1183--1189.

Digital Library

[14]

Erick Delage and Yinyu Ye. 2010. Distributionally robust optimization under moment uncertainty with application to data-driven problems. Operat. Res. 58, 3 (2010), 595--612.

Digital Library

[15]

Brian Donovan and Daniel B. Work. 2015. Using coarse GPS data to quantify city-scale transportation system resilience to extreme events. In Proceedings of the Transportation Research Board Annual Meeting.

[16]

Raphael A. Finkel and Jon Louis Bentley. 1974. Quad trees a data structure for retrieval on composite keys. Acta Inf. 4, 1 (1974), 1--9.

Digital Library

[17]

Raghu Ganti, Mudhakar Srivatsa, and Tarek Abdelzaher. 2014. On limits of travel time predictions: Insights from a new york city case study. In Proceedings of the 2014 IEEE 34th International Conference on Distributed Computing Systems (ICDCS’14). 166--175.

Digital Library

[18]

Yanfeng Geng and C. G. Cassandras. 2014. New “Smart parking” system based on resource allocation and reservations. IEEE Trans. Intell. Transport. Syst. 14, 3 (2014), 1129--1139.

Digital Library

[19]

Joel Goh and Melvyn Sim. 2010. Distributionally robust optimization and its tractable approximations. Operat. Res. 58, 4-part-1 (2010), 902--917.

Digital Library

[20]

Donald Gross. 2008. Fundamentals of Queueing Theory. John Wiley 8 Sons.

Digital Library

[21]

Antonin Guttman. 1984. R-trees: A dynamic index structure for spatial searching. SIGMOD Rec. 14, 2 (June 1984), 47--57.

Digital Library

[22]

J. Herrera, D. Work, R. Herring, X. Ban, Q. Jacobson, and A. Bayen. 2010. Evaluation of traffic data obtained via GPS-enabled mobile phones: The Mobile Century field experiment. Transport. Res. C 18, 4 (2010), 568--583.

[23]

Lam Kiet, Krichene Walid, and Bayen Alexandre. 2016. On learning how players learn: Estimation of learning dynamics in the routing game. In Proceedings of the 7th ACM/IEEE International Conference on Cyber-Physical Systems (ICCPS’16). 1--10.

Digital Library

[24]

X. Li, M. Li, Y. Gong, X. Zhang, and J. Yin. 2016. T-DesP: Destination prediction based on big trajectory data. IEEE Trans. Intell. Transport. Syst. 17, 8 (August 2016), 2344--2354.

[25]

Lingbo Liu, Zhilin Qiu, Guanbin Li, Qing Shun Wang, Wanli Ouyang, and Liang Lin. 2019. Contextualized spatial-temporal network for taxi origin-destination demand prediction. IEEE Trans. Intell. Transport. Syst. 20, 10 (Oct. 2019), 3875--3887.

[26]

A. Lorca and A. Sun. 2015. Adaptive robust optimization with dynamic uncertainty sets for multi-period economic dispatch under significant wind. In Proceedings of the Power Energy Society General Meeting. 1--1.

[27]

J. Lv, Q. Li, Q. Sun, and X. Wang. 2018. T-CONV: A convolutional neural network for multi-scale taxi trajectory prediction. In Proceedings of the 2018 IEEE International Conference on Big Data and Smart Computing (BigComp’18). 82--89.

[28]

F. Miao, S. Han, S. Lin, and G. J. Pappas. 2015. Robust taxi dispatch under model uncertainties. In Proceedings of the 54th IEEE Conference on Decision and Control (CDC’15). 2816--2821.

[29]

Fei Miao, Shuo Han, Shan Lin, John A. Stankovic, Hua Huang, Desheng Zhang, Sirajum Munir, Tian He, and George J. Pappas. 2016. Taxi dispatch with real-time sensing data in metropolitan areas: A receding horizon control approach. IEEE Trans. Autom. Sci. Eng. 13, 2 (April 2016), 463--478.

[30]

F. Miao, S. Han, S. Lin, Q. Wang, J. A. Stankovic, A. Hendawi, D. Zhang, T. He, and G. J. Pappas. 2019. Data-driven robust taxi dispatch under demand uncertainties. IEEE Trans. Contr. Syst. Technol. 27, 1 (2019), 175--191.

[31]

L. Moreira-Matias, J. Gama, M. Ferreira, J. Mendes-Moreira, and L. Damas. 2013. Predicting taxi-passenger demand using streaming data. IEEE Trans. Intell. Transport. Syst. 14, 3 (Sept. 2013), 1393--1402.

Digital Library

[32]

Abood Mourad, Jakob Puchinger, and Chengbin Chu. 2019. A survey of models and algorithms for optimizing shared mobility. Transport. Res. B: Methodological 123 (May 2019), 323--346.

[33]

M. Naphade, G. Banavar, C. Harrison, J. Paraszczak, and R. Morris. 2011. Smarter cities and their innovation challenges. Computer 44, 6 (2011), 32--39.

Digital Library

[34]

Jürg Nievergelt, Hans Hinterberger, and Kenneth C Sevcik. 1984. The grid file: An adaptable, symmetric multikey file structure. ACM Trans. Database Syst. 9, 1 (1984), 38--71.

Digital Library

[35]

B. P. G. Van Parys, D. Kuhn, P. J. Goulart, and M. Morari. 2016. Distributionally robust control of constrained stochastic systems. IEEE Trans. Automat. Control 61, 2 (2016), 430--442.

[36]

Marco Pavone, Stephen L Smith, Emilio Frazzoli, and Daniela Rus. 2012. Robotic load balancing for mobility-on-demand systems. Int. J. Rob. Res. 31, 7 (June 2012), 839--854.

Digital Library

[37]

J. Pfrommer, J. Warrington, G. Schildbach, and M. Morari. 2014. Dynamic vehicle redistribution and online price incentives in shared mobility systems. IEEE Trans. Intell. Transport. Syst. 15, 4 (Aug. 2014), 1567--1578.

[38]

Jasper Schuijbroek, Robert Hampshire, and Willem-Jan van Hoeve. 2017. Inventory rebalancing and vehicle routing in bike sharing systems. European Journal of Operational Research 257, 3 (March 2017), 992--1004.

[39]

Wen Shen, Vahan Babushkin, Zeyar Aung, and Wei Lee Woon. 2013. An ensemble model for day-ahead electricity demand time series forecasting. In Proceedings of the 4th International Conference on Future Energy Systems (e-Energy’13). 51--62.

Digital Library

[40]

K. Spieser, S. Samaranayake, W. Gruel, and E. Frazzoli. 2016. Shared vehicle mobility-on-demand systems: A fleet operators guide to rebalancing empty vehicles. In Proceedings of the Transportation Research Board 95th Annual Meeting, Vol. 5. 100--111.

[41]

Håkan Terelius and Karl Henrik Johansson. 2015. An efficiency measure for road transportation networks with application to two case studies. In Proceedings of the IEEE Conference on Decision and Control (CDC’15). 5149--5155.

[42]

Jana Tumova, Sertac Karaman, Calin Belta, and Daniela Rus. 2016. Least-violating planning in road networks from temporal logic specifications. In Proceedings of the 7th ACM/IEEE International Conference on Cyber-Physical Systems (ICCPS’16). Article 17, 9 pages.

Digital Library

[43]

A. Wallar, M. Van Der Zee, J. Alonso-Mora, and D. Rus. 2018. Vehicle rebalancing for mobility-on-demand systems with ride-sharing. In Proceedings of the 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS’18). 4539--4546.

[44]

S. Weikl and K. Bogenberger. 2013. Relocation strategies and algorithms for free-floating car sharing systems. IEEE Intell. Transport. Syst. Mag. 5, 4 (2013), 100--111.

[45]

H. White and J. Racine. 2001. Statistical inference, the bootstrap, and neural-network modeling with application to foreign exchange rates. IEEE Trans. Neur. Netw. 12, 4 (July 2001), 657--673.

Digital Library

[46]

Huaxiu Yao, Xianfeng Tang, Hua Wei, Guanjie Zheng, Yanwei Yu, and Zhenhui Li. 2018. Modeling spatial-temporal dynamics for traffic prediction. arXiv:1803.01254. Retrieved from https://arxiv.org/abs/1803.01254.

[47]

Huaxiu Yao, Fei Wu, Jintao Ke, Xianfeng Tang, Yitian Jia, Siyu Lu, Pinghua Gong, Jieping Ye, and Zhenhui Li. 2018. Deep multi-view spatial-temporal network for taxi demand prediction. In Proceedings of the AAAI Annual Conference in Artificial Intelligence (AAAI’18).

[48]

Chenyang Yuan, Jérôme Thai, and Alexandre M. Bayen. 2016. ZUbers against ZLyfts apocalypse: An analysis framework for DoS attacks on mobility-as-a-service systems. In Proceedings of the 7th ACM/IEEE International Conference on Cyber-Physical Systems (ICCPS’16).

Digital Library

[49]

Desheng Zhang, Tian He, Shan Lin, S. Munir, and J. A. Stankovic. 2014. Dmodel: Online taxicab demand model from big sensor data in a roving sensor network. In Proceedings of the 2014 IEEE International Conference on Big Data (BigData’14). 152--159.

Digital Library

[50]

Rick Zhang and Marco Pavone. 2016. Control of robotic mobility-on-demand systems. Int. J. Rob. Res. 35, 1--3 (Jan. 2016), 186--203.

Digital Library

[51]

Rick Zhang, Federico Rossi, and Marco Pavone. 2016. Model predictive control of autonomous mobility-on-demand systems. In Proceedings of the International Conference on Robotics and Automation (ICRA’16).

Digital Library

Cited By

Wang GHe SJiang LWang SMiao FZhang FDong ZZhang D(2024)FairMove: A Data-Driven Vehicle Displacement System for Jointly Optimizing Profit Efficiency and Fairness of Electric For-Hire VehiclesIEEE Transactions on Mobile Computing10.1109/TMC.2023.332667623:6(6785-6802)Online publication date: Jun-2024
https://doi.org/10.1109/TMC.2023.3326676
Beojone CZhu PSirmatel IGeroliminis N(2024)A hierarchical control framework for vehicle repositioning in ride-hailing systemsTransportation Research Part C: Emerging Technologies10.1016/j.trc.2024.104717168(104717)Online publication date: Nov-2024
https://doi.org/10.1016/j.trc.2024.104717
Chen ZGong YYang LZhang JZhang WHe SZhang X(2023)Invariant Graph Neural Network for Out-of-Distribution NodesProceedings of the 2023 15th International Conference on Machine Learning and Computing10.1145/3587716.3587748(192-196)Online publication date: 17-Feb-2023
https://dl.acm.org/doi/10.1145/3587716.3587748
Show More Cited By

Index Terms

Data-driven Distributionally Robust Optimization For Vehicle Balancing of Mobility-on-Demand Systems

Recommendations

Data-driven distributionally robust vehicle balancing using dynamic region partitions
ICCPS '17: Proceedings of the 8th International Conference on Cyber-Physical Systems

With the transformation to smarter cities and the development of technologies, a large amount of data is collected from sensors in real-time. This paradigm provides opportunities for improving transportation systems' performance by allocating vehicles ...
Data-Driven Distributionally Robust Electric Vehicle Balancing for Autonomous Mobility-on-Demand Systems Under Demand and Supply Uncertainties
Electric vehicles (EVs) are being rapidly adopted due to their economic and societal benefits. Autonomous mobility-on-demand (AMoD) systems also embrace this trend. However, the long charging time and high recharging frequency of EVs pose challenges to ...
Robotic load balancing for mobility-on-demand systems

In this paper we develop methods for maximizing the throughput of a mobility-on-demand urban transportation system. We consider a finite group of shared vehicles, located at a set of stations. Users arrive at the stations, pickup vehicles, and drive (or ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Cyber-Physical Systems

ACM Transactions on Cyber-Physical Systems Volume 5, Issue 2

Special Issue on Time for CPS and Regular Papers

April 2021

238 pages

ISSN:2378-962X

EISSN:2378-9638

DOI:10.1145/3446669

Editor:
Tei-Wei Kuo
City University of Hong Kong and National Taiwan University, Taiwan

Issue’s Table of Contents

Copyright © 2021 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 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

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 04 January 2021

Accepted: 01 August 2020

Revised: 01 July 2020

Received: 01 January 2020

Published in TCPS Volume 5, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

NSF

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
499
Total Downloads

Downloads (Last 12 months)84
Downloads (Last 6 weeks)11

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang GHe SJiang LWang SMiao FZhang FDong ZZhang D(2024)FairMove: A Data-Driven Vehicle Displacement System for Jointly Optimizing Profit Efficiency and Fairness of Electric For-Hire VehiclesIEEE Transactions on Mobile Computing10.1109/TMC.2023.332667623:6(6785-6802)Online publication date: Jun-2024
https://doi.org/10.1109/TMC.2023.3326676
Beojone CZhu PSirmatel IGeroliminis N(2024)A hierarchical control framework for vehicle repositioning in ride-hailing systemsTransportation Research Part C: Emerging Technologies10.1016/j.trc.2024.104717168(104717)Online publication date: Nov-2024
https://doi.org/10.1016/j.trc.2024.104717
Chen ZGong YYang LZhang JZhang WHe SZhang X(2023)Invariant Graph Neural Network for Out-of-Distribution NodesProceedings of the 2023 15th International Conference on Machine Learning and Computing10.1145/3587716.3587748(192-196)Online publication date: 17-Feb-2023
https://dl.acm.org/doi/10.1145/3587716.3587748
He SZhang ZHan SPepin LWang GZhang DStankovic JMiao F(2023)Data-Driven Distributionally Robust Electric Vehicle Balancing for Autonomous Mobility-on-Demand Systems Under Demand and Supply UncertaintiesIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2023.323780424:5(5199-5215)Online publication date: 1-May-2023
https://dl.acm.org/doi/10.1109/TITS.2023.3237804
Liu WHua MDeng ZMeng ZHuang YHu CSong SGao LLiu CShuai BKhajepour AXiong LXia X(2023)A Systematic Survey of Control Techniques and Applications in Connected and Automated VehiclesIEEE Internet of Things Journal10.1109/JIOT.2023.330700210:24(21892-21916)Online publication date: 15-Dec-2023
https://doi.org/10.1109/JIOT.2023.3307002
He SWang YHan SZou SMiao F(2023)A Robust and Constrained Multi-Agent Reinforcement Learning Electric Vehicle Rebalancing Method in AMoD Systems2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)10.1109/IROS55552.2023.10342342(5637-5644)Online publication date: 1-Oct-2023
https://doi.org/10.1109/IROS55552.2023.10342342
He SHan SMiao F(2023)Robust Electric Vehicle Balancing of Autonomous Mobility-on-Demand System: A Multi-Agent Reinforcement Learning Approach2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)10.1109/IROS55552.2023.10342263(5471-5478)Online publication date: 1-Oct-2023
https://doi.org/10.1109/IROS55552.2023.10342263
Li ZYin BYao TGuo JDing SChen SLiu C(2023)Sibling-Attack: Rethinking Transferable Adversarial Attacks against Face Recognition2023 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)10.1109/CVPR52729.2023.02359(24626-24637)Online publication date: Jun-2023
https://doi.org/10.1109/CVPR52729.2023.02359
Xi H(2022)Data-driven optimization technologies for MaaSBig Data and Mobility as a Service10.1016/B978-0-323-90169-7.00006-3(143-176)Online publication date: 2022
https://doi.org/10.1016/B978-0-323-90169-7.00006-3
Li XGao JWang CHuang XNie Y(2021)Order Dispatching in Ride-Sharing Platform under Travel Time Uncertainty: A Data-Driven Robust Optimization Approach2021 IEEE International Conference on Autonomous Systems (ICAS)10.1109/ICAS49788.2021.9551160(1-7)Online publication date: 11-Aug-2021
https://doi.org/10.1109/ICAS49788.2021.9551160
Show More Cited By

View Options

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Issue’s Table of Contents