计算机科学与探索 ›› 2022, Vol. 16 ›› Issue (7): 1611-1622.DOI: 10.3778/j.issn.1673-9418.2012039
收稿日期:
2020-12-10
修回日期:
2021-02-07
出版日期:
2022-07-01
发布日期:
2021-02-26
作者简介:
郭羽含(1983—),男,黑龙江哈尔滨人,博士,副教授,硕士生导师,CCF会员,主要研究方向为智能搜索算法、车辆调度问题、供应链优化问题。 基金资助:
Received:
2020-12-10
Revised:
2021-02-07
Online:
2022-07-01
Published:
2021-02-26
Supported by:
摘要:
随着互联网技术的快速发展,网约车已成为出行的重要方式。通过智能手段为用户推荐上车点不仅可有效实现分流缓解道路拥堵,也可减少乘客与司机的沟通成本,提升司机的服务效率并降低乘客的等待时间,从而提高司乘双方的出行体验感。但现存推荐方法所依据的指标较为单一,未在乘客便利性与司机收益之间取得较好平衡,且无法保证所推荐上车点的安全性与可达性。通过对时空轨迹大数据的归纳与分析,提取保证可达性的潜在上车点,避免依据单一指标推荐上车点所导致的偏袒性问题,综合考虑乘客步行收益、司机驾驶收益、上车点路况指标、周边安全性等关键因素,建立上车点的复合收益评价,构建上车点的动态推荐模型。以约束控制同时段同上车点的推荐量,有效解决由于单上车点订单堆积而造成的非必要等待和资源浪费,在一定程度上缓解交通压力。基于真实网约车数据的实验表明,该模型和推荐方法可实现上车点的有效动态分配,较单一指标上车点推荐方法有较好的综合收益与时间优势。从司机与乘客双方角度出发,在降低行程总时间的基础上,提升全局司机接驾效率并降低乘客等待时间,且推荐结果的综合评价值优于现存推荐方法。
中图分类号:
郭羽含, 刘秋月. 时空轨迹和复合收益的动态上车点推荐[J]. 计算机科学与探索, 2022, 16(7): 1611-1622.
GUO Yuhan, LIU Qiuyue. Dynamic Pickup-Point Recommendation Based on Spatiotemporal Trajectory and Hybrid Gain Evaluation[J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(7): 1611-1622.
符号 | 含义 |
---|---|
| 乘客步行收益 |
| 司机驾驶收益 |
| 上车点路况指标 |
| 上车点安全指标 |
| 上车点id |
| 乘客标识 |
| 乘客叫车点经度 |
| 乘客叫车点纬度 |
| 上车点经度 |
| 上车点纬度 |
| 乘客从叫车点到上车点的距离 |
| 司机标识 |
| 乘客目的地经度 |
| 乘客目的地纬度 |
| 司机从上车点到乘客目的地的距离 |
| 司机当前位置经度 |
| 司机当前位置纬度 |
| 司机从当前位置到上车点的接驾距离 |
| 上车点的瞬时速度 |
| 上车点的平均速度 |
| 上车点的速度方差 |
表1 参数及变量
Table 1 Parameters and variables
符号 | 含义 |
---|---|
| 乘客步行收益 |
| 司机驾驶收益 |
| 上车点路况指标 |
| 上车点安全指标 |
| 上车点id |
| 乘客标识 |
| 乘客叫车点经度 |
| 乘客叫车点纬度 |
| 上车点经度 |
| 上车点纬度 |
| 乘客从叫车点到上车点的距离 |
| 司机标识 |
| 乘客目的地经度 |
| 乘客目的地纬度 |
| 司机从上车点到乘客目的地的距离 |
| 司机当前位置经度 |
| 司机当前位置纬度 |
| 司机从当前位置到上车点的接驾距离 |
| 上车点的瞬时速度 |
| 上车点的平均速度 |
| 上车点的速度方差 |
名称 | 环境 |
---|---|
操作系统 | Windows 10 |
CPU | Intel®CoreTM i5-10210UCPU@1.60 GHz |
CPU核数 | 6 |
内存/GB | 16 |
Python版本 | Python3.7 |
表2 实验环境
Table 2 Experimental environment
名称 | 环境 |
---|---|
操作系统 | Windows 10 |
CPU | Intel®CoreTM i5-10210UCPU@1.60 GHz |
CPU核数 | 6 |
内存/GB | 16 |
Python版本 | Python3.7 |
参数 | 含义 | 数值 |
---|---|---|
| 上车点分配人数阈值 | 5 |
| 时间间隔 | 1 |
| 误差半径 | 1 |
| 乘客数量 | 100 |
| 司机数量 | 100 |
| 扫描半径 | 30 |
| | 0.4 |
| | 0.6 |
| | 0.5 |
| | 0.5 |
表3 参数设置
Table 3 Parameter setting
参数 | 含义 | 数值 |
---|---|---|
| 上车点分配人数阈值 | 5 |
| 时间间隔 | 1 |
| 误差半径 | 1 |
| 乘客数量 | 100 |
| 司机数量 | 100 |
| 扫描半径 | 30 |
| | 0.4 |
| | 0.6 |
| | 0.5 |
| | 0.5 |
参数 | 含义 | 数值 |
---|---|---|
| 乘客步行收益权重 | 0.35 |
| 司机驾驶收益权重 | 0.23 |
| 上车点路况指标权重 | 0.27 |
| 上车点安全性指标权重 | 0.15 |
表4 PPS实验权重设置
Table 4 Weight setting in PPS experiment
参数 | 含义 | 数值 |
---|---|---|
| 乘客步行收益权重 | 0.35 |
| 司机驾驶收益权重 | 0.23 |
| 上车点路况指标权重 | 0.27 |
| 上车点安全性指标权重 | 0.15 |
参数 | 含义 | 数值 |
---|---|---|
| 乘客步行收益权重 | 0.126 |
| 司机驾驶收益权重 | 0.281 |
| 上车点路况指标权重 | 0.525 |
| 上车点安全性指标权重 | 0.068 |
表5 DPS实验权重设置
Table 5 Weight setting in DPS experiment
参数 | 含义 | 数值 |
---|---|---|
| 乘客步行收益权重 | 0.126 |
| 司机驾驶收益权重 | 0.281 |
| 上车点路况指标权重 | 0.525 |
| 上车点安全性指标权重 | 0.068 |
方案 | 步行收益 | 驾驶收益 | 路况指标 | 安全系数 | 综合收益 | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
平均 | 最大 | 最小 | 平均 | 最大 | 最小 | 平均 | 最大 | 最小 | 平均 | 最大 | 最小 | 平均 | 最大 | 最小 | |
PPS | 1.94 | 16.67 | 0.10 | 1.13 | 11.55 | 0.26 | 0.09 | 0.16 | 0.02 | 0.67 | 1.00 | 0 | 3.82 | 17.03 | 0.87 |
DPS | 1.91 | 16.67 | 0.10 | 1.13 | 11.54 | 0.25 | 0.10 | 0.16 | 0.02 | 0.66 | 1.00 | 0 | 3.80 | 17.03 | 0.87 |
WDRS[ | 1.95 | 16.67 | 0.10 | 1.12 | 11.54 | 0.26 | 0.08 | 0.16 | 0.02 | 0.51 | 1.00 | 0 | 3.66 | 17.04 | 0.87 |
RCRS[ | 0.42 | 5.00 | 0.10 | 0.99 | 7.00 | 0.26 | 0.15 | 0.16 | 0.11 | 0.52 | 1.00 | 0 | 2.08 | 8.32 | 0.57 |
表6 上车点收益表
Table 6 Revenue of pickup point
方案 | 步行收益 | 驾驶收益 | 路况指标 | 安全系数 | 综合收益 | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
平均 | 最大 | 最小 | 平均 | 最大 | 最小 | 平均 | 最大 | 最小 | 平均 | 最大 | 最小 | 平均 | 最大 | 最小 | |
PPS | 1.94 | 16.67 | 0.10 | 1.13 | 11.55 | 0.26 | 0.09 | 0.16 | 0.02 | 0.67 | 1.00 | 0 | 3.82 | 17.03 | 0.87 |
DPS | 1.91 | 16.67 | 0.10 | 1.13 | 11.54 | 0.25 | 0.10 | 0.16 | 0.02 | 0.66 | 1.00 | 0 | 3.80 | 17.03 | 0.87 |
WDRS[ | 1.95 | 16.67 | 0.10 | 1.12 | 11.54 | 0.26 | 0.08 | 0.16 | 0.02 | 0.51 | 1.00 | 0 | 3.66 | 17.04 | 0.87 |
RCRS[ | 0.42 | 5.00 | 0.10 | 0.99 | 7.00 | 0.26 | 0.15 | 0.16 | 0.11 | 0.52 | 1.00 | 0 | 2.08 | 8.32 | 0.57 |
方案 | 步行时间 | 接驾时间 | 路程时间 | 行程总时间 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
平均 | 最大 | 最小 | 平均 | 最大 | 最小 | 平均 | 最大 | 最小 | 平均 | 最大 | 最小 | |
PPS | 3.17 | 16.31 | 0.50 | 0.55 | 9.65 | 0.05 | 20.40 | 55.06 | 1.27 | 24.12 | 64.81 | 2.82 |
DPS | 3.74 | 16.40 | 0.50 | 0.61 | 9.65 | 0.05 | 20.41 | 55.07 | 1.28 | 24.76 | 64.82 | 2.83 |
WDRS[ | 2.90 | 16.31 | 0.10 | 0.52 | 9.65 | 0.05 | 20.43 | 55.07 | 1.28 | 23.85 | 64.82 | 2.83 |
RCRS[ | 10.99 | 16.65 | 1.00 | 1.29 | 9.68 | 0.07 | 20.48 | 55.09 | 1.51 | 32.76 | 66.67 | 12.14 |
表7 行程时间表
Table 7 Travel schedule min
方案 | 步行时间 | 接驾时间 | 路程时间 | 行程总时间 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
平均 | 最大 | 最小 | 平均 | 最大 | 最小 | 平均 | 最大 | 最小 | 平均 | 最大 | 最小 | |
PPS | 3.17 | 16.31 | 0.50 | 0.55 | 9.65 | 0.05 | 20.40 | 55.06 | 1.27 | 24.12 | 64.81 | 2.82 |
DPS | 3.74 | 16.40 | 0.50 | 0.61 | 9.65 | 0.05 | 20.41 | 55.07 | 1.28 | 24.76 | 64.82 | 2.83 |
WDRS[ | 2.90 | 16.31 | 0.10 | 0.52 | 9.65 | 0.05 | 20.43 | 55.07 | 1.28 | 23.85 | 64.82 | 2.83 |
RCRS[ | 10.99 | 16.65 | 1.00 | 1.29 | 9.68 | 0.07 | 20.48 | 55.09 | 1.51 | 32.76 | 66.67 | 12.14 |
[1] | 费太兵, 桑晓珮, 朱琪月. “互联网+”时代中国网约车发展困境及对策研究[J]. 科技经济导刊, 2020, 28(9): 28. |
FEI T B, SANG X P, ZHU Q Y. Research on the dilemma and countermeasures of the development of China Internet contract car in the Internet plus era[J]. Technology and Economic Guide, 2020, 28(9): 28. | |
[2] | 徐海良, 束纬寰, 李瑞东.上车点推荐方法、装置及设备: 201711346863. 4[P]. 2017. |
XU H L, SHU W H, LI R D.Recommended method, device and equipment for boarding point: 201711346863. 4[P]. 2017. | |
[3] | 范哲铭.待载客车辆的路线推荐方法及上车点推荐方法: 201811258473. 6[P]. 2020. |
FAN Z M.Route recommendation method and boarding point recommendation method for passenger cars to be loaded: 201811258473. 6[P]. 2020. | |
[4] | 吴立薪, 陈弥, 尹茂林, 等. 上车点推荐的方法、装置、设备及存储介质: 202010440986.X[P]. 2020. |
WU L X, CHEN M, YIN M L, et al. Recommended method, device, equipment and storage medium at the vehicle loading point: 202010440986.X[P]. 2020. | |
[5] | 冀杰, 唐志荣, 吴明阳, 等. 面向车道变换的路径规划及模型预测轨迹跟踪[J]. 中国公路学报, 2018, 31(4): 172-179. |
JI J, TANG Z R, WU M Y, et al. Path planning and tracking for lane changing based on model predictive control[J]. China Journal of Highway and Transport, 2018, 31(4): 172-179. | |
[6] |
李立, 徐志刚, 赵祥模, 等. 智能网联汽车运动规划方法研究综述[J]. 中国公路学报, 2019, 32(6): 20-33.
DOI |
LI L, XU Z G, ZHAO X M, et al. Review of motion planning methods of intelligent connected vehicles[J]. China Journal of Highway and Transport, 2019, 32(6): 20-33.
DOI |
|
[7] |
李麟, 裴玉龙, 尹亮, 等. 基于稳定性和宏观交通流模型的车辆路径规划[J]. 中国公路学报, 2020, 33(8): 71-80.
DOI |
LI L, PEI Y L, YIN L, et al. Vehicle path planning based on stability and macroscopic traffic flow model[J]. China Journal of Highway and Transport, 2020, 32(8): 71-80. | |
[8] | 郭羽含, 宇俊宇. 考虑时空热度的共乘匹配问题建模及求解[J]. 交通运输系统工程与信息, 2019, 19(6): 112-122. |
GUO Y H, YU J Y. Modelization and resolution of ride-sharing problem with spatiotemporal thermo[J]. Journal of Transportation Systems Engineering and Information Techn-ology, 2019, 19(6): 112-122. | |
[9] | 贺明慧. 基于Spark的上车点推荐系统的设计与实现[D]. 北京: 北京交通大学, 2018. |
HE M H. Design and implementation of aboard-point recommendation system based on Spark[D]. Beijing: Beijing Jiaotong University, 2018. | |
[10] | 钟颖. 一种为乘客提供上车地点的方法和装置: CN2016- 10601433.1[P]. 2016. |
ZHONG Y. A method and device for providing a boarding place for passengers: CN201610601433.1[P]. 2004. | |
[11] | 马云飞. 基于出租车轨迹点的居民出行热点区域与时空特征研究[D]. 南京: 南京师范大学, 2014. |
MA Y F. Research on residents’ behavoir of attractive areas and spatio-temporal feature based on taxi trajectory data[D]. Nanjing: Nanjing Normal University, 2014. | |
[12] | 张旭东.上车点推荐方法及装置: 201910338700. 4[P]. 2019. |
ZHANG X D.Recommended method and device for boarding point: 201910338700. 4[P]. 2019. | |
[13] | 张岩.一种推荐上车点的方法、装置、设备及存储介质: 201810792316. 7[P]. 2018. |
ZHANG Y. A method, device.equipment and storage medium for recommending a boarding point: 201810792316. 7[P]. 2018. | |
[14] | 张海强. 一种推荐上车地点的方法及装置: CN2017-10708158.8[P]. 2017. |
ZHANG H Q. A method and device for recommending boarding place: CN201710708158.8[P]. 2017. | |
[15] | 苏童, 成晓婧. 滴滴出行安全与城市管理对接研究[J]. 财富时代, 2020(1): 45-46. |
SU T, CHENG X J. Research on the connection between DiDi travel safety and urban management[J]. Times of Fortune, 2020(1): 45-46. | |
[16] | 李青鹏, 赵相福, 陈中育, 等. 基于区块链的网约车安全风险规避模式[J]. 计算机技术与发展, 2019, 29(9): 152-157. |
LI Q P, ZHAO X F, CHEN Z Y, et al. Risk avoidance for safe network car system based on blockchain[J]. Computer Technology and Development, 2019, 29(9): 152-157. | |
[17] | 温志强, 李永俊. 网约车时代公共交通司乘安全科技保障研究[J]. 江苏科技信息, 2019, 36(22): 74-76. |
WEN Z Q, LI Y J. Study on the security technology guarantee of the public transportation department in the age of online car booking[J]. Jiangsu Science & Technology Information, 2019, 36(22): 74-76. | |
[18] | 郑小红, 龙军, 蔡志平. 关于网约车订单分配策略的综述[J]. 计算机工程与科学, 2020, 42(7): 1267-1275. |
ZHENG X H, LONG J, CAI Z P. A survey of order dispatch policy based on online ride-hailing services[J]. Computer Engineering & Science, 2020, 42(7): 1267-1275. |
[1] | 张硕航, 郭改枝. 多旅行商模型及其应用研究综述[J]. 计算机科学与探索, 2022, 16(7): 1516-1528. |
[2] | 林浩,李雷孝,王慧. 支持向量机在智能交通系统中的研究应用综述[J]. 计算机科学与探索, 2020, 14(6): 901-917. |
[3] | 刘忠慧,邹璐,杨梅,闵帆. 启发式概念构造的组推荐方法[J]. 计算机科学与探索, 2020, 14(4): 703-711. |
[4] | 张呈玲,李进金,林艺东. 不协调决策形式背景的矩阵型属性约简[J]. 计算机科学与探索, 2020, 14(3): 534-540. |
[5] | 江成,张军,卢山. 复杂网络关键节点组识别问题模型和算法研究[J]. 计算机科学与探索, 2019, 13(8): 1319-1330. |
[6] | 郭羽含,伊鹏. 车辆合乘问题的分布式复合变邻域搜索算法[J]. 计算机科学与探索, 2019, 13(2): 330-341. |
[7] | 赵超,王慧强,林俊宇,吕宏武,韩冀中. 面向大规模网络安全加固的攻击图分析方法[J]. 计算机科学与探索, 2018, 12(2): 263-273. |
[8] | 胡敏,孙欣然,黄宏程. 边缘覆盖去重的社交网络影响力最大化算法[J]. 计算机科学与探索, 2017, 11(5): 720-731. |
[9] | 王永恒,高慧,陈炫伶. 采用变结构动态贝叶斯网络的交通流量预测[J]. 计算机科学与探索, 2017, 11(4): 528-538. |
[10] | 陆秋琴,黄光球. 生态平衡动力学优化算法[J]. 计算机科学与探索, 2017, 11(10): 1689-1700. |
[11] | 侯越. 基于改进T-S模糊神经网络的交通流量预测[J]. 计算机科学与探索, 2014, 8(1): 121-126. |
阅读次数 | ||||||
全文 |
|
|||||
摘要 |
|
|||||