ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2020, Vol. 57 ›› Issue (1): 32-52.doi: 10.7544/issn1000-1239.2020.20190239

Special Issue: 2020优青专题

Previous Articles     Next Articles

Recent Progress in Large-Scale Ridesharing Algorithms

Xu Yi, Tong Yongxin, Li Wei   

  1. (State Key Laboratory of Software Development Environment (Beihang University), Beijing 100191) (School of Computer Science and Engineering, Beihang University, Beijing 100191)
  • Online:2020-01-01
  • Supported by: 
    This work was supported by the National Natural Science Foundation of China for Excellent Young Scientists (61822201) and the National Natural Science Foundation of China (U1811463).

Abstract: 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.

Key words: ridesharing algorithms, route planning, incentive mechanism, privacy preserving, safeguard measure

CLC Number: