(浙江工业大学计算机科学与技术学院 杭州 310023) (bincao@zjut.edu.cn)
出版日期: 2019-04-01基金资助:国家自然科学基金项目(61520106005，61761136014)；国家重点研发计划项目(2017YFB1010000)Uroad：An Efficient Method for Large-Scale Many to Many Ride Sharing Matching
Cao Bin, Hong Feng, Wang Kai, Xu Jinting, Zhao Liwei, Fan Jing(College of Computer Science & Technology, Zhejiang University of Technology, Hangzhou 310023)
Online: 2019-04-01摘要/Abstract
摘要： 由于日益拥堵的交通环境和不断增加的私家车出行成本，越来越多的人关注并接受拼车的出行方式.虽然现在已经有很多针对拼车研究的算法，但是目前还没有从全局的角度出发考虑拼车匹配问题的算法.从全局的角度合理规划所有拼车匹配路线，使所有司机因为拼车而产生的绕路距离最小，这不但能减少空气污染还能缓解交通压力等.因此，提出了一种高效的大规模多对多拼车匹配算法Uroad来弥补这一不足.Uroad允许乘客在提出的拼车请求中包含出发时间段和最大拼车费用来表明自己要求的出发时间范围和对拼车服务最多愿意支付的费用；也允许司机提出出发时间和最晚达到时间约束来表明自己开始行程的时间点和最晚达到自身目的地的时间点.和其他拼车算法一样，Uroad根据乘客自身的行程距离和拼车后对司机造成的绕路距离来计算车费.根据乘客和司机的要求，Uroad支持多乘客与多司机全局最优匹配，并同时尽可能为每一名乘客匹配一名符合双方拼车条件的司机，最终使得所有司机产生的绕路距离总和最小.Uroad通过前期一系列的基于时间、欧氏距离、路网距离的3种空间剪枝策略来减少最短路径的计算量，从而提高算法的整体效率.实验结果显示，Uroad算法能在2 min内，实现1 000名乘客在100 000名司机中找出最优的拼车匹配组合方案，与直接计算最短路径的基本方法相比，整体耗时缩短了40%.和现有算法中乘客随机选择司机的策略相比，加入了全局优化策略之后，Uroad算法中所有司机的绕路距离总和可减少60%左右.
参考文献
相关文章 11
| [1] | 徐毅, 童咏昕, 李未. 大规模拼车算法研究进展[J]. 计算机研究与发展, 2020, 57(1): 32-52. |
| [2] | 王豫峰,董文永,董学士,王浩. 求解大尺度优化问题的学生t-分布估计算法[J]. 计算机研究与发展, 2017, 54(8): 1644-1654. |
| [3] | 彭虎, 吴志健, 周新宇, 邓长寿. 基于三角的骨架差分进化算法[J]. 计算机研究与发展, 2015, 52(12): 2776-2788. |
| [4] | 谢丽萍 曾建潮. 基于拟态物理学方法的全局优化算法[J]. , 2011, 48(5): 848-854. |
| [5] | 刘国 周忠 吴威. 发布/订购系统中基于重复属性判定的事件匹配算法研究[J]. , 2010, 47(10): 1690-1699. |
| [6] | 陈中贵 刘利刚 王国瑾. 基于全局优化的图像块填充修复方法[J]. , 2009, 46(1): 144-150. |
| [7] | 蒋夏军 吴慧中 李蔚清. 数据分发管理匹配算法的R-树实现[J]. , 2006, 43(2): 362-367. |
| [8] | 徐 罡 马建刚 黄 涛. 一种基于OBDD图的事件复合匹配方法[J]. , 2006, 43(10): 1751-1759. |
| [9] | 何卫锋 毛志刚 吕志强 尹海丰. 一种基于FBMA算法的整像素运动估计芯片的VLSI设计[J]. , 2005, 42(7): 1225-1230. |
| [10] | 郎显宇, 牛北方, 沈 斌, 陆忠华, 迟学斌,. 分子空间结构比较方法优化与点部署的并行实现[J]. , 2005, 42(6): 1047-1052. |
| [11] | 汪锦岭 金蓓弘 李 京. 一种高效的RDF图模式匹配算法[J]. , 2005, 42(10): 1763-1770. |
PDF全文下载地址:
https://crad.ict.ac.cn/CN/article/downloadArticleFile.do?attachType=PDF&id=3915
