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

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

Abstract

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

CLC Number:

TN911.22

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.

Figures/Tables 21

区域	$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}$
$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$

区域	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

区域	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

区域	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

区域	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

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

Metrics

Recommended 0

No Suggested Reading articles found!

出租车编号	时间戳	纬度字段	经度字段	载客状态
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

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 21

References 35

Related Articles 15

Metrics

Recommended 0

[1]	Jun LI, Lejia ZHOU, Zhengquan LI, Ru JI, Jintao ZHU, Xingxin LIU, Ziyi LIU. SCLF algorithm for polar code based on GRU network assistance and path metric exchange [J]. Journal on Communications, 2023, 44(6): 223-237.
[2]	Ping ZHANG, Kai NIU, Shengshi YAO, Jincheng DAI. Semantic communications for future: basic principle and implementation methodology [J]. Journal on Communications, 2023, 44(5): 1-14.
[3]	Rui GUO, Yang LIU. Simplified sequence repetition nodes-based fast successive cancellation decoding algorithm for polar code [J]. Journal on Communications, 2023, 44(5): 158-168.
[4]	Xin SONG, Shuyan NI, Zhe ZHANG, Yurong LIAO, Tuofeng LEI. Low error floor LT coding algorithm for unequal error protection [J]. Journal on Communications, 2022, 43(6): 85-97.
[5]	Xin SONG, Naiping CHENG, Shuyan NI, Yurong LIAO, Tuofeng LEI. Low error floor LT coding algorithm by using fixed-length node classification window [J]. Journal on Communications, 2021, 42(9): 31-42.
[6]	Kai NIU,Jinchen DAI,Jinnan PIAO. Polar codes and polar processing for 6G wireless systems [J]. Journal on Communications, 2020, 41(5): 9-17.
[7]	Hairong WANG, Jian DONG, Yuhui WANG. Pilot decontamination based on spectrum separation in massive MIMO system [J]. Journal on Communications, 2020, 41(4): 197-205.
[8]	Yanjing SUN,Junqiu YANG,Yan CHEN,Yanfen WANG,Xiaojing CHEN,Fengzhen LIU,Zhi SUN. RAW online regrouping method in IEEE 802.11ah protocol for industrial Internet of things [J]. Journal on Communications, 2020, 41(4): 92-101.
[9]	Weidong WANG,Cheng WANG,Huiwen WANG,Pin XU. Dynamic cache allocation routing strategy of Internet of things satellite node based on traffic prediction [J]. Journal on Communications, 2020, 41(2): 25-35.
[10]	Xinming LU,Changqing YAN,Zhaoping YUAN. Precisely positioning method for roadheaders and robotic roadheader system [J]. Journal on Communications, 2020, 41(2): 58-65.
[11]	LI Hui,YE Ming,TONG Qiang,CHENG Jie,WANG Lijie. Performance comparison of systematic polar code and non-systematic polar code [J]. Journal on Communications, 2019, 40(6): 203-209.
[12]	Xiao MA,Meiying JI,Shengxiao CHEN. Performance of block Markov superposition transmission over non-Gaussian impulsive channels [J]. Journal on Communications, 2019, 40(3): 109-115.
[13]	Jianfei LIU,Liping HE,Ying TAO,Di LIU,Xiangye ZENG,Mengjun WANG. Low complexity codebook search method in massive MIMO system [J]. Journal on Communications, 2019, 40(1): 79-86.
[14]	Linhua MA,Shiping LIU,Xing HU,Tianyu HUANG,Bin XU. Optimizing low complexity encoding method for systematic polar code [J]. Journal on Communications, 2018, 39(7): 132-138.
[15]	Benshun YI,Weiqing YAO. Degree distribution optimization for LT codes and its application in link maintenance of cognitive radio [J]. Journal on Communications, 2018, 39(4): 76-83.