Efficient Algorithms for Stochastic Ride-Pooling Assignment with Mixed Fleets

Qi Luo (), Viswanath Nagarajan (), Alexander Sundt (), Yafeng Yin (), John Vincent () and Mehrdad Shahabi ()
Additional contact information
Qi Luo: Department of Industrial Engineering, Clemson University, Clemson, South Carolina 29634
Viswanath Nagarajan: Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan 48109
Alexander Sundt: Department of Civil and Environmental Engineering, University of Michigan, Ann Arbor, Michigan 48109
Yafeng Yin: Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan 48109; Department of Civil and Environmental Engineering, University of Michigan, Ann Arbor, Michigan 48109
John Vincent: Ford Motor Company, Dearborn, Michigan 48120
Mehrdad Shahabi: Ford Motor Company, Dearborn, Michigan 48120

Transportation Science, 2023, vol. 57, issue 4, 908-936

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 / p 2 and ( e − 1 ) / ( 2 e + o ( 1 ) ) p ln p , 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.

Keywords: ride-pooling assignment problem; approximation algorithm; mixed autonomy traffic (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2021.0349 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:57:y:2023:i:4:p:908-936

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().