Scalable ride-sharing through geometric algorithms and multi-hop matching

© 2020 Yixin XuThanks to the ubiquitous access to the Internet, on-demand ride-sharing service has emerged to provide timely and convenient rides to passengers. Ride-sharing creates a win-win situation for all participants involved and brings substantial environmental benefits, thus becoming a prevalent transportation mode. A fundamental problem of ride-sharing is determining how to dispatch vehicles to passengers. Efficiency and optimality are two core requirements for dispatching algorithms. Long response times would significantly impact the user experience, while sub-optimal matching results would substantially lower the operational efficiency. Finding optimal matches in a short time is challenging due to a large number of involved participants, the highly dynamic scenario, and the expensive road network distance computation. This thesis proposes efficient and scalable algorithms to enable fast and high-quality dispatching. We observe that vehicles and passengers can only visit limited areas to ensure their latest arrival times. The limited areas can be used to quickly filter out infeasible vehicles. Such areas can be easily indexed and updated if represented as rectangles. Inspired by this key observation, we first propose an efficient algorithm to solve a basic problem in ride-sharing -- how to quickly prune infeasible vehicles for passengers. Our algorithm ensures the finding of all possible candidates since we compute and index the confined visiting areas using ellipses, and the ellipses provide tight bound regardless of the underlying network. The effective pruning leads to only a small number of candidates remained, which substantially reduces the complexity of selecting the optimal matches and the overall matching time. We further investigate multi-hop ride-sharing algorithms that allow transfers on a user's trip. The algorithms search for possible transfers between vehicles by detecting whether the visiting areas of vehicles overlap. The proposed algorithms prune the combinations of vehicles and transfer points, thus overcoming the efficiency bottleneck and achieving real-time responses. We propose exact algorithms that guarantee the finding of optimal matches. We further improve the matching time using speed-up strategies. The enabled multi-hop trips largely enhance the flexibility of real-world ride-sharing, increase the number of successfully matched requests, and reduce the travel distance of vehicles. Lastly, we facilitate quick assigning of nearest pick-up/drop-off locations for passengers by proposing an efficient and scalable all nearest neighbor algorithm in road networks. We exploit the property of the problem such that finding a nearest neighbor only consumes constant time while only one graph traversal is required during the preprocessing phase. The proposed algorithms in this thesis achieve orders of magnitude faster running time compared to the state-of-the-art algorithms. The auxiliary indices are lightweight and eliminate the high preprocessing and update cost for the highly dynamic scenarios