• 中国精品科技期刊
  • CCF推荐A类中文期刊
  • 计算领域高质量科技期刊T1类
Advanced Search
Cao Bin, Hong Feng, Wang Kai, Xu Jinting, Zhao Liwei, Fan Jing. Uroad:An Efficient Method for Large-Scale Many to Many Ride Sharing Matching[J]. Journal of Computer Research and Development, 2019, 56(4): 866-883. DOI: 10.7544/issn1000-1239.2019.20180035
Citation: Cao Bin, Hong Feng, Wang Kai, Xu Jinting, Zhao Liwei, Fan Jing. Uroad:An Efficient Method for Large-Scale Many to Many Ride Sharing Matching[J]. Journal of Computer Research and Development, 2019, 56(4): 866-883. DOI: 10.7544/issn1000-1239.2019.20180035

Uroad:An Efficient Method for Large-Scale Many to Many Ride Sharing Matching

More Information
  • Published Date: March 31, 2019
  • Due to the congested road and the increasing cost of private car, more and more people are willing to choose carpooling for travel. Although there are a lot of algorithms for ride sharing research, there is no algorithm to consider this problem from a global view. Plan all the matching routes from the global view and make all drivers’ detour distances minimize, which not only can reduce air pollution, but also can ease the traffic pressure. This paper presents an efficient large-scale matching method for many to many ride sharing algorithm, called Uroad, to make up for the shortcomings of existing algorithms. Uroad allows the rider to request a ride service which includes the periods of departure time when he gets ready to start off and the maximum cost of the ride-sharing he is willing to pay for this service. At the same time, Uroad allows the driver to set the departure time to indicate when he will set out and the arrival time that he must reach to his destination before. The same to the other Carpooling algorithms, Uroad calculates the fare based on the distance of rider’s trip and the detour caused by the rider. According to the requirements of riders and drivers, Uroad supports the global optimal matching among multiple riders and drivers, matches a driver who can meet the requirements to each rider as far as possible, and minimizes the total detour of all the drivers to reach the goal of environmental protection and reducing the traffic pressure. Uroad uses a series of time pruning techniques and Euclidean distance pruning techniques to reduce the calculation of the shortest path which can make the overall algorithm more quick and efficient. The experiments show that it is less than 2 minutes for Uroad to find the optimal combination of ride-sharing for 1 000 riders in 100 000 drivers, which is 40% shorter than the direct calculation of the shortest path. Compared with the random selection of drivers, the total detours of all drivers can be reduced by about 60% with the global optimization strategy.
  • Related Articles

    [1]Li Jianhui, Shen Zhihong, Meng Xiaofeng. Scientific Big Data Management: Concepts, Technologies and System[J]. Journal of Computer Research and Development, 2017, 54(2): 235-247. DOI: 10.7544/issn1000-1239.2017.20160847
    [2]Shen Bilong, Zhao Ying, Huang Yan, Zheng Weimin. Survey on Dynamic Ride Sharing in Big Data Era[J]. Journal of Computer Research and Development, 2017, 54(1): 34-49. DOI: 10.7544/issn1000-1239.2017.20150729
    [3]ZhuWeiheng, YinJian, DengYuhui, LongShun, QiuShiding. Efficient Duplicate Detection Approach for High Dimensional Big Data[J]. Journal of Computer Research and Development, 2016, 53(3): 559-570. DOI: 10.7544/issn1000-1239.2016.20148218
    [4]Meng Xiaofeng, Du Zhijuan. Research on the Big Data Fusion: Issues and Challenges[J]. Journal of Computer Research and Development, 2016, 53(2): 231-246. DOI: 10.7544/issn1000-1239.2016.20150874
    [5]Li Weibang, Li Zhanhuai, Chen Qun, Jiang Tao, Liu Hailong, Pan Wei. Functional Dependencies Discovering in Distributed Big Data[J]. Journal of Computer Research and Development, 2015, 52(2): 282-294. DOI: 10.7544/issn1000-1239.2015.20140229
    [6]Meng Xiaofeng, Zhang Xiaojian. Big Data Privacy Management[J]. Journal of Computer Research and Development, 2015, 52(2): 265-281. DOI: 10.7544/issn1000-1239.2015.20140073
    [7]Liu Yahui, Zhang Tieying, Jin Xiaolong, Cheng Xueqi. Personal Privacy Protection in the Era of Big Data[J]. Journal of Computer Research and Development, 2015, 52(1): 229-247. DOI: 10.7544/issn1000-1239.2015.20131340
    [8]Meng Xiaofeng, Li Yong, Jonathan J. H. Zhu. Social Computing in the Era of Big Data: Opportunities and Challenges[J]. Journal of Computer Research and Development, 2013, 50(12): 2483-2491. DOI: 10.7544/issn1000-1239.2013.20130890
    [9]Li Jianzhong and Liu Xianmin. An Important Aspect of Big Data: Data Usability[J]. Journal of Computer Research and Development, 2013, 50(6): 1147-1162.
    [10]Meng Xiaofeng and Ci Xiang. Big Data Management: Concepts,Techniques and Challenges[J]. Journal of Computer Research and Development, 2013, 50(1): 146-169.
  • Cited by

    Periodical cited type(5)

    1. 廖鑫,黎懿熠,欧阳军林,周江盟,戴湘桃,秦拯. 一种基于深度学习的移动端隐写方法. 湖南大学学报(自然科学版). 2022(04): 18-25 .
    2. 何凤英. 改进卷积神经网络在图像隐写检测中的应用. 福建电脑. 2022(09): 1-6 .
    3. 黄思远,张敏情,柯彦,毕新亮. 基于显著性检测的图像隐写分析方法. 计算机应用. 2021(02): 441-448 .
    4. 黄思远,张敏情,柯彦,毕新亮. 基于自注意力机制的图像隐写分析方法. 计算机应用研究. 2021(04): 1190-1194 .
    5. 吴煌,李凯勇. 基于DCT域的数字图像隐写容量归一化方法. 计算机仿真. 2021(08): 207-211 .

    Other cited types(5)

Catalog

    Article views (2344) PDF downloads (580) Cited by(10)

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return