ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2020, Vol. 57 ›› Issue (1): 32-52.doi: 10.7544/issn1000-1239.2020.20190239

所属专题: 2020优青专题

• 综述 • 上一篇    下一篇

大规模拼车算法研究进展

徐毅,童咏昕,李未   

  1. (软件开发环境国家重点实验室(北京航空航天大学) 北京 100191) (北京航空航天大学计算机学院 北京 100191) (xuy@buaa.edu.cn)
  • 出版日期: 2020-01-01
  • 基金资助: 
    国家自然科学基金优秀青年科学基金项目(61822201);国家自然科学基金项目(U1811463)

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

中图分类号: