Research Projects

Stop the Video

Research Projects

STATUS: In Progress YEAR: 2019 TOPIC AREA: Connected and autonomous systems Sustainability, energy, and health CENTER: PSR

Non-myopic path-finding for shared-ride vehicles: A bi-criterion best-path approach considering travel time and proximity to demand

Project Summary

Project number: PSR-19-31
Funding source: Caltrans
Contract number: 65A0674, TO 026
Funding amount: $53,923
Start and end dates: January 1, 2020 to December 31, 2020

Project description

Shared-ride mobility-on-demand (MOD) services offered by transit agencies (e.g. flexible, demand-adaptive, and demand-responsive transit) and private companies (e.g. Uber Pool, Lyft Line, microtransit) have the potential to provide high-quality, convenient, and affordable on-demand mobility service to individual travelers, while simultaneously obtaining the societal benefits of decreased vehicle miles traveled, congestion, and vehicle emissions through increased vehicle occupancies. However, for shared-ride MOD services to capture these societal and individual mobility benefits, they need to be operated efficiently. Hence, this research project focuses on the efficient operation of shared-ride MOD services. Although several research studies, including work by the PI, address shared-ride MOD operational problems, this research project addresses a severely overlooked shared-ride MOD operational subproblem, namely, the assignment of individual shared-ride vehicles to network paths as they move between user pickup and drop-off locations. 

In practice, and in the academic literature, fleet controllers assign shared-ride vehicles (like non-shared-ride vehicles) to the shortest network path, in terms of travel time, between pickup and drop-off locations in their schedules. While this strategy/policy is intuitive, it is also myopic given the nature of shared-ride on-demand service and the (high) likelihood new users will request service as vehicles traverse network paths between pickup and drop-off locations. A non-myopic approach would anticipate the possibility of new requests and consider the proximity of network paths to future user requests (i.e. demand) when assigning shared-ride vehicles to network paths. 

The goal of this research is to support the efficient operation of shared-ride MOD services as a means to enhance mobility via developing a non-myopic algorithm to assign individual shared-ride vehicles to network paths considering proximity to future demand in addition to travel time. The PI's hypothesis is that the consideration of proximity of network paths to future demand in the controller's objective function will increase shared-ride opportunities and prevent some shared-ride vehicle detours from low-demand, high-speed areas back to high-demand, lower speed areas to pick up new requests. This should subsequently improve service quality, decrease operational costs, and decrease required fleet sizes for shared-ride MOD services. 

If assigning individual shared-ride vehicles to the shortest (travel time) paths is suboptimal, this suggests MOD fleet controllers should consider significant alterations to their operational strategies. Moreover, it suggests that the utilization of road networks may change substantially in the future if shared-ride MOD services gain significant market share relative to personal vehicles. 

Assuming this research project shows it is beneficial to route individual shared-ride vehicles, considering both travel time and proximity to demand, fleet operators should consider assigning all the vehicles in their fleet to network paths considering proximity to demand. However, the fleet operator will not want all shared-ride vehicles traveling along the same few corridors with the highest demand; this would be excessive. Rather, the fleet controller can spread individual shared-ride vehicles across the network in real-time to ‘cover' expected future demand throughout the service region, much the same way bus routes are designed, and route frequencies are set to cover expected demand throughout the service region.

Additionally, assuming this research project finds it is suboptimal for individual shared-ride vehicles to travel along shortest travel time paths, this implies the future use of road networks may change drastically if personal vehicle usage decreases and the use of shared-ride vehicles increases. Grade-separated, limited-access highways are likely to become less attractive paths as they limit sharing opportunities; whereas, main arterials cutting through or near high-density residential and business areas are likely to become more attractive paths. This leads to important planning and design questions related to infrastructure investments and curb space.

Although, these future research avenues are interesting and important, the research in this proposal represents a significant advancement in the control of shared-ride vehicles that has the potential to significantly improve mobility. The conceptualization of the problem, mathematical models, solution methods, and computational results from this project will be summarized in one or more papers that will be submitted to top-tier transportation and operations research journals, and top-tier transportation conferences. Given the potential of this project to spur future research, the research team plans to make a concerted effort to widely promote the research findings.


Michael Hyland
Assistant Professor of Civil and Environmental Engineering
The Henry Samueli School of Engineering
Institute of Transportation StudiesIrvine, CA 92697-3600
United States
[email protected]