On September 8, METRANS, the Pacific Southwest University Transportation Center (PSR), and the University of Southern California chapter of the Institute of Transportation Engineers (USC ITE), launched the first hybrid (in-person and online) transportation research seminar of the Fall 2021 seminar series. USC ITE is a student group of engineers, planners, and thinkers who aim to reimagine transportation systems. Titled “Pathfinding for Shared Ride Vehicles: Bi-criteria pathfinding considering travel time and proximity to demand,” this event showcased the research of Dr. Michael Hyland and his research team including Dingtong Yang and Navjyoth Sarma. Dr. Michael Hyland is an Assistant Professor of Civil and Environmental Engineering (CEE) at the University of California, Irvine (UCI), where he is affiliated with the Institute of Transportation Studies (ITS). Dr. Hyland’s research interests center on modeling, design, control, and analysis of smart city transportation systems with emphasis on shared-use autonomous mobility services and urban transit networks. Dr. Hyland’s research has been funded by PSR.

Dr. Michael Hyland

Assistant Professor of Civil and Environmental Engineering (CEE) at the University of California, Irvine (UCI)

The event was the first in-person seminar hosted by METRANS since March 2020, drawing an enthusiastic crowd of private sector transportation professionals, faculty, researchers, and students at all levels of study. The session began with a formal presentation and ended with a discussion of the audience’s questions.

Dr. Hyland began by introducing key terms and definitions that would be used throughout the presentation. Dr. Hyland described the difference between mobility-on-demand (MOD) services without shared rides and shared-ride MOD services. Examples of MOD services without shared rides are UberX, conventional Lyft, and taxis where you are the only passenger in the vehicle. Shared-ride MOD are those like Uber pool, Lyft line, and Via, where you share the vehicle with strangers. A network path is the sequence of nodes/links a vehicle traverses in a road network while a vehicle route is the ordered sequence of user pick-up and drop-off locations for a vehicle.

Dr. Hyland’s shared that his research is motivated by the multitude of benefits shared-ride MOD services provide. A few of these benefits include reduced travel costs for individuals, reduced fleet size and operational costs of mobility service providers (MSPs), and a reduction in vehicle miles traveled (VMT), traffic congestion, fuel consumption, and harmful emissions. Despite these many benefits, shared-ride MOD services only make up 20% of transportation network companies' (TNC) trips and face many challenges. A few challenges include travelers’ aversion to sharing rides and the uncertainty/stochasticity present in ride-sharing such as new traveler requests, link travel times, and pickup/drop-off times.

The research study conceptualizes bi-criteria (two criteria) path-finding for shared ride MOD vehicles and develops a modeling framework for the static and dynamic bi-criteria best-path problems for shared-ride vehicles. The research then proposes a solution algorithm (i.e. operational policy) for bi-criteria path assignment and tests and validates the solution algorithm using the Anaheim, CA network. The research hypothesizes that assigning vehicles to the shortest paths between pick-up and drop-off locations may result in suboptimal fleet performance. Vehicles may incur avoidable mileage when responding to new requests since the pathfinding process does not consider future demand.

The operational process for shared-ride MOD services usually includes two to three interconnected parts. Hyland described these interconnected parts as 1) matching passengers with service vehicles; 2) routing/sequencing vehicles to pick-up/drop-off customers; and, 3) repositioning empty vehicles. Pathfinding has been largely overlooked because the philosophy to “just assign vehicles to the shortest network paths” is commonly used.

Dr. Hyland shared that the research aims to develop an efficient operational policy for shared-ride MOD services that efficiently matches new requests to vehicles, sequences traveler pick-ups and drop-offs for individual vehicles, repositions empty vehicles, and assigns vehicles to paths through a network, considering both travel time and potential future demand. The research seeks to determine whether bi-criteria pathfinding improves the operational efficiency of shared-ride MOD services and if so when shared-ride MOD vehicles should be assigned to bi-criteria paths.

Visual of bi-criteria pathfinding.

His research methodology includes five steps: 1) determine feasible traveler-vehicle pairs; 2) calculate pairwise traveler-vehicle service cost; 3) match vehicles to traveler requests; 4) reposition empty vehicles to balance supply and demand; and 5) assign vehicles to network paths. The two inputs used are traveler requests and vehicles.

Architecture overview of the methodology.

Hyland then applied his research and methodology to a case study using the Anaheim, CA network. The Anaheim network consists of 401 nodes (223 nodes with demand) and 854 links. Other inputs include varying fleet size, number of requests, reward coefficient, and three bi-criteria conditions. The three bi-criteria conditions are: 1) the vehicle has only one drop-off task remaining; 2) the vehicle has two drop-off tasks and no pick-up tasks remaining; and, 3) the vehicle has two drop-off tasks and no pick-up tasks OR the vehicle is empty and en-route to a pick-up task.

For the base case, when the fleet size was 100, the reward coefficient was 0.1, and bi-criteria condition 1 was used, the results showed that bi-criteria pathfinding is reasonably effective when the number of requests is between 300 and 1,000. This represents a moderate oversupply to moderate undersupply of vehicles, demonstrating that bi-criteria pathfinding is ineffective in extreme undersupply and oversupply cases. Further, giving large weights to reward terms does not make bi-criteria pathfinding more effective.
regarding testing conditions for bi-criteria paths, the research found that bi-criteria condition 1 outperforms conditions 2 and 3. A simple policy is better than complex ones, and employing bi-criteria pathfinding needs to be selective.

Results of the Base Case: Condition 1, Fleet Size 100, and Reward Coefficient 0.1.

Dr. Hyland wrapped up the seminar with several of his conclusions and future enhancements. Bi-criteria path usage is effective for reducing both customer waiting time and in-vehicle travel time by 3-5%. Bi-criteria pathfinding works best in cases where the supply of vehicles and demand requests are relatively balanced. Lastly, it is best to only consider bi-criteria when the vehicle is empty or has one remaining drop-off. Two future enhancements Dr. Hyland would like to apply to the research are accounting for spatial and temporal availability of vehicles when assigning vehicles to paths and optimal dispersion of vehicles through multiple bi-criterion paths, instead of assigning vehicles on the same path.

For the full video of the event, event highlights, and presentation slides, please click here.

About the Author:

Hayley Rundle is a second-year Master of Urban Planning student at the USC Price School of Public Policy, concentrating in Mobility and Transportation Planning. Hayley is interested in sustainable transportation planning to improve environmental quality, equity, and mobility for all. Hayley serves as the team leader for the METRANS Industry Engagement and contributes to the Student Research Team, summarizing cutting-edge transportation research projects and findings for the METRANS Fast Facts for Students series.