基于分时MDP的出租车载客预测推荐技术研究

doi:10.11959/j.issn.1000-436x.2021002

通信学报 ›› 2021, Vol. 42 ›› Issue (2): 37-51.doi: 10.11959/j.issn.1000-436x.2021002

基于分时MDP的出租车载客预测推荐技术研究

王桐¹^,², 高山¹^,², 龚慧雯¹^,², 孙博¹^,²

¹ 哈尔滨工程大学信息与通信工程学院，黑龙江哈尔滨 150001
² 哈尔滨工程大学先进船舶通信与信息技术重点实验室，黑龙江哈尔滨 150001

修回日期:2020-08-20 出版日期:2021-02-25 发布日期:2021-02-01
作者简介:王桐（1977- ），男，黑龙江哈尔滨人，博士，哈尔滨工程大学教授、博士生导师，主要研究方向为车联网建模与仿真等。
高山（1986- ），男，黑龙江伊春人，博士，哈尔滨工程大学讲师、硕士生导师，主要研究方向为人工智能、车联网等。
龚慧雯（1997- ），女，河南南阳人，哈尔滨工程大学硕士生，主要研究方向为大数据分析、机器学习算法等。
孙博（1994- ），男，河北张家口人，哈尔滨工程大学硕士生，主要研究方向为数据挖掘、物联网等。
基金资助:
国家自然科学基金资助项目(61102105);国家自然科学基金资助项目(51779050);国家重点研发计划基金资助项目(2016YFB0700100);哈尔滨市青年后备人才基金资助项目(2017RAQXJ036);中央高校基本科研业务费资金资助项目(HEUCFG201831);中央高校基本科研业务费资金资助项目(3072020CF0815)

Research on forecast and recommendation technology of taxi passengers based on time-varying Markov decision process

Tong WANG¹^,², Shan GAO¹^,², Huiwen GONG¹^,², Bo SUN¹^,²

¹ College of Information and Communication Engineering, Harbin Engineering University, Harbin 150001, China
² Key Laboratory of Advanced Ship Communication and Information Technology, Harbin Engineering University, Harbin 150001, China

Revised:2020-08-20 Online:2021-02-25 Published:2021-02-01
Supported by:
The National Natural Science Foundation of China(61102105);The National Natural Science Foundation of China(51779050);The National Key Research and Development Program of China(2016YFB0700100);The Harbin Science Fund for Young Reserve Talents(2017RAQXJ036);Fun-damental Research Funds for the Central Universities(HEUCFG201831);Fun-damental Research Funds for the Central Universities(3072020CF0815)

摘要/Abstract

摘要：

针对出租车盲目寻客导致空载率高的问题，提出了一种出租车载客热点推荐策略，以最大程度优化匹配乘客过程，提高寻客效率。基于出租车历史轨迹数据，结合热点乘客信息的时间序列特性，提出基于循环神经网络的分段预测（SPBR）算法，以及基于分时马尔可夫决策过程（TMDP）的载客推荐模型。实验表明，SPBR算法预测结果的RMSE比SVR、CART和BPNN等算法分别降低了67.6%、71.1%和64.5%； TMDP模型出租车期望回报比历史期望提升了35.9%。

关键词: 出租车空载率, 分时马尔可夫决策过程, 热点预测, 分段预测方法, 载客推荐模型

Abstract:

To solve the problems of unloading rate caused by blind passenger search of taxis, the hotspot recommendation strategy of taxi passengers was proposed.The proposed strategy could optimize the process of matching passengers to the greatest extent to increase the efficiency of passenger search.Based on the historical trajectory data of taxis and the time series characteristics of hotspot passenger information, a segment prediction method was proposed based on recurrent neural network (SPBR) and a passenger recommendation model was proposed based on time-varying Markov decision process (TMDP).Experimental results show that the RMSE predicted by SPBR algorithm is 67.6%, 71.1% and 64.5% lower than the SVR, CART and BPNN algorithms.The expected return of taxis based on the TMDP algorithm is 35.9% higher than historical expectations.

Key words: taxi empty loading rate, time-varying Markov decision process, hotspot prediction, segment prediction me-thod, passenger recommendation model

中图分类号:

TN911.22

王桐, 高山, 龚慧雯, 孙博. 基于分时MDP的出租车载客预测推荐技术研究[J]. 通信学报, 2021, 42(2): 37-51.

Tong WANG, Shan GAO, Huiwen GONG, Bo SUN. Research on forecast and recommendation technology of taxi passengers based on time-varying Markov decision process[J]. Journal on Communications, 2021, 42(2): 37-51.

图/表 21

图1

表1

图2

图3

图4

表2

TMDP中的转移概率矩阵 P s i a "

区域	$s_{0}^{0}$	$s_{0}^{1}$	…	$s_{0}^{95}$	$s_{1}^{0}$	…	$s_{99}^{95}$
$s_{0}^{0}$	$P_{0, 0}^{0, 0}$	$P_{0, 0}^{0, 1}$	…	$P_{0, 0}^{0, 95}$	$P_{0, 1}^{0, 0}$	…	$P_{0, 99}^{0, 95}$
$s_{0}^{1}$	$P_{0, 0}^{1, 0}$	$P_{0, 0}^{1, 1}$	…	$P_{0, 0}^{1, 95}$	$P_{0, 1}^{1, 0}$	…	$P_{0, 99}^{1, 95}$
$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$
$s_{0}^{95}$	$P_{0, 0}^{95, 0}$	$P_{0, 0}^{95, 1}$	…	$P_{0, 0}^{95, 95}$	$P_{0, 1}^{95, 0}$	…	$P_{0, 99}^{95, 95}$
$s_{1}^{0}$	$P_{1, 0}^{0, 0}$	$P_{1, 0}^{0, 1}$	…	$P_{1, 0}^{0, 95}$	$P_{1, 1}^{0, 0}$	…	$P_{1, 99}^{0, 95}$
$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$

表2

图5

表3

TMDP最优策略矩阵形式"

区域	T₀	T₁	T₂	…	T₉₄	T₉₅
s₀	1	1	2	…	1	1
s₁	1	2	1	…	2	1
s₂	2	1	1	…	1	2
$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$
s₉₈	1	2	2	…	2	2
s₉₉	1	2	1	…	2	1

表3

图6

图7

图8

图9

图10

图11

图12

图13

图14

表4

TMDP推荐结果策略"

区域	T₀	T₁	T₂	…	T₉₄	T₉₅
s₀	1	2	2	…	1	1
s₁	2	1	2	…	1	2
s₂	1	1	1	…	1	2
$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$
s₉₈	2	2	1	…	1	1
s₉₉	1	1	1	…	1	1

表4

表5

TMDP最大期望回报矩阵"

区域	T₀	T₁	T₂	…	T₉₄	T₉₅
s₀	24.8	9.0	18.1	…	87.5	175.0
s₁	21.8	16.1	10.1	…	50.1	20.1
s₂	234.8	170.4	208.1	…	259.3	181.2
$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$
s₉₈	11.1	7.8	7.0	…	22.4	3.9
s₉₉	279.8	323.0	484.0	…	647.5	156.5

表5

表6

历史期望回报矩阵"

区域	T₀	T₁	T₂	…	T₉₄	T₉₅
s₀	13.6	0	2.7	…	17.6	61.3
s₁	1.4	2.3	7.1	…	8.4	0.5
s₂	45.6	10.9	18.2	…	27.2	8.7
$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$
s₉₈	0.4	2.1	0.1	…	2.3	11.1
s₉₉	61.8	83.1	72.3	…	242.9	19.5

表6

图15

参考文献 35

[1]	WANG T , CAO Y , ZHOU Y ,et al. A survey on geographic routing protocols in delay/disruption tolerant networks[J]. International Journal of Distributed Sensor Networks, 2016,12(2): 3174670.
[2]	ZHANG D , HE T , LIN S ,et al. Dmodel:online taxicab demand model from big sensor data in a roving sensor network[C]// 2014 IEEE International Congress on Big Data. Piscataway:IEEE Press, 2014: 152-159.
[3]	HUNTER T , HERRING R , ABBEEL P ,et al. Path and travel time inference from GPS probe vehicle data[J]. NIPS Analyzing Networks and Learning with Graphs, 2009,12(1): 2.
[4]	MEYER R F , WOLFE H B . The organization and operation of a taxi fleet[J]. Naval Research Logistics Quarterly, 1961,8(2): 137-150.
[5]	YAMAMOTO K , UESUGI K , WATANABE T . Adaptive routing of cruising taxis by mutual exchange of pathways[C]// International Conference on Knowledge-Based and Intelligent Information and Engineering Systems. Berlin:Springer, 2008: 559-566.
[6]	POWELL J W , HUANG Y , BASTANI F ,et al. Towards reducing taxicab cruising time using spatio-temporal profitability maps[C]// International Symposium on Spatial and Temporal Databases. Berlin:Springer, 2011: 242-260.
[7]	YUAN J , ZHENG Y , XIE X ,et al. Driving with knowledge from the physical world[C]// Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining. New York:ACM Press, 2011: 316-324.
[8]	SONG C , YAN X , STEPHEN N ,et al. Hidden Markov model and driver path preference for floating car trajectory map matching[J]. IET Intelligent Transport Systems, 2018,12(10): 1433-1441.
[9]	王媛, 梁泉, 翁剑成 ,等. 基于特征图谱的区域出租车出行需求分布特征研究[J]. 交通工程, 2018,18(1): 1-6.
	WANG Y , LIANG Q , WENG J C ,et al. Study on the regional taxi travel demand characteristics based on feature graph[J]. Journal of Transportation Engineering, 2018,18(1): 1-6.
[10]	曾艳秋, 洪成蹊 . 基于兴趣度和k均值聚类算法的热点区域分析[J]. 宜春学院学报, 2018,40(12): 47-49.
	ZENG Y Q , HONG C X . Hot regions analysis based on density of vehicles and k means clustering[J]. Journal of Yichun University, 2018,40(12): 47-49.
[11]	王明 . 基于出租车 GPS 数据的载客热点可视化的研究与应用[D]. 太原:中北大学, 2018.
	WANG M . Research and application of passenger hot spot visualization based on taxi GPS data[D]. Taiyuan:North University of China, 2018.
[12]	李佳蓉, 夏昊, 张迎 ,等. 城市居民出行 O/D 时空分布特征的轨迹数据提取[J]. 测绘科学, 2020,45(2): 150-158.
	LI J R , XIA H , ZHANG Y ,et al. Trajectory data extract of O/D temporal and spatial distribution of urban residents[J]. Science of Surveying and Mapping, 2020,45(2): 150-158.
[13]	方琪, 王山东, 朱鸿博 ,等. 基于决策图的城市热点区域提取[J]. 测绘与空间地理信息, 2018,41(11): 135-137.
	FANG Q , WANG S D , ZHU H B ,et al. City hot spot extraction based on decision graph[J]. Geomatics ＆ Spatial Information Technology, 2018,41(11): 135-137.
[14]	胡浩, 闫伟, 李泓明 . 基于组合预测方法的城市道路短时交通流预测[J]. 工业工程与管理, 2019,24(3): 107-115.
	HU H , YAN W , LI H M . Short-term traffic flow prediction of urban road based on combination forecasting method[J]. Industrial Engineering and Management, 2019,24(3): 107-115.
[15]	OU J , XIA J , WU Y J ,et al. Short-term traffic flow forecasting for urban roads using data-driven feature selection strategy and bias-corrected random forests[J]. Transportation Research Record, 2017,2645(1): 157-167.
[16]	孔蕙心 . 城市客流分布与出租车出行路线推荐算法的研究[D]. 北京:北京邮电大学, 2015.
	KONG H X . Research on urban passenger flow distribution and taxi route recommendation algorithm[D]. Beijing:Beijing University of Posts and Telecommunications, 2015.
[17]	HU H , WU Z , MAO B ,et al. Pick-up tree based route recommendation from taxi trajectories[C]// International Conference on Web-age Information Management. Berlin:Springer, 2012: 471-483.
[18]	DAI J , YANG B , GUO C ,et al. Personalized route recommendation using big trajectory data[C]// 2015 IEEE 31st International Conference on Data Engineering. Piscataway:IEEE Press, 2015: 543-554.
[19]	GE Y , XIONG H , TUZHILIN A ,et al. An energy-efficient mobile recommender system[C]// Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM Press, 2010: 899-908.
[20]	SUN Y , YU X , BIE R ,et al. Discovering time-dependent shortest path on traffic graph for drivers towards green driving[J]. Journal of Network and Computer Applications, 2017,83: 204-212.
[21]	RONG H , ZHOU X , YANG C ,et al. The rich and the poor:a Markov decision process approach to optimizing taxi driver revenue efficiency[C]// Proceedings of the 25th ACM International on Conference on Information and Knowledge Management. New York:ACM Press, 2016: 2329-2334.
[22]	刘丽 . 基于出租车GPS数据的高效益寻客推荐策略研究[D]. 杭州:浙江大学, 2017.
	LIU L . Research on high-efficiency searching recommendation strategy based on taxi GPS data[D]. Hangzhou:Zhejiang University, 2017.
[23]	QIAN S , ZHU Y , LI M . Smart recommendation by mining large-scale GPS traces[C]// 2012 IEEE Wireless Communications and Networking Conference (WCNC) Piscataway:IEEE Press, 2012: 3267-3272.
[24]	RONG H , WANG Z , ZHENG H ,et al. Mining efficient taxi operation strategies from large scale geo-location data[J]. IEEE Access, 2017,5: 25623-25634.
[25]	PUTRI F , SONG G , KWON J ,et al. DISPAQ:distributed profitable-area query from big taxi trip data[J]. Sensors, 2017,17(10): 2201.
[26]	YUAN J , ZHENG Y , XIE X ,et al. T-drive:enhancing driving directions with taxi drivers’ intelligence[J]. IEEE Transactions on Knowledge and Data Engineering, 2011,25(1): 220-232.
[27]	YUAN N J , ZHENG Y , ZHANG L ,et al. T-finder:a recommender system for finding passengers and vacant taxis[J]. IEEE Transactions on Knowledge and Data Engineering, 2012,25(10): 2390-2403.
[28]	朱本常 . 基于时间序列的网约车在线司机与乘客发单的供需预测[D]. 武汉:华中科技大学, 2019.
	ZHU B C . Forecast of supply and demand of online drivers and passengers billing based on time series[D]. Wuhan:Huazhong University of Science and Technology, 2019.
[29]	QIAN S , CAO J ， MOU?L F L ,et al. SCRAM:a sharing considered route assignment mechanism for fair taxi route recommendations[C]// Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM Press, 2015: 955-964.
[30]	HUANG Y , ZHAO L , VAN WOENSEL T ,et al. Time-dependent vehicle routing problem with path flexibility[J]. Transportation Research Part B:Methodological, 2017,95: 169-195.
[31]	LEI T , WANG S , LI J ,et al. A cooperative route choice approach via virtual vehicle in IoV[J]. Vehicular Communications, 2017,9: 281-287.
[32]	胡昊然 . 基于 Pick-up 树的路径推荐研究[D]. 南京:南京大学, 2013.
	HU H R . Research on Path Recommendation Based on Pickup Tree[D]. Nanjing:Nanjing University, 2013.
[33]	XIAO Y , WEI L . Study on revenue distribution of passenger platform under the integrated transportation value chain[C]// 2016 International Conference on Education,Sports,Arts and Management Engineering. Paris:Atlantis Press, 2016:doi.org/10.2991/icesame-16.2016.220.
[34]	毕硕本, 万蕾, 杨树亮 ,等. 基于 GPS 数据的南京出租车上下客时间特征及热点时空分布[J]. 中国科技论文, 2018(9): 10.
	BI S B , WAN L , YANG S L ,et al. Characteristics of Nanjing taxi boarding time based on gps data and temporal and spatial distribution of hot spots[J]. China Science and Technology Papers, 2018(9): 10.
[35]	丁涛杰, 史殿习, 李永谋 . 基于出租车 GPS 数据的道路平均速度估计方法[J]. 计算机技术与发展, 2015,25(7): 15-19.
	DING T J , SHI D X , LI Y M . Road average speed estimation method based on taxi GPS data[J]. Computer Technology and Development, 2015,25(7): 15-19.

出租车编号	时间戳	纬度字段	经度字段	载客状态
000313…e4fc71	1451518112	3996019	11641702	0
000313…e4fc71	1451582834	3994592	11646645	10000000
000449…45a4c4	1451444563	3997385	11639662	10000000
000a38…3d6ac7	1451440546	3980436	11635363	0
001996…5221e2	1451439580	3953281	11627752	10000000

基于分时MDP的出租车载客预测推荐技术研究

Research on forecast and recommendation technology of taxi passengers based on time-varying Markov decision process

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 21

参考文献 35

相关文章 15

Metrics

推荐阅读 0

[1]	李君, 周乐佳, 李正权, 吉茹, 诸锦涛, 刘兴鑫, 刘子怡. 基于GRU网络辅助和路径度量交换的极化码SCLF算法[J]. 通信学报, 2023, 44(6): 223-237.
[2]	张平, 牛凯, 姚圣时, 戴金晟. 面向未来的语义通信：基本原理与实现方法[J]. 通信学报, 2023, 44(5): 1-14.
[3]	郭锐, 刘洋. 基于简化序列重复节点的极化码快速串行抵消译码算法[J]. 通信学报, 2023, 44(5): 158-168.
[4]	宋鑫, 倪淑燕, 张喆, 廖育荣, 雷拓峰. 面向不等差错保护的低误码平台LT编码算法[J]. 通信学报, 2022, 43(6): 85-97.
[5]	宋鑫, 程乃平, 倪淑燕, 廖育荣, 雷拓峰. 采用定长节点分类窗口的低误码平台LT编码算法[J]. 通信学报, 2021, 42(9): 31-42.
[6]	牛凯,戴金晟,朴瑨楠. 面向6G的极化码与极化处理[J]. 通信学报, 2020, 41(5): 9-17.
[7]	王海荣, 董健, 王玉辉. 大规模MIMO系统中基于谱分离的导频去污染[J]. 通信学报, 2020, 41(4): 197-205.
[8]	孙彦景,杨俊秋,陈岩,王艳芬,陈晓晶,刘丰祯,孙智. 面向工业物联网的IEEE 802.11ah协议RAW在线式重分组方法[J]. 通信学报, 2020, 41(4): 92-101.
[9]	王卫东,王程,王慧文,徐玭. 基于流量预测的物联网卫星节点动态缓存分配路由策略[J]. 通信学报, 2020, 41(2): 25-35.
[10]	卢新明,闫长青,袁照平. 掘进机精准定位方法与掘进机器人系统[J]. 通信学报, 2020, 41(2): 58-65.
[11]	李晖,叶铭,童强,程杰,王力杰. 系统极化码和非系统极化码的性能比较[J]. 通信学报, 2019, 40(6): 203-209.
[12]	马啸,吉眉颖,陈声晓. 分组马尔可夫叠加传输在非高斯脉冲信道上的性能研究[J]. 通信学报, 2019, 40(3): 109-115.
[13]	刘剑飞,何利平,陶颖,刘迪,曾祥烨,王蒙军. 大规模MIMO系统中低复杂度的码本搜索方法[J]. 通信学报, 2019, 40(1): 79-86.
[14]	马林华,刘士平,胡星,黄天宇,徐彬. 系统极化码低复杂度编码优化方案[J]. 通信学报, 2018, 39(7): 132-138.
[15]	易本顺,姚渭箐. LT码度分布改进及在认知无线电链路保持中的应用[J]. 通信学报, 2018, 39(4): 76-83.