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

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

浙江大学学报(工学版)

2024, Vol. 58

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

土木工程、交通工程

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

王琴(

),路庆昌*(

),李建宇,王张鑫,张图

长安大学电子与控制工程学院，陕西西安 710064

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

全文: PDF(1685 KB) HTML

摘要：

当前研究忽略出租车接载下一个乘客获得的收益，并且会为出租车推荐具有较低接客概率的路线. 针对以上问题，基于移动顺序推荐对出租车路线推荐问题进行建模，提出考虑出租车下一个乘客收益的出租车收益路线推荐（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模型的有效性.

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

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

收稿日期: 2023-07-29 出版日期: 2024-05-25

CLC:

U 491

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

通讯作者: 路庆昌 E-mail: 2021132066@chd.edu.cn;qclu@chd.edu.cn

作者简介: 王琴（1999—），女，硕士生，从事交通大数据处理与分析研究. orcid.org/0009-0005-1061-4510. E-mail：2021132066@chd.edu.cn

	服务
	把本文推荐给朋友
	加入引用管理器
	E-mail Alert
	作者相关文章
	王琴
	路庆昌
	李建宇
	王张鑫
	张图

引用本文:

王琴,路庆昌,李建宇,王张鑫,张图. 考虑需求的出租车收益路线推荐[J]. 浙江大学学报(工学版), 2024, 58(6): 1233-1242.

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.

链接本文:

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

图 1 出租车收益路线推荐示例图

图 2 出租车路线推荐算法框架

表 1 上海市出租车GPS轨迹数据示例

图 3 上车事件数量时变特性图

图 4 2016年8月29日7:00—10:00上车事件聚类结果

图 5 2016年8月29日13:00—16:00上车事件聚类结果

图 6 潜在上客点数量对SA+GA、BFS和LCPS运行时间的影响

表 2 7:00—10:00 PTD模型路线推荐结果

表 3 7:00—10:00 RTS模型路线推荐结果

表 4 7:00—10:00 PMSR模型路线推荐结果

表 5 13:00—16:00 PTD模型路线推荐结果

表 6 13:00—16:00 RTS模型路线推荐结果

表 7 13:00—16:00 PMSR模型路线推荐结果

图 7 7:00—10:00不同模型推荐路线的搜索时间

图 8 7:00—10:00不同模型推荐路线的搜索距离

图 9 13:00—16:00不同模型推荐路线的搜索时间

图 10 13:00—16:00不同模型推荐路线的搜索距离

表 8 7:00—10:00 PMSR-D模型路线推荐结果

表 9 13:00—16:00 PMSR-D模型路线推荐结果

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]	李家碧,韩曙光. 考虑客户等级和时变路况的无人物流配送路径[J]. 浙江大学学报(工学版), 2023, 57(10): 2018-2027.
[2]	史文韬,李红艳,崔建国,马熠阳,张翀,董颖虹. 极小降压空间下城市供水管网的DMA分区方法[J]. 浙江大学学报(工学版), 2022, 56(8): 1533-1541.
[3]	潘晓,杨云丹,尧鑫,吴雷,王书海. 基于隐马尔科夫模型的潜在个性化路线推荐[J]. 浙江大学学报(工学版), 2020, 54(9): 1736-1745.
[4]	黄家骏, 腾来, 张朝杰, 王春晖, 朴成勇. 基于模拟退火算法的I/Q不平衡校正[J]. 浙江大学学报(工学版), 2018, 52(11): 2218-2225.
[5]	袁友伟, 余佳, 郑宏升, 王娇娇. 基于新颖性排名和多服务质量的云工作流调度算法[J]. 浙江大学学报(工学版), 2017, 51(6): 1190-1196.
[6]	程准,鲁植雄,龚佳慧,刁秀永 . 转向系统传递函数的研究及理想传动比获取[J]. 浙江大学学报(工学版), 2016, 50(7): 1276-1283.
[7]	刘爱军, 杨育, 李斐, 邢青松, 陆惠, 张煜东. 混沌模拟退火粒子群优化算法研究及应用[J]. J4, 2013, 47(10): 1722-1730.
[8]	陈晓刚, 于浩, 王波, 蒋正威, 江全元, 郭创新, 曹一家. 满足多种约束条件的最优PMU配置方法[J]. J4, 2010, 44(3): 539-543.

Viewed

Full text

Abstract

Cited

Shared

Discussed