A Time-Indexed Model for Online Ride-Sharing Optimization: Benchmarking Online Algorithms

This paper presents a novel mathematical model for the dynamic and online ride-sharing problem, incorporating time-dependent variables that account for the time aspects of ride requests and demands. The model uses complete knowledge of all future ride requests. While this "prophet" model is not feasible for real-time applications due to its reliance on future data, it serves as a valuable benchmark for evaluating the performance of online algorithms. By comparing the results of real-time algorithms against this optimal solution, researchers can better assess the effectiveness and efficiency of various dynamic ride-sharing strategies and algorithms in practical, real-world scenarios.

Keywords:

Online Ride-Sharing Problem , Mathematical Programming , Exact Static Model , Operation Research , Dynamic Vehicle Routing , Online Optimization