Novel dynamic formulations for real-time ride-sharing systems

This paper proposes new objective functions for the matching problem arising in ride-sharing systems based on trips’ spatial attributes. Novel dynamic matching policies are then proposed to solve the problem dynamically in a rolling horizon framework. Finally, we present a new clustering heuristic to tackle instances with a large number of participants efficiently. We find that the proposed models maximize the matching rate while maintaining distance-savings at an acceptable level, which is an appealing achievement for ride-sharing systems. Further, our solution method is capable of solving large-scale instances in real-time.