Design and operation of efficient and budget-balanced shared-use mobility systems

Abstract

Traffic congestion has become a serious issue around the globe, partly owing to single-occupancy commuter trips. Ridesharing can present a suitable alternative for serving commuter trips. However, there are several important obstacles that impede ridesharing systems from becoming a viable mode of transportation, including the lack of a guarantee for a ride back home as well as the difficulty of obtaining a critical mass of participants. This paper addresses these obstacles by introducing a Traveler Incentive Program (TIP) to promote community-based ridesharing with a ride-back home guarantee among commuters. The TIP program allocates incentives to (1) directly subsidize a select set of ridesharing rides, and (2) encourage a few, carefully selected set of travelers to change their travel behavior (i.e., departure or arrival times). We formulate the underlying ride-matching problem as a budget-constrained min-cost flow problem, and present a Lagrangian Relaxation-based algorithm with a worst-case optimality bound to solve large-scale instances of this problem in polynomial time. We further propose a polynomial-time budget-balanced version of the problem. Numerical experiments suggest that allocating subsidies to change travel behavior is significantly more beneficial than directly subsidizing rides. Furthermore, using a flat tax rate as low as 1\% can double the system's social welfare in the budget-balanced variant of the incentive program.