A distributed algorithm for operating large-scale ridesourcing systems

With ridesourcing services gaining popularity in the past few years, there has been growing interest in algorithms that could enable real-time operation of these systems. As ridesourcing systems rely on independent entities to build the supply and demand sides of the market, they have been shown to operate more successfully in metropolitan areas where there is a high level of demand for rides as well as a high number of drivers, and a large volume of trips occurring within a geographically constrained region. Despite the suitable ecosystem that metropolitan areas offer for ridesourcing operations, there is a lack of methods that can provide high-quality matching solutions in real-time. To fill this gap, this paper introduces a framework that allows for solving the large-scale matching problems by means of solving smaller problems in a distributed fashion. The proposed methodology is based on constructing approximately-uniform clusters of trip requests, where vehicle tours form cluster centers. Using the New York Taxi dataset, we compare the performance of the proposed methodology against three benchmark methods to showcase its advantages in terms of solution quality and solution time.