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.
Fig.1Example diagram of profitable taxi route recommendation
Fig.2Framework for taxi route recommendation algorithm
车机号
空车
GPS时间
经度/°E
纬度/°N
3
1
2016-08-29 07:22:38
121.463 930
31.256 790
3
1
2016-08-29 07:22:48
121.464 068
31.256 278
3
1
2016-08-29 07:22:58
121.464 087
31.255 910
$\vdots $
$\vdots $
$\vdots $
$\vdots $
$\vdots $
21 641
0
2016-08-29 09:11:11
121.604 590
31.318 463
21 641
0
2016-08-29 09:11:21
121.606 452
31.318 510
$\vdots $
$\vdots $
$\vdots $
$\vdots $
$\vdots $
Tab.1Example of taxi GPS trajectory data in Shanghai
Fig.3Time-varying characteristic diagram of number of picking-up
Fig.4Clustering results of picking up events during 7:00—10:00 on August 29, 2016
Fig.5Clustering results of picking up events during 13:00—16:00 on August 29, 2016
Fig.6Impact of number of potential picking-up points on running time of SA+GA, BFS and LCPS algorithms
上客点
$ {P_i} $
Ti/h
Di/km
$ {F_i} $/元
$ {C_4} $
0.095
1.761
21.738
57.643
$ {C_{17}} $
0.243
3.344
51.332
26.591
$ {C_{14}} $
0.120
4.861
86.188
17.506
$ {C_{29}} $
0.051
5.493
97.403
68.778
$ {C_{10}} $
0.546
6.670
123.784
37.570
Tab.2Route recommendation result of PTD model during 7:00—10:00
上客点
$ {P_i} $
Ti/h
Di/km
$ {F_i} $/元
$ {C_{17}} $
0.243
1.417
26.794
26.591
$ {C_4} $
0.095
2.733
58.234
57.643
$ {C_{14}} $
0.120
3.681
79.277
17.506
$ {C_{29}} $
0.051
4.313
90.491
68.778
$ {C_{32}} $
0.233
5.899
120.290
18.650
Tab.3Route recommendation result of RTS model during 7:00—10:00
上客点
$ {P_i} $
Ti/h
Di/km
$ {F_i} $/元
$ {C_{17}} $
0.243
1.417
26.794
26.591
$ {C_{47}} $
0.846
2.580
45.308
36.512
$ {C_{10}} $
0.546
3.697
64.540
37.570
$ {C_{11}} $
0.829
4.359
74.315
51.181
$ {C_{43}} $
0.155
5.713
102.337
20.506
Tab.4Route recommendation result of PMSR model during 7:00—10:00
上客点
$ {P_i} $
Ti/h
Di/km
$ {F_i} $/元
$ {C_{99}} $
0.400
0.399
5.215
21.474
$ {C_{117}} $
0.217
1.825
27.960
32.680
$ {C_{40}} $
0.353
3.628
57.423
23.012
$ {C_{84}} $
0.386
4.195
66.016
16.938
$ {C_{109}} $
0.220
5.892
102.351
18.777
Tab.5Route recommendation result of PTD model during 13:00—16:00
上客点
$ {P_i} $
Ti/h
Di/km
$ {F_i} $/元
$ {C_{99}} $
0.400
0.399
5.215
21.474
$ {C_8} $
0.621
1.658
24.048
27.457
$ {C_{40}} $
0.353
3.203
48.012
23.012
$ {C_{84}} $
0.386
3.771
56.605
16.938
$ {C_{86}} $
0.243
4.747
73.130
27.551
Tab.6Route recommendation result of RTS model during 13:00—16:00
上客点
$ {P_i} $
Ti/h
Di/km
$ {F_i} $/元
$ {C_{48}} $
0.295
0.666
9.595
22.459
$ {C_{12}} $
0.567
1.847
26.999
17.223
$ {C_{41}} $
0.356
3.554
57.332
20.224
$ {C_{13}} $
0.990
4.443
69.245
38.361
$ {C_{82}} $
0.757
4.466
69.556
29.704
Tab.7Route recommendation result of PMSR model during 13:00—16:00
Fig.7Search time for recommended routes in different models during 7:00—10:00
Fig.8Search distance for recommended routes in different models during 7:00—10:00
Fig.9Search time for recommended routes in different models during 13:00—16:00
Fig.10Search distance for recommended routes in different models during 13:00—16:00
上客点
$ {P_i} $
Ti/h
Di/km
$ {F_i} $/元
$ {C_{17}} $
0.243
1.417
26.794
26.591
$ {C_2} $
0.532
2.870
59.048
65.875
$ {C_{11}} $
0.829
4.203
85.459
51.181
$ {C_{10}} $
0.546
4.405
88.785
37.570
$ {C_{43}} $
0.155
4.936
103.323
20.506
Tab.8Route recommendation result of PMSR-D model during 7:00—10:00
上客点
$ {P_i} $
Ti/h
Di/km
$ {F_i} $/元
$ {C_{48}} $
0.295
0.666
9.595
22.459
$ {C_8} $
0.621
2.030
30.761
27.457
$ {C_{41}} $
0.356
3.070
52.501
20.224
$ {C_{82}} $
0.757
4.160
69.363
29.704
$ {C_{13}} $
0.990
4.178
69.599
38.361
Tab.9Route 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
