The Commute Trip-Sharing Problem

Parking pressure has been steadily increasing in cities as well as on university and corporate campuses. To relieve this pressure, this paper studies a carpooling 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 CTSP: a route-enumeration algorithm and a branch-and-price algorithm. Experimental results show that on a high-fidelity real-world data set of commute trips from a midsize city, both algorithms optimally solve small and medium-sized problems and produce high-quality solutions for larger problem instances. The results show that carpooling, if widely adopted, has the potential to reduce vehicle usage by up to 57% and decrease vehicle miles traveled by up to 46% while incurring only a 22% increase in average ride time per commuter for the trips considered.