Recent Progress in Large-Scale Ridesharing Algorithms

Ridesharing, a new shared mobility service where passengers with different origins and destinations agree to take the same vehicle for their rides and share the cost, is experiencing widespread adoption with the development of sharing economy. In the era of mobile Internet and ubiquitous computing, ridesharing becomes large-scale and exhibits new characteristics including enormous data, dynamic scenarios, diverse objectives, and varied applications. These characteristics fundamentally complicate the ridesharing problem and have spurred extensive new research on large-scale ridesharing algorithms. Furthermore, research on social aspects of large-scale ridesharing has also attracted increasing research attention. This paper aims at a systematic and comprehensive survey on recent advances in large-scale ridesharing algorithms. We first introduce the basic concepts and workflow of ridesharing, and then systematically review existing algorithms for route planning, the core algorithmic problem for large-scale ridesharing. We also discuss social aspects critical for practical large-scale ridesharing applications such as incentive mechanisms, privacy and safeguard measures and finally point out potential future research directions.