  This paper studies the benefits of autonomous vehicles in ride-sharing
platforms dedicated to serving commuting needs. It considers the Commute Trip
Sharing Problem with Autonomous Vehicles (CTSPAV), the optimization problem
faced by a reservation-based platform that receives daily commute-trip requests
and serves them with a fleet of autonomous vehicles. The CTSPAV can be viewed
as a special case of the Dial- A-Ride Problem (DARP). However, this paper
recognizes that commuting trips exhibit special spatial and temporal properties
that can be exploited in a branch and cut algorithm that leverages a redundant
modeling approach. In particular, the branch and cut algorithm relies on a MIP
formulation that schedules mini routes representing inbound or outbound trips.
This formulation is effective in finding high-quality solutions quickly but its
relaxation is relatively weak. To remedy this limitation, the mini-route MIP is
complemented by a DARP formulation which is not as effective in obtaining
primal solutions but has a stronger relaxation. The benefits of the proposed
approach are demonstrated by comparing it with another, more traditional, exact
branch and cut procedure and a heuristic method based on mini routes.
  The methodological contribution is complemented by a comprehensive analysis
of a CTSPAV platform for reducing vehicle counts, travel distances, and
congestion. In particular, the case study for a medium-sized city reveals that
a CTSPAV platform can reduce daily vehicle counts by a staggering 92% and
decrease vehicles miles by 30%. The platform also significantly reduces
congestion, measured as the number of vehicles on the road per unit time, by
60% during peak times. These benefits, however, come at the expense of
introducing empty miles. Hence the paper also highlights the tradeoffs between
future ride-sharing and car-pooling platforms.
