IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v284y2020i3p1088-1106.html
   My bibliography  Save this article

Approximate dynamic programming for planning a ride-hailing system using autonomous fleets of electric vehicles

Author

Listed:
  • Al-Kanj, Lina
  • Nascimento, Juliana
  • Powell, Warren B.

Abstract

We address a comprehensive ride-hailing system taking into account many of the decisions required to operate it in reality. The ride-hailing system is formed of a centrally managed fleet of autonomous electric vehicles which is creating a transformative new technology with significant cost savings. This problem involves a dispatch problem for assigning riders to cars, a surge pricing problem for deciding on the price per trip and a planning problem for deciding on the fleet size. We use approximate dynamic programming to develop high-quality operational dispatch strategies to determine which car is best for a particular trip, when a car should be recharged, when it should be re-positioned to a different zone which offers a higher density of trips and when it should be parked. These decisions have to be made in the presence of a highly dynamic call-in process, and assignments have to take into consideration the spatial and temporal patterns in trip demand which are captured using value functions. We prove that the value functions are monotone in the battery and time dimensions and use hierarchical aggregation to get better estimates of the value functions with a small number of observations. Then, surge pricing is discussed using an adaptive learning approach to decide on the price for each trip. Finally, we discuss the fleet size problem.

Suggested Citation

  • Al-Kanj, Lina & Nascimento, Juliana & Powell, Warren B., 2020. "Approximate dynamic programming for planning a ride-hailing system using autonomous fleets of electric vehicles," European Journal of Operational Research, Elsevier, vol. 284(3), pages 1088-1106.
    • Handle: RePEc:eee:ejores:v:284:y:2020:i:3:p:1088-1106
    DOI: 10.1016/j.ejor.2020.01.033
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221720300540
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2020.01.033?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Dimitris Bertsimas & Patrick Jaillet, & Sébastien Martin, 2019. "Online Vehicle Routing: The Edge of Optimization in Large-Scale Applications," Operations Research, INFORMS, vol. 67(1), pages 143-162, January.
    2. Mourad, Abood & Puchinger, Jakob & Chu, Chengbin, 2019. "A survey of models and algorithms for optimizing shared mobility," Transportation Research Part B: Methodological, Elsevier, vol. 123(C), pages 323-346.
    3. Hugo P. Simão & Jeff Day & Abraham P. George & Ted Gifford & John Nienow & Warren B. Powell, 2009. "An Approximate Dynamic Programming Algorithm for Large-Scale Fleet Management: A Case Application," Transportation Science, INFORMS, vol. 43(2), pages 178-197, May.
    4. Fagnant, Daniel J. & Kockelman, Kara, 2015. "Preparing a nation for autonomous vehicles: opportunities, barriers and policy recommendations," Transportation Research Part A: Policy and Practice, Elsevier, vol. 77(C), pages 167-181.
    5. J. Michael Harrison & N. Bora Keskin & Assaf Zeevi, 2012. "Bayesian Dynamic Pricing Policies: Learning and Earning Under a Binary Prior Distribution," Management Science, INFORMS, vol. 58(3), pages 570-586, March.
    6. Anton Braverman & J. G. Dai & Xin Liu & Lei Ying, 2019. "Empty-Car Routing in Ridesharing Systems," Operations Research, INFORMS, vol. 67(5), pages 1437-1452, September.
    7. Agatz, Niels & Erera, Alan & Savelsbergh, Martin & Wang, Xing, 2012. "Optimization for dynamic ride-sharing: A review," European Journal of Operational Research, Elsevier, vol. 223(2), pages 295-303.
    8. Boyacı, Burak & Zografos, Konstantinos G. & Geroliminis, Nikolas, 2015. "An optimization framework for the development of efficient one-way car-sharing systems," European Journal of Operational Research, Elsevier, vol. 240(3), pages 718-733.
    9. Clewlow, Regina R. & Mishra, Gouri S., 2017. "Disruptive Transportation: The Adoption, Utilization, and Impacts of Ride-Hailing in the United States," Institute of Transportation Studies, Working Paper Series qt82w2z91j, Institute of Transportation Studies, UC Davis.
    10. Sun, Luoyi & Teunter, Ruud H. & Babai, M. Zied & Hua, Guowei, 2019. "Optimal pricing for ride-sourcing platforms," European Journal of Operational Research, Elsevier, vol. 278(3), pages 783-795.
    11. Itf, 2015. "Urban Mobility System Upgrade: How shared self-driving cars could change city traffic," International Transport Forum Policy Papers 6, OECD Publishing.
    12. Loeb, Benjamin & Kockelman, Kara M., 2019. "Fleet performance and cost evaluation of a shared autonomous electric vehicle (SAEV) fleet: A case study for Austin, Texas," Transportation Research Part A: Policy and Practice, Elsevier, vol. 121(C), pages 374-385.
    13. Gregory A. Godfrey & Warren B. Powell, 2002. "An Adaptive Dynamic Programming Algorithm for Dynamic Fleet Management, I: Single Period Travel Times," Transportation Science, INFORMS, vol. 36(1), pages 21-39, February.
    14. Rodier, Caroline & Alemi, Farzad & Smith, Dylan, 2016. "Dynamic Ridesharing: Exploration of Potential for Reduction in Vehicle Miles Traveled," Institute of Transportation Studies, Working Paper Series qt6r6139g8, Institute of Transportation Studies, UC Davis.
    15. Chen, T. Donna & Kockelman, Kara M. & Hanna, Josiah P., 2016. "Operations of a shared, autonomous, electric vehicle fleet: Implications of vehicle & charging infrastructure decisions," Transportation Research Part A: Policy and Practice, Elsevier, vol. 94(C), pages 243-254.
    16. Lawrence D. Burns, 2013. "A vision of our transport future," Nature, Nature, vol. 497(7448), pages 181-182, May.
    17. Florian Dandl & Michael Hyland & Klaus Bogenberger & Hani S. Mahmassani, 2019. "Evaluating the impact of spatio-temporal demand forecast aggregation on the operational performance of shared autonomous mobility fleets," Transportation, Springer, vol. 46(6), pages 1975-1996, December.
    18. Huseyin Topaloglu & Warren B. Powell, 2006. "Dynamic-Programming Approximations for Stochastic Time-Staged Integer Multicommodity-Flow Problems," INFORMS Journal on Computing, INFORMS, vol. 18(1), pages 31-42, February.
    19. Sun, Bo & Sun, Xu & Tsang, Danny H.K. & Whitt, Ward, 2019. "Optimal battery purchasing and charging strategy at electric vehicle battery swap stations," European Journal of Operational Research, Elsevier, vol. 279(2), pages 524-539.
    20. Daniel R. Jiang & Warren B. Powell, 2015. "An Approximate Dynamic Programming Algorithm for Monotone Value Functions," Operations Research, INFORMS, vol. 63(6), pages 1489-1511, December.
    21. Li, Baoxiang & Krushinsky, Dmitry & Reijers, Hajo A. & Van Woensel, Tom, 2014. "The Share-a-Ride Problem: People and parcels sharing taxis," European Journal of Operational Research, Elsevier, vol. 238(1), pages 31-40.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. De Munck, Thomas & Chevalier, Philippe & Tancrez, Jean-Sébastien, 2023. "Managing priorities on on-demand service platforms with waiting time differentiation," International Journal of Production Economics, Elsevier, vol. 266(C).
    2. Bosse, Alexander & Ulmer, Marlin W. & Manni, Emanuele & Mattfeld, Dirk C., 2023. "Dynamic priority rules for combining on-demand passenger transportation and transportation of goods," European Journal of Operational Research, Elsevier, vol. 309(1), pages 399-408.
    3. Yan, Pengyu & Yu, Kaize & Chao, Xiuli & Chen, Zhibin, 2023. "An online reinforcement learning approach to charging and order-dispatching optimization for an e-hailing electric vehicle fleet," European Journal of Operational Research, Elsevier, vol. 310(3), pages 1218-1233.
    4. Wang, Dujuan & Wang, Qi & Yin, Yunqiang & Cheng, T.C.E., 2023. "Optimization of ride-sharing with passenger transfer via deep reinforcement learning," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 172(C).
    5. Heydar, Mojtaba & Mardaneh, Elham & Loxton, Ryan, 2022. "Approximate dynamic programming for an energy-efficient parallel machine scheduling problem," European Journal of Operational Research, Elsevier, vol. 302(1), pages 363-380.
    6. Shen, Zuo-Jun Max & Xie, Jingui & Zheng, Zhichao & Zhou, Han, 2023. "Dynamic scheduling with uncertain job types," European Journal of Operational Research, Elsevier, vol. 309(3), pages 1047-1060.
    7. Yan, Pengyu & Lee, Chung-Yee & Chu, Chengbin & Chen, Cynthia & Luo, Zhiqin, 2021. "Matching and pricing in ride-sharing: Optimality, stability, and financial sustainability," Omega, Elsevier, vol. 102(C).
    8. Jacob, Jagan & Roet-Green, Ricky, 2021. "Ride solo or pool: Designing price-service menus for a ride-sharing platform," European Journal of Operational Research, Elsevier, vol. 295(3), pages 1008-1024.
    9. Cervellera, Cristiano, 2023. "Optimized ensemble value function approximation for dynamic programming," European Journal of Operational Research, Elsevier, vol. 309(2), pages 719-730.
    10. Yu, Guodong & Liu, Aijun & Zhang, Jianghua & Sun, Huiping, 2021. "Optimal operations planning of electric autonomous vehicles via asynchronous learning in ride-hailing systems," Omega, Elsevier, vol. 103(C).
    11. Zhou, Yaqian & Yang, Hai & Ke, Jintao & Wang, Hai & Li, Xinwei, 2022. "Competition and third-party platform-integration in ride-sourcing markets," Transportation Research Part B: Methodological, Elsevier, vol. 159(C), pages 76-103.
    12. Soeffker, Ninja & Ulmer, Marlin W. & Mattfeld, Dirk C., 2022. "Stochastic dynamic vehicle routing in the light of prescriptive analytics: A review," European Journal of Operational Research, Elsevier, vol. 298(3), pages 801-820.
    13. Liu, Yang & Xie, Jiaohong & Chen, Nan, 2022. "Stochastic one-way carsharing systems with dynamic relocation incentives through preference learning," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 166(C).
    14. Nikola Mardešić & Tomislav Erdelić & Tonči Carić & Marko Đurasević, 2023. "Review of Stochastic Dynamic Vehicle Routing in the Evolving Urban Logistics Environment," Mathematics, MDPI, vol. 12(1), pages 1-44, December.
    15. Fleckenstein, David & Klein, Robert & Steinhardt, Claudius, 2023. "Recent advances in integrating demand management and vehicle routing: A methodological review," European Journal of Operational Research, Elsevier, vol. 306(2), pages 499-518.
    16. Tang, Xindi & Yang, Jie & Lin, Xi & He, Fang & Si, Jinhua, 2023. "Dynamic operations of an integrated mobility service system of fixed-route transits and flexible electric buses," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 173(C).
    17. Guo, Xiaotong & Caros, Nicholas S. & Zhao, Jinhua, 2021. "Robust matching-integrated vehicle rebalancing in ride-hailing system with uncertain demand," Transportation Research Part B: Methodological, Elsevier, vol. 150(C), pages 161-189.
    18. Meijian Yang & Enjun Xia, 2021. "A Systematic Literature Review on Pricing Strategies in the Sharing Economy," Sustainability, MDPI, vol. 13(17), pages 1-28, August.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Yu, Guodong & Liu, Aijun & Zhang, Jianghua & Sun, Huiping, 2021. "Optimal operations planning of electric autonomous vehicles via asynchronous learning in ride-hailing systems," Omega, Elsevier, vol. 103(C).
    2. Meyer, Jonas & Becker, Henrik & Bösch, Patrick M. & Axhausen, Kay W., 2017. "Autonomous vehicles: The next jump in accessibilities?," Research in Transportation Economics, Elsevier, vol. 62(C), pages 80-91.
    3. Hyland, Michael & Mahmassani, Hani S., 2020. "Operational benefits and challenges of shared-ride automated mobility-on-demand services," Transportation Research Part A: Policy and Practice, Elsevier, vol. 134(C), pages 251-270.
    4. Becker, Henrik & Becker, Felix & Abe, Ryosuke & Bekhor, Shlomo & Belgiawan, Prawira F. & Compostella, Junia & Frazzoli, Emilio & Fulton, Lewis M. & Guggisberg Bicudo, Davi & Murthy Gurumurthy, Krishna, 2020. "Impact of vehicle automation and electric propulsion on production costs for mobility services worldwide," Transportation Research Part A: Policy and Practice, Elsevier, vol. 138(C), pages 105-126.
    5. Amirmahdi Tafreshian & Neda Masoud & Yafeng Yin, 2020. "Frontiers in Service Science: Ride Matching for Peer-to-Peer Ride Sharing: A Review and Future Directions," Service Science, INFORMS, vol. 12(2-3), pages 44-60, June.
    6. Guo, Xiaotong & Caros, Nicholas S. & Zhao, Jinhua, 2021. "Robust matching-integrated vehicle rebalancing in ride-hailing system with uncertain demand," Transportation Research Part B: Methodological, Elsevier, vol. 150(C), pages 161-189.
    7. Ulmer, Marlin W. & Thomas, Barrett W., 2020. "Meso-parametric value function approximation for dynamic customer acceptances in delivery routing," European Journal of Operational Research, Elsevier, vol. 285(1), pages 183-195.
    8. Mourad, Abood & Puchinger, Jakob & Chu, Chengbin, 2019. "A survey of models and algorithms for optimizing shared mobility," Transportation Research Part B: Methodological, Elsevier, vol. 123(C), pages 323-346.
    9. Wang, Hai & Yang, Hai, 2019. "Ridesourcing systems: A framework and review," Transportation Research Part B: Methodological, Elsevier, vol. 129(C), pages 122-155.
    10. Kang, Di & Levin, Michael W., 2021. "Maximum-stability dispatch policy for shared autonomous vehicles," Transportation Research Part B: Methodological, Elsevier, vol. 148(C), pages 132-151.
    11. Tang, Zhe-Yi & Tian, Li-Jun & Wang, David Z.W., 2021. "Multi-modal morning commute with endogenous shared autonomous vehicle penetration considering parking space constraint," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 151(C).
    12. Wadud, Zia & Mattioli, Giulio, 2021. "Fully automated vehicles: A cost-based analysis of the share of ownership and mobility services, and its socio-economic determinants," Transportation Research Part A: Policy and Practice, Elsevier, vol. 151(C), pages 228-244.
    13. Enzi, Miriam & Parragh, Sophie N. & Pisinger, David & Prandtstetter, Matthias, 2021. "Modeling and solving the multimodal car- and ride-sharing problem," European Journal of Operational Research, Elsevier, vol. 293(1), pages 290-303.
    14. Rajendran, Suchithra & Srinivas, Sharan, 2020. "Air taxi service for urban mobility: A critical review of recent developments, future challenges, and opportunities," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 143(C).
    15. Mofidi, Seyed Shahab & Pazour, Jennifer A., 2019. "When is it beneficial to provide freelance suppliers with choice? A hierarchical approach for peer-to-peer logistics platforms," Transportation Research Part B: Methodological, Elsevier, vol. 126(C), pages 1-23.
    16. Iacobucci, Riccardo & McLellan, Benjamin & Tezuka, Tetsuo, 2018. "Modeling shared autonomous electric vehicles: Potential for transport and power grid integration," Energy, Elsevier, vol. 158(C), pages 148-163.
    17. Zhou, Fan & Zheng, Zuduo & Whitehead, Jake & Perrons, Robert K. & Washington, Simon & Page, Lionel, 2020. "Examining the impact of car-sharing on private vehicle ownership," Transportation Research Part A: Policy and Practice, Elsevier, vol. 138(C), pages 322-341.
    18. Warren B. Powell, 2016. "Perspectives of approximate dynamic programming," Annals of Operations Research, Springer, vol. 241(1), pages 319-356, June.
    19. Fehn, Fabian & Engelhardt, Roman & Dandl, Florian & Bogenberger, Klaus & Busch, Fritz, 2023. "Integrating parcel deliveries into a ride-pooling service—An agent-based simulation study," Transportation Research Part A: Policy and Practice, Elsevier, vol. 169(C).
    20. Martin Adler & Stefanie Peer & Tanja Sinozic, 2019. "Autonomous, Connected, Electric Shared vehicles (ACES) and public finance: an explorative analysis," Tinbergen Institute Discussion Papers 19-005/VIII, Tinbergen Institute.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:284:y:2020:i:3:p:1088-1106. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.