Trip-based graph partitioning in dynamic ridesharing

Abstract A dynamic ridesharing system is a platform that connects drivers who use their personal vehicles to travel with riders who are in need of transportation, on a short notice. Since each driver/rider may have several potential matches, to achieve a high performance level, the ridesharing operator needs to make the matching decisions based on a global view of the system that includes all active riders and drivers. Consequently, the ride-matching problem that needs to be solved can become computationally expensive, especially when the system is operating over a large region, or when it faces high demand levels during certain hours of the day. This paper develops a graph partitioning methodology based on the bipartite graph that arises in the one-to-one ride-matching problem. The proposed method decomposes the original graph into multiple sub-graphs with the goal of reducing the overall computational complexity of the problem as well as providing high quality solutions. We further show that this methodology can be extended to more complex ride-matching problems in a dynamic ride-sharing system. Using numerical experiments, we showcase the advantages of the new partitioning method for different forms of ride-matching problems. Moreover, a sensitivity analysis is conducted to show the impact of different parameters on the quality of our solution.