Journal article
Efficient Algorithms for Stochastic Ride-Pooling Assignment with Mixed Fleets
Transportation science, Vol.57(4), pp.908-936
07/01/2023
DOI: 10.1287/trsc.2021.0349
Abstract
Ride-pooling, which accommodates multiple passenger requests in a single trip, has the potential to substantially enhance the throughput of mobility-on-demand (MoD) systems. This paper investigates MoD systems that operate mixed fleets composed of "basic supply" and "augmented supply" vehicles. When the basic supply is insufficient to satisfy demand, augmented supply vehicles can be repositioned to serve rides at a higher operational cost. We formulate the joint vehicle repositioning and ride-pooling assignment problem as a two-stage stochastic integer program, where repositioning augmented supply vehicles precedes the realization of ride requests. Sequential ride-pooling assignments aim to maximize total utility or profit on a shareability graph: a hypergraph representing the matching compatibility between available vehicles and pending requests. Two approximation algorithms for midcapacity and high-capacity vehicles are proposed in this paper; the respective approximation ratios are 1/p2 and (e � 1)/(2e + o(1))plnp, where p is the maximum vehicle capacity plus one. Our study evaluates the performance of these approximation algorithms using an MoD simulator, demonstrating that these algorithms can parallelize computations and achieve solutions with small optimality gaps (typically within 1%). These efficient algorithms pave the way for various multimodal and multiclass MoD applications.
Details
- Title: Subtitle
- Efficient Algorithms for Stochastic Ride-Pooling Assignment with Mixed Fleets
- Creators
- Qi Luo - Clemson UniversityViswanath Nagarajan - University of MichiganAlexander Sundt - University of MichiganYafeng Yin - University of MichiganJohn Vincent - Ford Motor Company (United States)Mehrdad Shahabi - Ford Motor Company (United States)
- Resource Type
- Journal article
- Publication Details
- Transportation science, Vol.57(4), pp.908-936
- DOI
- 10.1287/trsc.2021.0349
- ISSN
- 0041-1655
- eISSN
- 1526-5447
- Publisher
- Informs
- Number of pages
- 30
- Grant note
- CCF-2006778; FW-HTF-P 2222806 / National Science Foundation; National Science Foundation (NSF) CMMI-1854684; CMMI-1904575; CMMI-1940766 / Division of Civil, Mechanical, and Manufacturing Innovation; National Science Foundation (NSF); NSF - Directorate for Engineering (ENG) Ford Motor Company
- Language
- English
- Date published
- 07/01/2023
- Academic Unit
- Business Analytics
- Record Identifier
- 9984696571502771
Metrics
45 Record Views