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

张文勇; 夏大文; 常国艳; 胡杨; 霍雨佳; 冯夫健; 李艳涛; 李华青

doi:10.1631/FITEE.2100530

Your Location：

Home >

Browse articles >

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

常规文章 | Updated：2022-10-28

- APFD：面向移动轨迹大数据的出租车路径推荐方法
- APFD: an effective approach to taxi route recommendation with mobile trajectory big data
- 信息与电子工程前沿（英文） 2022年23卷第10期页码：1494-1510
- Affiliations：
  
  1.College of Data Science and Information Engineering, Guizhou Minzu University, Guiyang 550025, China
  2.Department of Automotive Engineering, Guizhou Traffic Technician and Transportation College, Guiyang 550008, China
  3.College of Computer Science, Chongqing University, Chongqing 400044, China
  4.College of Electronic and Information Engineering, Southwest University, Chongqing 400715, China
  5.The Affiliated Hospital of Guizhou Medical University, Guiyang 550001, China
- Author bio：
  
  †E-mail: gzmdzwy@gzmu.edu.cn
  ‡Corresponding authors
- Funds：
  
  National Natural Science Foundation of China(62162012;62173278;62072061);Science and Technology Support Program of Guizhou Province, China(QKHZC2021YB531);Youth Science and Technology Talents Development Project of Colleges and Universities in Guizhou Province, China(QJHKY2022175);Science and Technology Foundation of Guizhou Province, China(QKHJCZK2022YB195;QKHJCZK2022YB197);Natural Science Research Project of the Department of Education of Guizhou Province, China(QJJ2022015);Scientific Research Platform Project of Guizhou Minzu University, China(GZMUSYS[2021]04)
- DOI：10.1631/FITEE.2100530
  中图分类号： TP39
- 收稿：2021-11-14，
  
  修回：2022-08-01，
  
  录用：2022-06-24，
  
  网络出版：2022-09-24，
  
  纸质出版：2022-10-0
- Accepted：
Scan QR Code
张文勇, 夏大文, 常国艳, 等. APFD：面向移动轨迹大数据的出租车路径推荐方法[J]. 信息与电子工程前沿（英文）, 2022,23(10):1494-1510.

Wenyong ZHANG, Dawen XIA, Guoyan CHANG, et al. 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.
张文勇, 夏大文, 常国艳, 等. APFD：面向移动轨迹大数据的出租车路径推荐方法[J]. 信息与电子工程前沿（英文）, 2022,23(10):1494-1510. DOI： 10.1631/FITEE.2100530.

Wenyong ZHANG, Dawen XIA, Guoyan CHANG, et al. 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. DOI： 10.1631/FITEE.2100530.

摘要

随着数据驱动智能交通系统的迅猛发展，高效的出租车路径推荐方法成为智慧城市的研究热点。基于移动轨迹大数据，提出一种基于人工势场（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方法。

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

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

APF

RRT

NSGA-II

and PSO

and the execution efficiency of APFD is higher than that of the Dijkstra method.

关键词

Keywords

references

D Agarwal , , PS Bharti , . 2020 . . Nature inspired evolutionary approaches for robot navigation: survey . . J Inform Optim Sci , , 41 ( ( 2 ): ): 421 - - 436 . . doi: 10.1080/02522667.2020.1723938 http://doi.org/10.1080/02522667.2020.1723938 .

FH Ajeil , , IK Ibraheem , , MA Sahib , , et al. , . 2020 . . Multi-objective path planning of an autonomous mobile robot using hybrid PSO-MFB optimization algorithm . . Appl Soft Comput , , 89 : 106076 . doi: 10.1016/j.asoc.2020.106076 http://doi.org/10.1016/j.asoc.2020.106076 .

M Akram , , A Habib , , JCR Alcantud , . 2021 . . An optimization study based on Dijkstra algorithm for a network with trapezoidal picture fuzzy numbers . . Neur Comput Appl , , 33 ( ( 4 ): ): 1329 - - 1342 . . doi: 10.1007/s00521-020-05034-y http://doi.org/10.1007/s00521-020-05034-y .

ZA Algfoor , , MS Sunar , , A Abdullah , . 2017 . . A new weighted pathfinding algorithms to reduce the search time on grid maps . . Expert Syst Appl , , 71 : 319 - - 331 . . doi: 10.1016/j.eswa.2016.12.003 http://doi.org/10.1016/j.eswa.2016.12.003 .

M Danilovic , , D Vasiljevic , , B Cvetic , . 2021 . . A novel pseudo-polynomial approach for shortest path problems . . Networks , , 78 ( ( 2 ): ): 107 - - 127 . . doi: 10.1002/net.22027 http://doi.org/10.1002/net.22027 .

ZC He , , KY Chen , , XY Chen , . 2018 . . A collaborative method for route discovery using taxi drivers’ experience and preferences . . IEEE Trans Intell Transp Syst , , 19 ( ( 8 ): ): 2505 - - 2514 . . doi: 10.1109/TITS.2017.2753468 http://doi.org/10.1109/TITS.2017.2753468 .

M Hoy , , AS Matveev , , AV Savkin , . 2015 . . Algorithms for collision-free navigation of mobile robots in complex cluttered environments: a survey . . Robotica , , 33 ( ( 3 ): ): 463 - - 497 . . doi: 10.1017/S0263574714000289 http://doi.org/10.1017/S0263574714000289 .

Y Huang , , JJC Ying , , PS Yu , , et al. , . 2021 . . Dynamic graph mining for multi-weight multi-destination route planning with deadlines constraints . . ACM Trans Knowl Discov Data , , 15 ( ( 1 ): ): 3 . doi: 10.1145/3412363 http://doi.org/10.1145/3412363 .

SG Ji , , ZY Wang , , TR Li , , et al. , . 2020 . . Spatio-temporal feature fusion for dynamic taxi route recommendation via deep reinforcement learning . . Knowl-Based Syst , , 205 : 106302 . doi: 10.1016/j.knosys.2020.106302 http://doi.org/10.1016/j.knosys.2020.106302 .

ZQ Jiao , , K Ma , , YL Rong , , et al. , . 2018 . . A path planning method using adaptive polymorphic ant colony algorithm for smart wheelchairs . . J Comput Sci , , 25 : 50 - - 57 . . doi: 10.1016/j.jocs.2018.02.004 http://doi.org/10.1016/j.jocs.2018.02.004 .

CX Kou , , DD Hu , , JH Yuan , , 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 . . doi: 10.1109/TNET.2019.2955451 http://doi.org/10.1109/TNET.2019.2955451 .

YX Lai , , Z Lv , , KC Li , , et al. , . 2019 . . Urban traffic Coulomb’s law: a new approach for taxi route recommendation . . IEEE Trans Intell Transp Syst , , 20 ( ( 8 ): ): 3024 - - 3037 . . doi: 10.1109/TITS.2018.2870990 http://doi.org/10.1109/TITS.2018.2870990 .

BL Lin , , YN Zhao , , RX Lin , , et al. , . 2021 . . Integrating traffic routing optimization and train formation plan using simulated annealing algorithm . . Appl Math Modell , , 93 : 811 - - 830 . . doi: 10.1016/j.apm.2020.12.031 http://doi.org/10.1016/j.apm.2020.12.031 .

TT Mac , , C Copot , , DT Tran , , et al. , . 2016 . . Heuristic approaches in robot path planning: a survey . . Rob Auton Syst , , 86 : 13 - - 28 . . doi: 10.1016/j.robot.2016.08.001 http://doi.org/10.1016/j.robot.2016.08.001 .

M Mavrovouniotis , , CH Li , , SX Yang , . 2017 . . A survey of swarm intelligence for dynamic optimization: algorithms and applications . . Swarm Evol Comput , , 33 : 1 - - 17 . . doi: 10.1016/j.swevo.2016.12.005 http://doi.org/10.1016/j.swevo.2016.12.005 .

M Nazarahari , , E Khanmirza , , S Doostie , . 2019 . . Multi-objective multi-robot path planning in continuous environment using an enhanced genetic algorithm . . Expert Syst Appl , , 115 : 106 - - 120 . . doi: 10.1016/j.eswa.2018.08.008 http://doi.org/10.1016/j.eswa.2018.08.008 .

MR Nimmagadda , , S Dattawadkar , , S Muthukumar , , 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 . . doi: 10.1109/ICRA40945.2020.9197417 http://doi.org/10.1109/ICRA40945.2020.9197417 .

M Parimala , , S Broumi , , K Prakash , , 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 . . doi: 10.1007/s40747-021-00430-w http://doi.org/10.1007/s40747-021-00430-w .

A Przybylski , , X Gandibleux , . 2017 . . Multi-objective branch and bound . . Eur J Oper Res , , 260 ( ( 3 ): ): 856 - - 872 . . doi: 10.1016/j.ejor.2017.01.032 http://doi.org/10.1016/j.ejor.2017.01.032 .

GY Qin , , TN Li , , B Yu , , et al. , . 2017 . . Mining factors affecting taxi drivers’ incomes using GPS trajectories . . Transp Res Part C Emerg Technol , , 79 : 103 - - 118 . . doi: 10.1016/j.trc.2017.03.013 http://doi.org/10.1016/j.trc.2017.03.013 .

BT Qu , , WX Yang , , G Cui , , et al. , . 2020 . . Profitable taxi travel route recommendation based on big taxi trajectory data . . IEEE Trans Intell Transp Syst , , 21 ( ( 2 ): ): 653 - - 668 . . doi: 10.1109/TITS.2019.2897776 http://doi.org/10.1109/TITS.2019.2897776 .

Y Rizk , , M Awad , , EW Tunstel , . 2018 . . Decision making in multiagent systems: a survey . . IEEE Trans Cogn Dev Syst , , 10 ( ( 3 ): ): 514 - - 529 . . doi: 10.1109/TCDS.2018.2840971 http://doi.org/10.1109/TCDS.2018.2840971 .

FA Santos , , DO Rodrigues , , TH Silva , , et al. , . 2018 . . Context-aware vehicle route recommendation platform: exploring open and crowdsourced data . . Proc IEEE Int Conf on Communications , p. . 1 - - 7 . . doi: 10.1109/ICC.2018.8422972 http://doi.org/10.1109/ICC.2018.8422972 .

Consulting Schaller , . 2006 . . The New York City Taxicab Fact Book . , Schaller Consulting , , : Brooklyn, UK . .

K Sharma , , R Doriya , . 2020 . . Path planning for robots: an elucidating draft . . Int J Intell Robot Appl , , 4 ( ( 3 ): ): 294 - - 307 . . doi: 10.1007/s41315-020-00129-0 http://doi.org/10.1007/s41315-020-00129-0 .

DA Sinyukov , , T Padir , . 2020 . . CWave: theory and practice of a fast single-source any-angle path planning algorithm . . Robotica , , 38 ( ( 2 ): ): 207 - - 234 . . doi: 10.1017/S0263574719000560 http://doi.org/10.1017/S0263574719000560 .

JK Wang , , MQH Meng , . 2020 . . Optimal path planning using generalized Voronoi graph and multiple potential functions . . IEEE Trans Ind Electron , , 67 ( ( 12 ): ): 10621 - - 10630 . . doi: 10.1109/TIE.2019.2962425 http://doi.org/10.1109/TIE.2019.2962425 .

JK Wang , , WZ Chi , , CM Li , , et al. , . 2020 . . Neural RRT * : learning-based optimal path planning . . IEEE Trans Autom Sci Eng , , 17 ( ( 4 ): ): 1748 - - 1758 . . doi: 10.1109/TASE.2020.2976560 http://doi.org/10.1109/TASE.2020.2976560 .

YS Wang , , XP Zheng , , W Chen , , et al. , . 2021 . . Robust and accurate optimal transportation map by self-adaptive sampling . . Front Inform Technol Electron Eng , , 22 ( ( 9 ): ): 1207 - - 1220 . . doi: 10.1631/FITEE.2000250 http://doi.org/10.1631/FITEE.2000250 .

N Wu , , JY Wang , , WX Zhao , , et al. , . 2019 . . Learning to effectively estimate the travel time for fastest route recommendation . . Proc 28 th ACM Int Conf on Information and Knowledge Management , p. , 1923 - - 1932 . . doi: 10.1145/3357384.3357907 http://doi.org/10.1145/3357384.3357907 .

TQ Wu , , M Yao , , JH Yang , . 2016 . . Dolphin swarm algorithm . . Front Inform Technol Electron Eng , , 17 ( ( 8 ): ): 717 - - 729 . . doi: 10.1631/FITEE.1500287 http://doi.org/10.1631/FITEE.1500287 .

SY Yang , , LJ Ning , , LC Tong , , et al. , . 2021 . . Optimizing electric vehicle routing problems with mixed backhauls and recharging strategies in multi-dimensional representation network . . Expert Syst Appl , , 176 : 114804 . doi: 10.1016/j.eswa.2021.114804 http://doi.org/10.1016/j.eswa.2021.114804 .

S Zajac , , S Huber , . 2021 . . Objectives and methods in multi-objective routing problems: a survey and classification scheme . . Eur J Oper Res , , 290 ( ( 1 ): ): 1 - - 25 . . doi: 10.1016/j.ejor.2020.07.005 http://doi.org/10.1016/j.ejor.2020.07.005 .

XJ Zhang , , W Jia , , XM Guan , , et al. , . 2019 . . Optimized deployment of a radar network based on an improved firefly algorithm . . Front Inform Technol Electron Eng , , 20 ( ( 3 ): ): 425 - - 437 . . doi: 10.1631/FITEE.1800749 http://doi.org/10.1631/FITEE.1800749 .

Y Zhang , , LL Li , , HC Lin , , et al. , . 2019 . . Development of path planning approach using improved A-star algorithm in AGV system . . J Int Technol , , 20 ( ( 3 ): ): 915 - - 924 . . doi: 10.3966/160792642019052003023 http://doi.org/10.3966/160792642019052003023 .

DD Zhu , , JQ Sun , . 2021 . . A new algorithm based on Dijkstra for vehicle path planning considering intersection attribute . . IEEE Access , , 9 : 19761 - - 19775 . . doi: 10.1109/ACCESS.2021.3053169 http://doi.org/10.1109/ACCESS.2021.3053169 .

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

Target detection for multi-UAVs via digital pheromones and navigation algorithm in unknown environments