ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2017, Vol. 54 ›› Issue (1): 34-49.doi: 10.7544/issn1000-1239.2017.20150729

• 综述 • 上一篇    下一篇



  1. 1(清华大学计算机科学与技术系 北京 100084); 2(北德克萨斯州大学计算机科学与工程系 美国德克萨斯州登顿市 311277) (
  • 出版日期: 2017-01-01

Survey on Dynamic Ride Sharing in Big Data Era

Shen Bilong1, Zhao Ying1, Huang Yan2, Zheng Weimin1   

  1. 1(Department of Computer Science and Technology, Tsinghua University, Beijing 100084); 2(Computer Science and Engineering Department, University of North Texas, Denton, TX, USA 311277)
  • Online: 2017-01-01

摘要: 共乘也被称为“合乘”、“拼车”、“顺风车”,通过有效整合运力资源减少路上行驶车辆数量,对缓解交通拥堵、降低出行费用、减轻环境污染都有重要意义.大数据背景下实时更新的车辆位置信息数据、城市交通数据、社交网络数据,为智能出行特别是共乘带来了全新的发展机遇.在车辆行驶中对乘客请求进行实时匹配的动态共乘,是大数据背景下智能出行发展趋势的代表.在统一归纳了解决动态共乘实时性的Filter and Refine框架基础上,介绍了动态共乘的各种类型;针对大数据背景下动态共乘问题遇到的问题,对Filter步骤中预先计算可行解、建立动态空间索引、基于请求分组预处理及并行优化方法,Refine步骤中简化计算模型、采用新型数据结构、利用启发式算法等优化方法进行了详细介绍;然后对大数据背景下保证动态共乘系统的价格机制、信用体系和人机接口等相关技术进行了分析;最后,总结展望了大数据背景下动态共乘中亟待解决的关键问题和未来的研究方向,以期为创造低碳生活、绿色出行,解决环境污染有所启示.

关键词: 共乘, 动态共乘, 大数据, 优化算法, 城市计算

Abstract: The availability of multi-source data in big data era can potentially lead to a revolution in ride sharing, which has been widely studied in academia as a means of reducing the number of cars, congestion, and pollution by sharing empty seats, and is lack of popularity in practice due to the inflexibility of off-line booking, limited resources and so on. In big data era, dynamic ride sharing, powered by mobile computation, location based service, and social networks, emerges and gains popularities recently for providing real-time and flexible ride sharing services through real-time travel planning systems. These systems raise research opportunities as well as challenges, including how to process real-time location data and traffic data, to match ride requests and cars in real time, and to provide fair, secure, and low-priced services to gain more participants. This paper defines the problem of dynamic ride sharing formally and discusses its variants and recent developments. The framework of filter and refine to solve the real-time challenges of matching requests and cars is then discussed. In particular, in the filter step, we introduce the method of pre-computing, spatio-temporal index, grouping, and parallelizing. In the refine step, we introduce the method of lazy calculation strategy, new index tree structure, and evolutionary computation. We also discuss the techniques related to social factors such as pricing strategies, credit system, human-computer interaction, and security in big data era. Finally, this paper ends with a panoramic summary and a discussion on possible future research directions.

Key words: ride sharing, dynamic ride sharing, big data, optimization algorithm, urban computing