Full Text:   <1664>

Summary:  <214>

CLC number: TP39

On-line Access: 2022-10-24

Received: 2021-11-14

Revision Accepted: 2022-10-24

Crosschecked: 2022-06-24

Cited: 0

Clicked: 1678

Citations:  Bibtex RefMan EndNote GB/T7714

 ORCID:

Huaqing Li

https://orcid.org/0000-0001-6310-8965

Wenyong ZHANG

https://orcid.org/0000-0002-6969-9695

Dawen XIA

https://orcid.org/0000-0002-0151-9643

-   Go to

Article info.
Open peer comments

Frontiers of Information Technology & Electronic Engineering  2022 Vol.23 No.10 P.1494-1510

http://doi.org/10.1631/FITEE.2100530


APFD: an effective approach to taxi route recommendation with mobile trajectory big data


Author(s):  Wenyong ZHANG, Dawen XIA, Guoyan CHANG, Yang HU, Yujia HUO, Fujian FENG, Yantao LI, Huaqing LI

Affiliation(s):  College of Data Science and Information Engineering, Guizhou Minzu University, Guiyang 550025, China; more

Corresponding email(s):   gzmdzwy@gzmu.edu.cn, dwxia@gzmu.edu.cn, huaqingli@swu.edu.cn

Key Words:  Big data analytics, Region extraction, Artificial potential field, Dijkstra, Route recommendation, GPS trajectories of taxis


Wenyong ZHANG, Dawen XIA, Guoyan CHANG, Yang HU, Yujia HUO, Fujian FENG, Yantao LI, Huaqing LI. APFD: an effective approach to taxi route recommendation with mobile trajectory big data[J]. Frontiers of Information Technology & Electronic Engineering, 2022, 23(10): 1494-1510.

@article{title="APFD: an effective approach to taxi route recommendation with mobile trajectory big data",
author="Wenyong ZHANG, Dawen XIA, Guoyan CHANG, Yang HU, Yujia HUO, Fujian FENG, Yantao LI, Huaqing LI",
journal="Frontiers of Information Technology & Electronic Engineering",
volume="23",
number="10",
pages="1494-1510",
year="2022",
publisher="Zhejiang University Press & Springer",
doi="10.1631/FITEE.2100530"
}

%0 Journal Article
%T APFD: an effective approach to taxi route recommendation with mobile trajectory big data
%A Wenyong ZHANG
%A Dawen XIA
%A Guoyan CHANG
%A Yang HU
%A Yujia HUO
%A Fujian FENG
%A Yantao LI
%A Huaqing LI
%J Frontiers of Information Technology & Electronic Engineering
%V 23
%N 10
%P 1494-1510
%@ 2095-9184
%D 2022
%I Zhejiang University Press & Springer
%DOI 10.1631/FITEE.2100530

TY - JOUR
T1 - APFD: an effective approach to taxi route recommendation with mobile trajectory big data
A1 - Wenyong ZHANG
A1 - Dawen XIA
A1 - Guoyan CHANG
A1 - Yang HU
A1 - Yujia HUO
A1 - Fujian FENG
A1 - Yantao LI
A1 - Huaqing LI
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 23
IS - 10
SP - 1494
EP - 1510
%@ 2095-9184
Y1 - 2022
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/FITEE.2100530


Abstract: 
With the rapid development of data-driven intelligent transportation systems, an efficient route recommendation method for taxis has become a hot topic in smart cities. We present an effective taxi route recommendation approach (called APFD) based on the artificial potential field (APF) method and dijkstra method with mobile trajectory big data. Specifically, to improve the efficiency of route recommendation, we propose a region extraction method that searches for a region including the optimal route through the origin and destination coordinates. Then, based on the APF method, we put forward an effective approach for removing redundant nodes. Finally, we employ the dijkstra method to determine the optimal route recommendation. In particular, the APFD approach is applied to a simulation map and the real-world road network on the Fourth Ring Road in Beijing. On the map, we randomly select 20 pairs of origin and destination coordinates and use APFD with the ant colony (AC) algorithm, greedy algorithm (A∗), APF, rapid-exploration random tree (RRT), non-dominated sorting genetic algorithm-II (NSGA-II), particle swarm optimization (PSO), and dijkstra for the shortest route recommendation. Compared with AC, A∗, APF, RRT, NSGA-II, and PSO, concerning shortest route planning, APFD improves route planning capability by 1.45%–39.56%, 4.64%–54.75%, 8.59%–37.25%, 5.06%–45.34%, 0.94%–20.40%, and 2.43%–38.31%, respectively. Compared with dijkstra, the performance of APFD is improved by 1.03–27.75 times in terms of the execution efficiency. In addition, in the real-world road network, on the Fourth Ring Road in Beijing, the ability of APFD to recommend the shortest route is better than those of AC, A∗, APF, RRT, NSGA-II, and PSO, and the execution efficiency of APFD is higher than that of the dijkstra method.

APFD:面向移动轨迹大数据的出租车路径推荐方法

张文勇1,夏大文1,常国艳5,胡杨2,霍雨佳1,冯夫健1,李艳涛3,李华青4
1贵州民族大学数据科学与信息工程学院,中国贵阳市,550025
2贵州交通技师学院汽车工程系,中国贵阳市,550008
3重庆大学计算机科学学院,中国重庆市,400044
4西南大学电子与信息工程学院,中国重庆市,400715
5贵州医科大学附属医院,中国贵阳市,550001
摘要:随着数据驱动智能交通系统的迅猛发展,高效的出租车路径推荐方法成为智慧城市的研究热点。基于移动轨迹大数据,提出一种基于人工势场(APF)和Dijkstra方法的出租车路径推荐方法。为提高路径推荐效率,提出一种区域提取方法,该方法通过原点和终点坐标搜索包含最优路径的区域。基于APF方法,提出一种有效的冗余节点去除方法。最后,通过Dijkstra方法推荐最优路径。将APFD方法应用于仿真地图和北京四环的实际路网。在地图上随机选取20对起点和终点坐标,采用APFD方法、蚁群(AC)算法、贪婪算法(A•)、APF、迅速探索随机树(RRT)、非支配排序遗传算法-II(NSGA-II)、粒子群算法(PSO)和Dijkstra算法进行最短路径推荐。在最短路径规划方面,与AC、A•、APF、RRT、NSGA-II和PSO相比,APFD的路径规划能力分别提高了1.45%–39.56%、4.64%–54.75%、8.59%–37.25%、5.06%–45.34%、0.94%–20.40%和2.43%–38.31%。与Dijkstra算法相比,APFD的执行效率提高了1.03–27.75倍。此外,在北京四环实际路网中,APFD推荐最短路径的能力优于AC、A•、APF、RRT、NSGA-II和PSO,且APFD的执行效率高于Dijkstra方法。

关键词:大数据分析;区域提取;人工势场;Dijkstra;路线推荐;出租车GPS轨迹

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

[1]Agarwal D, Bharti PS, 2020. Nature inspired evolutionary approaches for robot navigation: survey. J Inform Optim Sci, 41(2):421-436.

[2]Ajeil FH, Ibraheem IK, Sahib MA, et al., 2020. Multi-objective path planning of an autonomous mobile robot using hybrid PSO-MFB optimization algorithm. Appl Soft Comput, 89:106076.

[3]Akram M, Habib A, Alcantud JCR, 2021. An optimization study based on Dijkstra algorithm for a network with trapezoidal picture fuzzy numbers. Neur Comput Appl, 33(4):1329-1342.

[4]Algfoor ZA, Sunar MS, Abdullah A, 2017. A new weighted pathfinding algorithms to reduce the search time on grid maps. Expert Syst Appl, 71:319-331.

[5]Danilovic M, Vasiljevic D, Cvetic B, 2021. A novel pseudo-polynomial approach for shortest path problems. Networks, 78(2):107-127.

[6]He ZC, Chen KY, Chen XY, 2018. A collaborative method for route discovery using taxi drivers’ experience and preferences. IEEE Trans Intell Transp Syst, 19(8):2505-2514.

[7]Hoy M, Matveev AS, Savkin AV, 2015. Algorithms for collision-free navigation of mobile robots in complex cluttered environments: a survey. Robotica, 33(3):463-497.

[8]Huang Y, Ying JJC, Yu PS, et al., 2021. Dynamic graph mining for multi-weight multi-destination route planning with deadlines constraints. ACM Trans Knowl Discov Data, 15(1):3.

[9]Ji SG, Wang ZY, Li TR, et al., 2020. Spatio-temporal feature fusion for dynamic taxi route recommendation via deep reinforcement learning. Knowl-Based Syst, 205:106302.

[10]Jiao ZQ, Ma K, Rong YL, et al., 2018. A path planning method using adaptive polymorphic ant colony algorithm for smart wheelchairs. J Comput Sci, 25:50-57.

[11]Kou CX, Hu DD, Yuan JH, et al., 2020. Bisection and exact algorithms based on the Lagrangian dual for a single-constrained shortest path problem. IEEE/ACM Trans Netw, 28(1):224-233.

[12]Lai YX, Lv Z, Li KC, et al., 2019. Urban traffic Coulomb’s law: a new approach for taxi route recommendation. IEEE Trans Intell Transp Syst, 20(8):3024-3037.

[13]Lin BL, Zhao YN, Lin RX, et al., 2021. Integrating traffic routing optimization and train formation plan using simulated annealing algorithm. Appl Math Modell, 93:811-830.

[14]Mac TT, Copot C, Tran DT, et al., 2016. Heuristic approaches in robot path planning: a survey. Rob Auton Syst, 86:13-28.

[15]Mavrovouniotis M, Li CH, Yang SX, 2017. A survey of swarm intelligence for dynamic optimization: algorithms and applications. Swarm Evol Comput, 33:1-17.

[16]Nazarahari M, Khanmirza E, Doostie S, 2019. Multi-objective multi-robot path planning in continuous environment using an enhanced genetic algorithm. Expert Syst Appl, 115:106-120.

[17]Nimmagadda MR, Dattawadkar S, Muthukumar S, et al., 2020. Adaptive directional path planner for real-time, energy-efficient, robust navigation of mobile robots. Proc IEEE Int Conf on Robotics and Automation, p.455-461.

[18]Parimala M, Broumi S, Prakash K, et al., 2021. Bellman–Ford algorithm for solving shortest path problem of a network under picture fuzzy environment. Compl Intell Syst, 7(5):2373-2381.

[19]Przybylski A, Gandibleux X, 2017. Multi-objective branch and bound. Eur J Oper Res, 260(3):856-872.

[20]Qin GY, Li TN, Yu B, et al., 2017. Mining factors affecting taxi drivers’ incomes using GPS trajectories. Transp Res Part C Emerg Technol, 79:103-118.

[21]Qu BT, Yang WX, Cui G, et al., 2020. Profitable taxi travel route recommendation based on big taxi trajectory data. IEEE Trans Intell Transp Syst, 21(2):653-668.

[22]Rizk Y, Awad M, Tunstel EW, 2018. Decision making in multiagent systems: a survey. IEEE Trans Cogn Dev Syst, 10(3):514-529.

[23]Santos FA, Rodrigues DO, Silva TH, et al., 2018. Context-aware vehicle route recommendation platform: exploring open and crowdsourced data. Proc IEEE Int Conf on Communications, p.1-7.

[24]Schaller Consulting, 2006. The New York City Taxicab Fact Book. Schaller Consulting, Brooklyn, UK.

[25]Sharma K, Doriya R, 2020. Path planning for robots: an elucidating draft. Int J Intell Robot Appl, 4(3):294-307.

[26]Sinyukov DA, Padir T, 2020. CWave: theory and practice of a fast single-source any-angle path planning algorithm. Robotica, 38(2):207-234.

[27]Wang JK, Meng MQH, 2020. Optimal path planning using generalized Voronoi graph and multiple potential functions. IEEE Trans Ind Electron, 67(12):10621-10630.

[28]Wang JK, Chi WZ, Li CM, et al., 2020. Neural RRT*: learning-based optimal path planning. IEEE Trans Autom Sci Eng, 17(4):1748-1758.

[29]Wang YS, Zheng XP, Chen W, et al., 2021. Robust and accurate optimal transportation map by self-adaptive sampling. Front Inform Technol Electron Eng, 22(9):1207-1220.

[30]Wu N, Wang JY, Zhao WX, et al., 2019. Learning to effectively estimate the travel time for fastest route recommendation. Proc 28th ACM Int Conf on Information and Knowledge Management, p.1923-1932.

[31]Wu TQ, Yao M, Yang JH, 2016. Dolphin swarm algorithm. Front Inform Technol Electron Eng, 17(8):717-729.

[32]Yang SY, Ning LJ, Tong LC, et al., 2021. Optimizing electric vehicle routing problems with mixed backhauls and recharging strategies in multi-dimensional representation network. Expert Syst Appl, 176:114804.

[33]Zajac S, Huber S, 2021. Objectives and methods in multi-objective routing problems: a survey and classification scheme. Eur J Oper Res, 290(1):1-25.

[34]Zhang XJ, Jia W, Guan XM, et al., 2019. Optimized deployment of a radar network based on an improved firefly algorithm. Front Inform Technol Electron Eng, 20(3):425-437.

[35]Zhang Y, Li LL, Lin HC, et al., 2019. Development of path planning approach using improved A-star algorithm in AGV system. J Int Technol, 20(3):915-924.

[36]Zhu DD, Sun JQ, 2021. A new algorithm based on Dijkstra for vehicle path planning considering intersection attribute. IEEE Access, 9:19761-19775.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - 2024 Journal of Zhejiang University-SCIENCE