Profitable taxi route recommendation considering demand

doi:10.3785/j.issn.1008-973X.2024.06.013

Journal of ZheJiang University (Engineering Science)

2024, Vol. 58

Issue (6): 1233-1242 DOI: 10.3785/j.issn.1008-973X.2024.06.013

Profitable taxi route recommendation considering demand

Qin WANG(

),Qingchang LU*(

),Jianyu LI,Zhangxin WANG,Tu ZHANG

School of Electronics and Control Engineering, Chang’an University, Xi’an 710064, China

Download:

HTML

PDF(1685KB) HTML
Export: BibTeX | EndNote (RIS)

Abstract

The existing research neglects the income earned by taxi driver when picking up the next passenger and recommends route with a relatively low probability of picking up for taxi. In response to the above problem, the taxi route recommendation problem based on mobile sequential recommendation was modeled, and an improved model for profitable taxi route recommendation based on mobile sequential recommendation (PMSR) considering the next passenger’s income was proposed. An improved model for profitable taxi route recommendation based on mobile sequential recommendation considering demand (PMSR-D) was proposed, considering the impact of the demand for pick-up point on the likelihood of taxi successfully picking up passenger at pick-up point. The density-based spatial clustering of applications with noise (DBSCAN) algorithm, simulated annealing algorithm and greedy algorithm were used to verify the PMSR and PMSR-D models, based on the taxi GPS trajectory data in Shanghai. Results showed that the minimum expected fare at the pick-up points recommended by PMSR model was relatively high. From 7:00 to 10:00, the PMSR model had an average increase of 148.2% and 253.0% in picking up probability compared to the potential cruising distance (PTD) model and the route recommendation model based on temporal-spatial metric (RTS), respectively. From 13:00 to 16:00, the PMSR model had an average increase of 88.1% and 48.0% in picking up probability compared to the PTD and RTS model, respectively. This indicated that the PMSR model can recommend route with high expected fare and high picking up probability for taxi, which was superior to the PTD and RTS models. Compared with the PMSR model, the PMSR-D model added 125 and 20 potential passenger demands from 7:00 to 10:00 and 13:00 to 16:00, respectively, verifying the effectiveness of PMSR-D model.

Key words： taxi mobile sequential recommendation route recommendation trajectory data simulated annealing algorithm

Received: 29 July 2023 Published: 25 May 2024

CLC:

U 491

Fund: 国家自然科学基金资助项目(71971029)；陕西省自然科学基础计划资助项目(2021JC-28).

Corresponding Authors: Qingchang LU E-mail: 2021132066@chd.edu.cn;qclu@chd.edu.cn

	Service
	E-mail this article
	Add to my bookshelf
	Add to citation manager
	E-mail Alert
	RSS
	Articles by authors
	Qin WANG
	Qingchang LU
	Jianyu LI
	Zhangxin WANG
	Tu ZHANG

Cite this article:

Qin WANG,Qingchang LU,Jianyu LI,Zhangxin WANG,Tu ZHANG. Profitable taxi route recommendation considering demand. Journal of ZheJiang University (Engineering Science), 2024, 58(6): 1233-1242.

URL:

https://www.zjujournals.com/eng/10.3785/j.issn.1008-973X.2024.06.013 OR https://www.zjujournals.com/eng/Y2024/V58/I6/1233

考虑需求的出租车收益路线推荐

当前研究忽略出租车接载下一个乘客获得的收益，并且会为出租车推荐具有较低接客概率的路线. 针对以上问题，基于移动顺序推荐对出租车路线推荐问题进行建模，提出考虑出租车下一个乘客收益的出租车收益路线推荐（PMSR）的改进模型. 考虑到上客点的需求大小对出租车在上客点成功接载乘客的可能性的影响，提出考虑需求的出租车收益路线推荐（PMSR-D）的改进模型. 基于上海市出租车GPS轨迹数据，采用带噪声的基于密度的空间聚类(DBSCAN)算法、模拟退火算法和贪心算法对PMSR和PMSR-D模型进行验证. 结果表明，PMSR模型推荐路线的上客点的最低预期票价较高，其接客概率与潜在巡航距离（PTD）、基于时空矩阵的路线推荐（RTS）模型相比在7:00—10:00和13:00—16:00分别平均增加了148.2%、253.0%和88.1%、48.0%，表明PMSR模型能够为出租车推荐预期票价较高且接客概率更大的路线，优于PTD和RTS模型. 与PMSR模型相比，PMSR-D模型在7:00—10:00和13:00—16:00分别增加了125和20个潜在的乘客需求，验证了PMSR-D模型的有效性.

关键词： 出租车, 移动顺序推荐, 路线推荐, 轨迹数据, 模拟退火算法

Fig.1 Example diagram of profitable taxi route recommendation

Fig.2 Framework for taxi route recommendation algorithm

Tab.1 Example of taxi GPS trajectory data in Shanghai

Fig.3 Time-varying characteristic diagram of number of picking-up

Fig.4 Clustering results of picking up events during 7:00—10:00 on August 29, 2016

Fig.5 Clustering results of picking up events during 13:00—16:00 on August 29, 2016

Fig.6 Impact of number of potential picking-up points on running time of SA+GA, BFS and LCPS algorithms

Tab.2 Route recommendation result of PTD model during 7:00—10:00

Tab.3 Route recommendation result of RTS model during 7:00—10:00

Tab.4 Route recommendation result of PMSR model during 7:00—10:00

Tab.5 Route recommendation result of PTD model during 13:00—16:00

Tab.6 Route recommendation result of RTS model during 13:00—16:00

Tab.7 Route recommendation result of PMSR model during 13:00—16:00

Fig.7 Search time for recommended routes in different models during 7:00—10:00

Fig.8 Search distance for recommended routes in different models during 7:00—10:00

Fig.9 Search time for recommended routes in different models during 13:00—16:00

Fig.10 Search distance for recommended routes in different models during 13:00—16:00

Tab.8 Route recommendation result of PMSR-D model during 7:00—10:00

Tab.9 Route recommendation result of PMSR-D model during 13:00—16:00


[1]	WONG R C P, SZETO W Y An alternative methodology for evaluating the service quality of urban taxis[J]. Transport Policy, 2018, 69: 132- 140 doi: 10.1016/j.tranpol.2018.05.016

[2]	MA Y Y, CHEN K, XIAO Y Z, et al Does online ride-hailing service improve the efficiency of taxi market? evidence from Shanghai[J]. Sustainability, 2022, 14 (14): 8872 doi: 10.3390/su14148872

[3]	DONG X L, ZHANG M, ZHANG S, et al The analysis of urban taxi operation efficiency based on GPS trajectory big data[J]. Physica A: Statistical Mechanics and its Applications, 2019, 528: 121456 doi: 10.1016/j.physa.2019.121456

[4]	LI R M, YANG F H, LIU Z Y, et al Effect of taxis on emissions and fuel consumption in a city based on license plate recognition data: a case study in Nanning, China[J]. Journal of Cleaner Production, 2019, 215: 913- 925 doi: 10.1016/j.jclepro.2019.01.123

[5]	刘海玥, 蒋朝哲, 付川云, 等出租车超速行为道路因素随机系数空间模型构建[J]. 交通运输系统工程与信息, 2022, 22 (3): 140- 146 LIU Haiyue, JIANG Chaozhe, FU Chuanyun, et al Group-level random parameter spatial modeling for road factors of taxi speeding behavior[J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22 (3): 140- 146

[6]	BAO J, YANG Z, ZENG W L, et al Exploring the spatial impacts of human activities on urban traffic crashes using multi-source big data[J]. Journal of Transport Geography, 2021, 94: 103118 doi: 10.1016/j.jtrangeo.2021.103118

[7]	SHOU Z Y, DI X, YE J P, et al Optimal passenger-seeking policies on e-hailing platforms using Markov decision process and imitation learning[J]. Transportation Research Part C: Emerging Technologies, 2020, 111: 91- 113 doi: 10.1016/j.trc.2019.12.005

[8]	廖祝华, 张健, 刘毅志, 等基于稀疏轨迹数据的出租车载客区域推荐[J]. 电子学报, 2020, 48 (11): 2178- 2185 LIAO Zhuhua, ZHANG Jian, LIU Yizhi, et al Taxi pick-up area recommendation based on sparse trajectory data[J]. Acta Electronica Sinica, 2020, 48 (11): 2178- 2185

[9]	FENG X Y, SUN H J, WU J J, et al Understanding detour behavior in taxi services: a combined approach[J]. Transportation Research Part C: Emerging Technologies, 2022, 145: 103950 doi: 10.1016/j.trc.2022.103950

[10]	ZHENG Z, RASOULI S, TIMMERMANS H Modeling taxi driver search behavior under uncertainty[J]. Travel Behaviour and Society, 2021, 22: 207- 218 doi: 10.1016/j.tbs.2020.09.008

[11]	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 . Washington, DC: KDD, 2010: 899-908.

[12]	GE Y, LI H Y, TUZHILIN A Route recommendations for intelligent transportation services[J]. IEEE Transactions on Knowledge and Data Engineering, 2019, 33 (3): 1169- 1182

[13]	LUO Z W, LV H M, FANG F, et al Dynamic taxi service planning by minimizing cruising distance without passengers[J]. IEEE Access, 2018, 6: 70005- 70016 doi: 10.1109/ACCESS.2018.2881419

[14]	XIAO K L, YE Z Y, ZHANG L H, et al Multi-user mobile sequential recommendation for route optimization[J]. ACM Transactions on Knowledge Discovery from Data, 2020, 14 (5): 1- 28

[15]	HUANG J B, HUANGFU X J, SUN H L, et al Backward path growth for efficient mobile sequential recommendation[J]. IEEE Transactions on Knowledge and Data Engineering, 2015, 27 (1): 46- 60 doi: 10.1109/TKDE.2014.2298012

[16]	YE Z Y, XIAO K L, GE Y, et al Applying simulated annealing and parallel computing to the mobile sequential recommendation[J]. IEEE Transactions on Knowledge and Data Engineering, 2019, 31 (2): 243- 256 doi: 10.1109/TKDE.2018.2827047

[17]	LIANG F, CHEN H L, LIN K, et al Route recommendation based on temporal-spatial metric[J]. Computers and Electrical Engineering, 2022, 97: 107549 doi: 10.1016/j.compeleceng.2021.107549

[18]	高瞻, 余辰, 向郑涛, 等基于网格化的出租车空载寻客路径推荐[J]. 计算机应用与软件, 2019, 36 (5): 281- 288 GAO Zhan, YU Chen, XIANG Zhengtao, et al Grid-based route recommendation of no-load taxi[J]. Computer Applications and Software, 2019, 36 (5): 281- 288

[19]	FENG R, YAO B Z, GU X N, et al Environmental benefits mining based on data-driven taxi cruising recommendation strategy[J]. Journal of Cleaner Production, 2021, 326: 129376 doi: 10.1016/j.jclepro.2021.129376

[20]	王桐, 高山, 龚慧雯, 等基于分时MDP的出租车载客预测推荐技术研究[J]. 通信学报, 2021, 42 (2): 37- 51 WANG Tong, GAO Shan, GONG Huiwen, et al 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]	TRAN D H, LEYMAN P, CAUSMAECKER P D Adaptive passenger-finding recommendation system for taxi drivers with load balancing problem[J]. Computers and Industrial Engineering, 2022, 169: 108187 doi: 10.1016/j.cie.2022.108187

[22]	陈冬梅, 卜霄菲, 黄河, 等基于候客点规划的空闲出租车路线推荐算法[J]. 计算机工程, 2022, 48 (2): 297- 305 CHEN Dongmei, BU Xiaofei, HUANG He, et al Idle taxi route recommendation algorithm based on waiting point planning[J]. Computer Engineering, 2022, 48 (2): 297- 305

[23]	上海发布. 《上海市市民价格信息指南》[EB/OL]. (2014-01-22). https://mp.weixin.qq.com/s/U-McsTfk5gU S0mWSSDI7-g.

[1]	Jia-bi LI,Shu-guang HAN. Unmanned logistics distribution route considering customer level and time-varying road conditions[J]. Journal of ZheJiang University (Engineering Science), 2023, 57(10): 2018-2027.

[2]	Wen-tao SHI,Hong-yan LI,Jian-guo CUI,Yi-yang MA,Chong ZHANG,Ying-hong DONG. DMA partition method of urban water distribution network under extreme small depressurization space[J]. Journal of ZheJiang University (Engineering Science), 2022, 56(8): 1533-1541.

[3]	Xiao PAN,Yun-dan YANG,Xin YAO,Lei WU,Shu-hai WANG. Personalized potential route recommendation based on hidden Markov model[J]. Journal of ZheJiang University (Engineering Science), 2020, 54(9): 1736-1745.

[4]	HUANG Jia-jun, TENG Lai, ZHANG Chao-jie, WANG Chun-hui, PIAO Cheng-yong. I/Q imbalance calibration based on simulated annealing algorithm[J]. Journal of ZheJiang University (Engineering Science), 2018, 52(11): 2218-2225.

[5]	YUAN You-wei-, YU Jia, ZHENG Hong-sheng, WANG Jiao-jiao. Cloud workflow scheduling algorithm based on novelty ranking and multi-quality of service[J]. Journal of ZheJiang University (Engineering Science), 2017, 51(6): 1190-1196.

[6]	CHENG Zhun,LU Zhi xiong,GONG Jia hui,DIAO Xiu yong. Transfer function of steering system and acquisition method of ideal steering ratio[J]. Journal of ZheJiang University (Engineering Science), 2016, 50(7): 1276-1283.

[7]	LIU Ai-jun, YANG Yu, LI Fei, XING Qing-song, LU Hui, ZHANG Yu-dong. Chaotic simulated annealing particle swarm optimization algorithm research and its application[J]. Journal of ZheJiang University (Engineering Science), 2013, 47(10): 1722-1730.

[8]	LI Jing-chun, YANG Hong-dong, YANG Yang, QUAN Feng-xi. Growth and characterization of local biaxial strained SiGe[J]. Journal of ZheJiang University (Engineering Science), 2011, 45(6): 1048-1051.

Viewed

Full text

Abstract

Cited

Shared

Discussed