An Integrated Decomposition and Approximate Dynamic Programming Approach for On-Demand Ride Pooling

Through smartphone apps, drivers and passengers can dynamically enter and leave ride-hailing platforms. As a result, ride-pooling is challenging due to complex system dynamics and different objectives of multiple stakeholders. In this paper, the authors study ride-pooling with no more than two passenger groups who can share rides in the same vehicle. They dynamically match available drivers to randomly arriving passengers and also decide pick-up and drop-off routes. The goal is to minimize a weighted sum of passengers’ waiting time and trip delay time. A spatial-and-temporal decomposition heuristic is applied and each subproblem is solved using Approximate Dynamic Programming (ADP), for which they show properties of the approximated value function at each stage. Their model is benchmarked with the one that optimizes vehicle dispatch without ride-pooling and the one that matches current drivers and passengers without demand forecasting. Using test instances generated based on the New York City taxi data during one peak hour, the authors conduct computational studies and sensitivity analysis to show (i) empirical convergence of ADP, (ii) benefit of ride-pooling, and (iii) value of future supply-demand information.

• Record URL:
  http://dx.doi.org/10.1109/TITS.2019.2934423
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/oclc/41297384
• Supplemental Notes:
  • Copyright © 2020, IEEE.
• Authors:
  • Yu, Xian
  • Shen, Siqian
• Publication Date: 2020-9

Language

• English

Media Info

• Media Type: Digital/other
• Features: Figures; References; Tables;
• Pagination: pp 3811-3820
• Serial:
  • IEEE Transactions on Intelligent Transportation Systems
  • Volume: 21
  • Issue Number: 9
  • Publisher: Institute of Electrical and Electronics Engineers (IEEE)
  • ISSN: 1524-9050
  • Serial URL: http://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=6979

Subject/Index Terms

• TRT Terms: Algorithms; Dynamic programming; Mobility; Spatial analysis; Travel demand; Uncertainty
• Identifier Terms: Mobility-as-a-Service (MaaS)
• Geographic Terms: New York (New York)
• Subject Areas: Highways; Planning and Forecasting;

Filing Info

• Accession Number: 01772899
• Record Type: Publication
• Files: TLIB, TRIS
• Created Date: May 25 2021 4:22PM