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

doi:10.3778/j.issn.1673-9418.2012039

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

摘要：

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

CLC Number:

U495
TP301.6

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.

郭羽含, 刘秋月. 时空轨迹和复合收益的动态上车点推荐[J]. 计算机科学与探索, 2022, 16(7): 1611-1622.

Figures/Tables 23

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$	上车点的速度方差

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$	上车点的速度方差

Fig.1 Algorithm architecture

Fig.2 Passenger incident diagram

Fig.3 Schematic diagram of DBSCAN algorithm

Fig.4 Point to line matching

Fig.5 Flow chart of order quantity control

Table 2 Experimental environment

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

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

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

Table 4 Weight setting in PPS experiment

参数	含义	数值
$α$	乘客步行收益权重	0.35
$β$	司机驾驶收益权重	0.23
$ϕ$	上车点路况指标权重	0.27
$γ$	上车点安全性指标权重	0.15

Table 4 Weight setting in PPS experiment

参数	含义	数值
$α$	乘客步行收益权重	0.35
$β$	司机驾驶收益权重	0.23
$ϕ$	上车点路况指标权重	0.27
$γ$	上车点安全性指标权重	0.15

Fig.6 Passenger 2 recommendation results

Fig.7 Revenue comparison of passenger 2

Fig.8 Multi-passenger recommendation results

Table 5 Weight setting in DPS experiment

参数	含义	数值
$α$	乘客步行收益权重	0.126
$β$	司机驾驶收益权重	0.281
$ϕ$	上车点路况指标权重	0.525
$γ$	上车点安全性指标权重	0.068

Table 5 Weight setting in DPS experiment

参数	含义	数值
$α$	乘客步行收益权重	0.126
$β$	司机驾驶收益权重	0.281
$ϕ$	上车点路况指标权重	0.525
$γ$	上车点安全性指标权重	0.068

Fig.9 Passenger 2 recommendation results

Fig.10 Revenue comparison of passenger 2

Fig.11 Multi-passenger recommendation results

Fig.12 Driver and passenger income analysis figure 1

Fig.13 Driver and passenger income analysis figure 2

Fig.14 Driver and passenger income analysis figure 3

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

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

Fig.15 Time comparison chart

Fig.16 Sensitivity analysis

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