Snapshot Optimal Real-time Ride Sharing

Ridesharing effectively tackles urban mobility challenges by providing a service comparable to private vehicles while minimising resource usage. Our research primarily concentrates on dynamic ridesharing, which conventionally involves connecting drivers with passengers in need of transportation. The process of one-to-one matching presents a complex challenge, particularly when addressing it on a large scale, as the substantial number of potential matches make the attainment of a global optimum a challenging endeavour. This paper aims to address the absence of an optimal approach for dynamic ridesharing by refraining from conventional heuristic-based methods, commonly used to achieve timely solutions in large-scale ride-matching. We propose a novel approach that provides snapshot optimal solutions for various forms of one-to-one matching, ensuring they are generated within an acceptable timeframe for service providers. Additionally, we introduce and solve a new variant where the system itself provides the vehicles. The efficacy of our methodology is substantiated through experiments carried out with real-world data extracted from the openly available New York City taxicab dataset.