Route Recommendation to Facilitate Carpooling

Recently ride-sharing platforms have struggled with a decreased supply of drivers, which has negatively impacted their passengers, by subjecting them to long delays and extremely high surge prices. An approach for mitigating these problems is for service providers to facilitate and coordinate carpooling via the recommendation of individually curated paths, not necessarily the shortest, for drivers towards completing their chosen rides. In this paper, we redesign the Weight Evolving Temporal graph structure to efficiently encode large dynamic road networks with temporal ride availability. Leveraging that graph structure, we efficiently define a polynomial-time optimal route recommendation algorithm that increases carpooling opportunities, taking into consideration the spatio-temporal constraints of both drivers and rides in such a highly-dynamic setting. Finally, we use simulations to demonstrate the effectiveness of these route recommendations, on both the driver and passenger experience.