Improving transportation efficiency with ridesharing

Due to growing population, there is a higher demand for public transit. On the other hand, public transportation systems in many cities are not able to handle all the increasing demand due to their slow development. This and the inconvenient of transit push people to use personal vehicles. Mobility-on-demand (MoD) systems, such as Uber and Lyft, have become popular around the globe for their convenience. Despite their convenience, the current use of MoD has created a negative effect on traffic, such as increasing traffic congestion. One way to improve transportation efficiency is to promote ridesharing among MoD systems since it is a promising way to increase the occupancy rate of personal vehicles and reduce traffic congestion. We study two ridesharing minimization problems: given a set of individuals, (1) assign the minimum number of individuals as drivers to serve all individuals, and (2) minimize the total travel distance of the assigned drivers to serve all individuals. We show that even restricted variants of these two problems are NP-hard (and NP-hard to approximate within a constant factor). We propose exact and approximation algorithms for restricted variants of these two problems. We also study a ridesharing maximization problem: given a set of drivers and a set of passengers, maximize the number of passengers assigned to drivers such that the total profit of drivers reaches a specified target. This problem focuses on the profitability for adopting ridesharing in practice. We give an exact and two approximation algorithms for two variants of this problem. Based on a real-world ridesharing dataset in Chicago City, profit model of Uber and practical scenarios, we create datasets for an extensive computational study on our model and algorithms. We study another optimization problem that focuses on the integration of public transit with ridesharing, which can increase transit ridership. Specifically, given a set of drivers and a set of transit riders, we assign riders to drivers such that the number of riders with shorter transit travel time (with the use of ridesharing) is maximized. We show that this problem is NP-hard, and we present an exact algorithm approach and several polynomial-time constant approximation algorithms. Based on real-world ridesharing and transit datasets in Chicago City, we conducted an extensive computational study to showcase the potential of integrating public transit with ridesharing.