ºìÐÓÊÓƵ

Topic

Fast Trips: A Scalable Insertion Operator Approach for Ridesharing over Time-Dependent Road Networks

Department of Computer Science

Date & location

• Wednesday, April 23, 2025

• 12:00 P.M.

• Engineering Computer Science Building

• Room 468 and Virtual

Reviewers

Supervisory Committee

• Dr. Sean Chester, Department of Computer Science, University of Victoria (Co-Supervisor)

• Dr. Mario Nascimento, Department of Computer Science, UVic (Co-Supervisor) 

External Examiner

• Dr. Lin Cai, Department of Electrical and Computer Engineering, University of Victoria 

Chair of Oral Examination

• Dr. Timothy Iles, School of Pacific and Asian Studies, UVic

   

Abstract

Effective Route planning for shared mobility (RPSM) is crucial for optimizing the goals of transportation services such as ridesharing, logistics, and food delivery. Route planning requires dynamically integrating new transportation requests into existing routes of transportation workers while accounting for real-world conditions such as traffic congestion, variable travel speeds, and changing demand patterns. A core component of dynamic route-planning systems is the insertion operator, a state-of-the-art method that integrates new transportation requests into existing worker routes with minimal additional travel time. Although effective and fast for route-planning simulations on static road networks, route-planning simulations experience significant performance degradation when applied to real world, time-dependent road networks (TDRNs), where travel times between roads fluctuate due to varying traffic conditions. This thesis addresses the scalability challenge by introducing an informed approach to partitioning the data used by the insertion operator into separate, disjoint batches. I propose a clustering method utilizing K-means clustering complemented by an opportunistic allocation of workers to clusters. This strategy reduces the large number of shortest path query invocations inherent to time dependent insertions, significantly decreasing RPSM simulation speeds without sacrificing, and in some cases even improving the quality of the solutions. Through extensive experimental evaluations using large-scale, real-world datasets from major Chinese cities, the proposed method is compared against the sequential time-dependent insertion operator. The results indicate a minimum of 7X acceleration in RPSM simulation times, with potential speedups up to 24X, while consistently matching or surpassing the original insertion operator in the solution quality. Furthermore, the flexibility of the clustering approach allows for customizable trade-offs between simulation speed and service quality, ensuring adaptability to diverse operational goals of transportation services. Ultimately, this thesis contributes a scalable, adaptable, and computationally efficient insertion operator framework capable of handling realistic scenarios in dynamic shared mobility environments, providing valuable tools for transportation and logistics companies seeking operational optimization.