时空轨迹和复合收益的动态上车点推荐

doi:10.3778/j.issn.1673-9418.2012039

计算机科学与探索 ›› 2022, Vol. 16 ›› Issue (7): 1611-1622.DOI: 10.3778/j.issn.1673-9418.2012039

时空轨迹和复合收益的动态上车点推荐

郭羽含⁺^,(), 刘秋月

辽宁工程技术大学软件学院,辽宁葫芦岛 125105

收稿日期:2020-12-10 修回日期:2021-02-07 出版日期:2022-07-01 发布日期:2021-02-26
作者简介:郭羽含（1983—）,男,黑龙江哈尔滨人,博士,副教授,硕士生导师,CCF会员,主要研究方向为智能搜索算法、车辆调度问题、供应链优化问题。
GUO Yuhan, born in 1983, Ph.D., associate professor, M.S. supervisor, member of CCF. His research interests include intelligent search algorithm, vehicle scheduling problem and supply chain optimization problem.
刘秋月（1995—）,女,黑龙江黑河人,硕士研究生,主要研究方向为智能搜索算法、车辆调度问题。
LIU Qiuyue, born in 1995, M.S. candidate. Her research interests include intelligent search algorithm and vehicle scheduling problem.
基金资助:
国家自然科学基金(61404069);辽宁省自然科学基金(2019-ZD-0048);辽宁省教育厅基础研究项目(LJ2019JL012)

Dynamic Pickup-Point Recommendation Based on Spatiotemporal Trajectory and Hybrid Gain Evaluation

GUO Yuhan⁺^,(), LIU Qiuyue

School of Software, Liaoning Technical University, Huludao, Liaoning 125105, China

Received:2020-12-10 Revised:2021-02-07 Online:2022-07-01 Published:2021-02-26
Supported by:
the National Natural Science Foundation of China(61404069);the Natural Science Foundation of Liaoning Province(2019-ZD-0048);the Basic Research Project of Department of Education of Liaoning Province(LJ2019JL012)

摘要/Abstract

摘要：

随着互联网技术的快速发展,网约车已成为出行的重要方式。通过智能手段为用户推荐上车点不仅可有效实现分流缓解道路拥堵,也可减少乘客与司机的沟通成本,提升司机的服务效率并降低乘客的等待时间,从而提高司乘双方的出行体验感。但现存推荐方法所依据的指标较为单一,未在乘客便利性与司机收益之间取得较好平衡,且无法保证所推荐上车点的安全性与可达性。通过对时空轨迹大数据的归纳与分析,提取保证可达性的潜在上车点,避免依据单一指标推荐上车点所导致的偏袒性问题,综合考虑乘客步行收益、司机驾驶收益、上车点路况指标、周边安全性等关键因素,建立上车点的复合收益评价,构建上车点的动态推荐模型。以约束控制同时段同上车点的推荐量,有效解决由于单上车点订单堆积而造成的非必要等待和资源浪费,在一定程度上缓解交通压力。基于真实网约车数据的实验表明,该模型和推荐方法可实现上车点的有效动态分配,较单一指标上车点推荐方法有较好的综合收益与时间优势。从司机与乘客双方角度出发,在降低行程总时间的基础上,提升全局司机接驾效率并降低乘客等待时间,且推荐结果的综合评价值优于现存推荐方法。

Abstract:

With the rapid development of Internet technology, online car-hailing has become an important way of travel. Recommending boarding points for users through intelligent means can not only effectively achieve traffic diversion and alleviate congestion, but also reduce the communication cost between passengers and drivers, improve the service efficiency of drivers and reduce the waiting time of passengers, so as to improve the travel experience of both drivers and passengers. However, the existing recommendation methods are normally based on a single criterion, which do not achieve a good balance between passenger convenience and driver income, and can not guarantee the safety and accessibility of the recommended boarding point. By summarizing and analyzing the big data of spatiotemporal trajectory, this paper extracts the potential boarding points to ensure accessibility, avoids the bias caused by considering a single criterion, and comprehensively considers the key factors such as passenger walking income, driver driving income, road condition, and peripheral safety. It establishes a composite income evaluation of boarding points, and constructs the dynamic recommendation model of boarding points to control the recommended quantity of the same boarding point at the same time with constraints, effectively solving the unnecessary waiting and waste of resources caused by the accumulation of orders at a single boarding point, and alleviating the traffic pressure to a certain extent. Experiments based on real online car-hailing data show that the proposed model and recommendation method can achieve an effective dynamic allocation of boarding points, and have better comprehensive benefits and time advantages than the single criterion method. From the perspective of both drivers and passengers, on the basis of reducing the total travel time, the proposed method improves the overall driver pick-up efficiency and reduces the waiting time of passengers, and the comprehensive evaluation shows the obtained results are better than those provided by the existing recommendation methods.

Key words: intelligent transportation, pickup-point recommendation, hybrid gain, spatiotemporal trajectory data, heuristic algorithm

中图分类号:

U495
TP301.6

郭羽含, 刘秋月. 时空轨迹和复合收益的动态上车点推荐[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.

图/表 23

表1 参数及变量

Table 1 Parameters and variables

符号	含义
$G r j (k)$	乘客步行收益
$K d j (k)$	司机驾驶收益
$S k$	上车点路况指标
$P k$	上车点安全指标
$h i d$	上车点id
$r j$	乘客标识
$r c l o n$	乘客叫车点经度
$r c l a t$	乘客叫车点纬度
$h l o n$	上车点经度
$h l a t$	上车点纬度
$L r, h$	乘客从叫车点到上车点的距离
$d j$	司机标识
$r m l o n$	乘客目的地经度
$r m l a t$	乘客目的地纬度
$L h, m$	司机从上车点到乘客目的地的距离
$d l o n$	司机当前位置经度
$d l a t$	司机当前位置纬度
$L d, h$	司机从当前位置到上车点的接驾距离
$v k i$	上车点的瞬时速度
$v - k$	上车点的平均速度
$a k 2$	上车点的速度方差

表1 参数及变量

Table 1 Parameters and variables

符号	含义
$G r j (k)$	乘客步行收益
$K d j (k)$	司机驾驶收益
$S k$	上车点路况指标
$P k$	上车点安全指标
$h i d$	上车点id
$r j$	乘客标识
$r c l o n$	乘客叫车点经度
$r c l a t$	乘客叫车点纬度
$h l o n$	上车点经度
$h l a t$	上车点纬度
$L r, h$	乘客从叫车点到上车点的距离
$d j$	司机标识
$r m l o n$	乘客目的地经度
$r m l a t$	乘客目的地纬度
$L h, m$	司机从上车点到乘客目的地的距离
$d l o n$	司机当前位置经度
$d l a t$	司机当前位置纬度
$L d, h$	司机从当前位置到上车点的接驾距离
$v k i$	上车点的瞬时速度
$v - k$	上车点的平均速度
$a k 2$	上车点的速度方差

图1 算法架构图

Fig.1 Algorithm architecture

图2 载客事件图

Fig.2 Passenger incident diagram

图3 DBSCAN算法示意图

Fig.3 Schematic diagram of DBSCAN algorithm

图4 点到线匹配

Fig.4 Point to line matching

图5 控制订单量流程图

Fig.5 Flow chart of order quantity control

表2 实验环境

Table 2 Experimental environment

名称	环境
操作系统	Windows 10
CPU	Intel^®Core^TM i5-10210UCPU@1.60 GHz
CPU核数	6
内存/GB	16
Python版本	Python3.7

表3 参数设置

Table 3 Parameter setting

参数	含义	数值
$ξ p a s$	上车点分配人数阈值	5
$k / m i n$	时间间隔	1
$r / m$	误差半径	1
$R l e n$	乘客数量	100
$D l e n$	司机数量	100
$Z$	扫描半径	30
$∂$	$L h, m$ 所占权重	0.4
$θ$	$L d, h$ 所占权重	0.6
$λ e$	$e$ 所占权重	0.5
$λ u$	$u$ 所占权重	0.5

表3 参数设置

Table 3 Parameter setting

参数	含义	数值
$ξ p a s$	上车点分配人数阈值	5
$k / m i n$	时间间隔	1
$r / m$	误差半径	1
$R l e n$	乘客数量	100
$D l e n$	司机数量	100
$Z$	扫描半径	30
$∂$	$L h, m$ 所占权重	0.4
$θ$	$L d, h$ 所占权重	0.6
$λ e$	$e$ 所占权重	0.5
$λ u$	$u$ 所占权重	0.5

表4 PPS实验权重设置

Table 4 Weight setting in PPS experiment

参数	含义	数值
$α$	乘客步行收益权重	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

图6 乘客2推荐结果

Fig.6 Passenger 2 recommendation results

图7 乘客2收益对比

Fig.7 Revenue comparison of passenger 2

图8 多乘客推荐结果

Fig.8 Multi-passenger recommendation results

表5 DPS实验权重设置

Table 5 Weight setting in DPS experiment

参数	含义	数值
$α$	乘客步行收益权重	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

图9 乘客2推荐结果

Fig.9 Passenger 2 recommendation results

图10 乘客2收益对比

Fig.10 Revenue comparison of passenger 2

图11 多乘客推荐结果

Fig.11 Multi-passenger recommendation results

图12 司乘收益分析图1

Fig.12 Driver and passenger income analysis figure 1

图13 司乘收益分析图2

Fig.13 Driver and passenger income analysis figure 2

图14 司乘收益分析图3

Fig.14 Driver and passenger income analysis figure 3

表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]	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^[3]	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

表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^[1]	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^[3]	10.99	16.65	1.00	1.29	9.68	0.07	20.48	55.09	1.51	32.76	66.67	12.14

图15 时间对比图

Fig.15 Time comparison chart

图16 敏感度分析

Fig.16 Sensitivity analysis

参考文献 18

[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.

时空轨迹和复合收益的动态上车点推荐

Dynamic Pickup-Point Recommendation Based on Spatiotemporal Trajectory and Hybrid Gain Evaluation

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 23

参考文献 18

相关文章 11

编辑推荐

Metrics

[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.