  Parking pressure has been steadily increasing in cities as well as in
university and corporate campuses. To relieve this pressure, this paper studies
a car-pooling platform that would match riders and drivers, while guaranteeing
a ride back and exploiting spatial and temporal locality. In particular, the
paper formalizes the Commute Trip Sharing Problem (CTSP) to find a routing plan
that maximizes ride sharing for a set of commute trips. The CTSP is a
generalization of the vehicle routing problem with routes that satisfy time
window, capacity, pairing, precedence, ride duration, and driver constraints.
The paper introduces two exact algorithms for the CTPS: A route-enumeration
algorithm and a branch-and-price algorithm. Experimental results show that, on
a high-fidelity, real-world dataset of commute trips from a mid-size city, both
algorithms optimally solve small and medium-sized problems and produce
high-quality solutions for larger problem instances. The results show that car
pooling, if widely adopted, has the potential to reduce vehicle usage by up to
57% and decrease vehicle miles traveled by up to 46% while only incurring a 22%
increase in average ride time per commuter for the trips considered.
