An Effective Multi-hop Ride-Sharing Algorithm on Large-Scale Road Networks

This paper addresses the multi-hop ride-sharing problem in large-scale road networks. Traditional ride-sharing (i.e., single-hop ride-sharing) is constrained by limited flexibility and rider convenience, whereas multi-hop ride-sharing significantly enhances adaptability by allowing riders to transfer between multiple vehicles during their trips. We construct a Feasible Matching Graph (FMG) to systematically represent the potential matching relationships between drivers and riders, capturing feasible areas and possible path constraints for drivers. To efficiently organize and store paths within the FMG and avoid redundant calculations during repeated searches, we introduce a Guide-Tree based on the Trie data structure, which captures the hierarchical relationships among paths and allows shared subpaths to be stored only once, thereby substantially improving search efficiency. Building on the Guide-Tree, we propose the Guide Search (GS) algorithm, which leverages the Guide-Tree to identify optimal multi-hop paths, significantly reducing the search space and improving computational efficiency. Extensive experiments on two real-world datasets show that our algorithms consistently outperform current state-of-the-art methods in both computational efficiency and scalability.