Ride-Sharing Optimization Algorithms for Urban Commuting

Virtual dissertation defense

ABSTRACT: As cities struggle to cope with the ever-increasing demand on their transportation infrastructures, ride-hailing services have emerged as a potential remedy that promises to revolutionize urban mobility by making on-demand transportation available at the touch of a fingertip. The long-term sustainability of these services, however, can only be realized when their rides are aggregated by having individual vehicles serve multiple trips simultaneously to maximize the utilization of available seat capacity, i.e., by “true” ride sharing. While the community has long recognized ride sharing’s potential for reducing traffic congestion, energy consumption, parking utilization, and greenhouse gas emissions, numerous unsolved challenges—from providing attractive mechanisms to incentivize modal shifts to building trust among unacquainted passengers—remain to hinder its widespread adoption.

A key obstacle to ride sharing’s ubiquity is the difficulty of coordinating rides with matching locations and schedules combined with the absence of algorithms capable of matching riders and drivers quickly and effectively. This research addresses this challenge by focusing on finding optimal routing plans for fleets of conventional and autonomous vehicles that maximize ride sharing for commute trips to power future ride-sharing platforms. The need to design routes that match trips to and from the workplace—that in turn, are dispersed spatially and temporally with schedules that may change every day—while respecting time-window, ride-duration, and vehicle-capacity constraints highlights the complexity of the problem. Driven by an original desire to investigate the potential of optimized ride-sharing platforms in relieving the parking pressure induced by the thousands of commuters traveling to the University of Michigan campus in Ann Arbor, Michigan, this research: (1) develops the mathematical framework for modeling the problem of seeking the optimal routing plan that maximizes ride sharing for commute trips for conventional and autonomous vehicles, (2) proposes techniques to decompose the problem and designs exact and approximate algorithms to tackle its computational complexity, and (3) quantifies the potential benefits and drawbacks of the generated plans and provides insight into the different factors that influence their performance through a real case study.

Aside from investigating modeling and decomposition techniques that specifically exploit the structure imposed by the problem constraints and the spatio-temporal characteristics of the trips, this research also proposes solution approaches that leverage state-of-the-art linear-programming and combinatorial-optimization techniques, ranging from column generation to discover useful routes on demand to dynamic programming to efficiently find resource-constrained least-cost paths. The solution approaches share a common characteristic: Each produces a valid lower bound to the objective value which allows the calculation of an optimality gap to quantify its solution quality. These algorithms are further bolstered by the availability of a real-world dataset of the commute trips made by 15,000 drivers that use 15 university-operated parking structures in downtown Ann Arbor over April 2017; it not only allows the algorithms to be evaluated on real-world data, but analyses of its results provide invaluable insights into the performance characteristics of the optimized routing plans. This research demonstrates that through the optimal plans, the number of vehicles for these trips can be potentially reduced by 57% and 92% when using conventional and autonomous vehicles respectively. It also quantifies numerous other potential benefits and drawbacks from utilizing the plans, some of which include reductions in vehicle usage during peak hours, decreases in vehicle miles traveled, and increases in average commute times.