Wenyong ZHANG,Dawen XIA?,Guoyan CHANG,Yang HU,Yujia HUO,Fujian FENG,Yantao LI,Huaqing LI?

1College of Data Science and Information Engineering,Guizhou Minzu University,Guiyang 550025,China

2Department of Automotive Engineering,Guizhou Traffic Technician and Transportation College,Guiyang 550008,China

3College of Computer Science,Chongqing University,Chongqing 400044,China

4College of Electronic and Information Engineering,Southwest University,Chongqing 400715,China

5The Affiliated Hospital of Guizhou Medical University,Guiyang 550001,China

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.

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

1 Introduction

Along with social progress,people’s capacity for consumption and travel is increasing,which createshigher requirements for urban transportation.Recently,taxi has become the first choice for travelers due to its convenience,safety,and personalization(He et al.,2018;Lai et al.,2019).Specifically,it is well known that urbanization has led to the growth of traffic congestion.To address this issue,urban managers have invested significant funds to expand and renovate urban roads,making the transportation network increasingly complicated.At the same time,the complex road network and traffic congestion have made taxis less efficient in carrying passengers(Qin et al.,2017).Existing studies have shown that taxis spend 35%–60% of their time cruising the road and searching for passengers(Schaller Consulting,2006).On one hand,this increases waiting time and creates a poor ride experience for passengers.On the other hand,it results in issues such as high taxi operating cost,high energy consumption,and environmental pollution(Ji et al.,2020).To improve passenger experience,increase the efficiency of taxi operation,and reduce energy consumption,many scholars have proposed different methods for recommending the fastest taxi routes.Currently,route planning methods can be divided into classic methods and heuristic methods(Mac et al.,2016;Zajac and Huber,2021).The dynamic programming method,branch-and-bound method(Przybylski and Gandibleux,2017),artificial potential field(APF)method,Dijkstra method,Bellman–Ford method(Parimala et al.,2021),and greedy algorithm(A*)(Zhang Y et al.,2019)are classic methods.The latter includes simulated annealing(Lin et al.,2021),firefly algorithm(Zhang XJ et al.,2019),neural network method(Wang JK et al.,2020),genetic algorithm(Nazarahari et al.,2019),ant colony(AC)algorithm(Jiao et al.,2018),and Dolphin swarm algorithm(Wu TQ et al.,2016).

When it comes to heuristic algorithms,the simulated annealing method has strong local search ability,and the neural network method easily converges to the local minimum solution when the target scale is large.The genetic algorithm,with excellent robustness,has strong parallel processing ability and global search ability.However,it has poor local search ability,thus resulting in premature convergence.The characteristics of the AC algorithm are self-adaptation,self-organization,and positive feedback falling,which can promote the whole system to evolve to the optimal solution.However,the AC algorithm has the shortcomings of low convergence speed and is easy to fall into local optima.In addition,there is no parameter setting in the algorithm,and the theoretical basis must be adjusted and determined by extensive experiments(Agarwal and Bharti,2020;Sharma and Doriya,2020).

Among classic approaches,dynamic programming is a recursive method,and the time complexity grows sharply as the number of targets increases.The time complexity of the branch-andbound method increases with an increase in the number of targets,and the calculation time is longer when the number of targets is larger.The APF method imitates the movement of objects under gravity and repulsion.Gravitational forces exist between the target point and moving object.There are repulsive forces between the moving object and obstacles.The route is optimized by establishing a gravitational field function and a repulsive force field function.The advantage is that the route planning effect is smooth,but many problems exist,such as being easily trapped into local optima.Dijkstra is a classic method used to search for the shortest route,and it extends from the origin to the outer layer to the end.The shortest route is obtained by comparing all nodes because the method needs to gradually expand from the origin to the surroundings.Therefore,the calculation of the shortest route has a high success rate and good robustness,but when it is applied to a large-scale node network,the execution time is longer than that of other algorithms(Hoy et al.,2015;Mavrovouniotis et al.,2017;Rizk et al.,2018;Zajac and Huber,2021).

When taxis carry passengers,the method needs to complete the optimal route recommendation in the shortest possible time.If the execution time of the method is too long,taxi drivers and passengers would wait for a long time for the route planning results.If the method fails to obtain the optimal route,it affects the arrival time of passengers.Therefore,to satisfy passengers and taxi drivers,the recommendation result of the algorithm needs to have the shortest execution time and the best route planning.

Heuristic methods have strong search capabilities and large-scale retrieval capabilities compared to classic methods,but they require multiple iterations to obtain a better route.Although classic methods take a long time to process a large-scale node network,when the number of nodes is smallerthan a certain size,the execution efficiency is higher.In classic methods,Dijkstra finds the destination by traversing layer by layer,and the route obtained is the optimal route.In the calculation process,most of the points cannot be the optimal route nodes.If they can be removed,the execution time of the Dijkstra method would be greatly reduced.

For this reason,the algorithm needs to be executed in a short time and solve the recommended route optimization problem.We propose a novel hybrid route recommendation approach(named APFD)based on the APF and Dijkstra methods.Specifically,according to the origin and destination coordinates,we select the area that contains the best route.Furthermore,we employ the APF method to remove redundant points with a low possibility of forming the shortest route.Finally,we use the Dijkstra method for optimal route planning.

The proposed APFD approach is applied to the simulated road network and the real-world road network on the Fourth Ring Road in Beijing.Compared with AC,A*,APF,rapid-exploration random tree(RRT),non-dominated sorting genetic algorithm-II(NSGA-II),and particle swarm optimization(PSO)methods,route planning ability of APFD is the best.Particularly,compared with Dijkstra,APFD has higher execution efficiency.

The main contributions of this work are summarized as follows:(1)The origin and destination coordinates are used to extract the area that is likely to include the optimal route.The area is taken as the effective area for method retrieval to improve the execution efficiency.(2)A potential energy field is constructed in the road network area.A critical equipotential line is established according to the current coordinate position,and redundant points are removed by comparing the potential energy of each connection point with the critical potential.(3)A distance matrix,a marker matrix,and a visited matrix are constructed for calculating the optimal route.These matrices are calculated using the node coordinates and side length data to obtain the optimal route.

2 Related works

In this section,we review related works about route recommendation and planning.

The rapid development of information technology to solve problems caused by urban transportation has led to the intelligent transportation system.Optimal route recommendation is an important branch and key technology in the field of intelligent transportation(Wu N et al.,2019;Yang et al.,2021).In terms of massive and rapid changes in traffic information,it is very important that the intelligent transportation system can complete route planning before the traffic information is updated and effi-ciently transferred to drivers(Algfoor et al.,2017;Santos et al.,2018;Wang YS et al.,2021).Therefore,the performance of the route planning method becomes the key to solve this problem.For this reason,many scholars have conducted research on route planning methods.

Using heuristic methods,Nimmagadda et al.(2020)proposed an adaptive planning algorithm that uses a combination of continuous space and spatial discretization methods to generate optimal paths and achieve fast route convergence.The algorithm is highly efficient and robust.Ajeil et al.(2020)put forward a hybrid algorithm combining a PSO algorithm and an improved frequency bat algorithm to solve the route planning problem.This method can generate the best feasible route,even in a complex dynamic environment,and thus overcomes the shortcomings of traditional methods such as the grid method.In addition,compared with existing route planning technologies,the proposed hybrid particle swarm optimization-modified frequency bat(PSOMFB)algorithm is strongly competitive in route optimization.Wang JK and Meng(2020)presented a non-uniform sampling technique based on rapid exploration of random tree pipelines,which was used to calculate high-quality conflict-free paths while maintaining fast asymptotic convergence to the optimal solution.The algorithm first calculates the heuristic route.Furthermore,heuristic route discretization and multiple potential functions provide nonuniform sampling distribution for the route planner.Compared to advanced route planning algorithms,this algorithm has better performance.

Although the above methods have strong search capabilities and large-scale retrieval capabilities,they require multiple iterations to obtain a better route.Also,the execution time of the algorithms is long,and it is difficult to meet the real-time requirements.

For classic methods,Sinyukov and Padir(2020)designed a high-performance algorithm based on two-dimensional grid single-source route planning at any angle.This algorithm abandons the general graph model,and directly uses discrete geometric primitives to represent vertices on the grid geometry.By introducing floating-point calculations,the accuracy was enhanced,and a better optimal route was obtained.Danilovic et al.(2021)developed a breadth-first search method to solve the shortest route problem,and all points were processed hierarchically.The method starts from the source point and scans to the outer layer,step by step,to select the most suitable point in the next layer until the key layer is found.Huang et al.(2021)proposed a multi-weight and multi-destination route planning framework with deadline constraints.The experimental results showed that the proposed algorithm performed well in terms of efficiency and effectiveness.Qu et al.(2020)proposed an adaptive shortest expected cruise route method using taxi global position system(GPS)data,the Kalman filter method,a probabilistic network model,and the data structure KDS-tree to improve recommendation efficiency.Zhu and Sun(2021)put forward the reverse labeling Dijkstra algorithm(RLDA)to solve the problem of car rental route recommendation based on the traditional Dijkstra algorithm,breadth-first search,and data structure of stack and queue.The experimental results demonstrated that this method was better than the PSO algorithm,genetic algorithm,AC algorithm,and neural network algorithm,and particularly had higher convergence efficiency and higher calculation speed.Akram et al.(2021)designed a Dijkstra algorithm for the shortest route of image blur,defining the trapezoidal image blur number and its graphical representation.The related cost was captured by the trapezoidal image blur number.Kou et al.(2020)developed a dichotomous method based on the Lagrangian dual method,employing the Dijkstra method in the Lagrangian dual method to improve the efficiency of the algorithm execution,and the effect was appreciable when addressing the route recommendation problem for large-scale complex networks.

Some of these studies adopted the idea of improving the classic route planning method to achieve optimal route planning.These algorithms are highly efficient,but it is difficult to obtain the optimal route using these algorithms.Other research focused on the use of hybrid algorithms for optimal route planning.The route planning ability is strong,but the execution efficiency is low,and it is difficult to meet the requirements of fast route planning.In addition,although some studies mentioned above employed the Dijkstra optimization method for route planning,their focus was on solving the route recommendation problem for large-scale complex networks,and the effect was not necessarily optimal based on the number of small-and medium-scale nodes.The APFD method proposed in this paper reduces the influence of redundant points on the execution efficiency of the algorithm by extracting effective areas and using APFs.After removing redundant points,the Dijkstra algorithm is used to calculate the optimal route plan,which guarantees the performance of the algorithm.The execution time is short,and the optimal route is guaranteed.

3 Problem analysis

In this section,we describe the taxi route recommendation problem and then put forward some reasonable hypotheses.Finally,the problem is modeled mathematically.

3.1 Problem statement

The road network can be expressed and constructed in various ways.In this work,we define intersections in the road network as road network nodes,roads between intersections as road side lengths,and the actual length of road side lengths as the weight value.Fig.1 shows a route simulation.The red node represents the road network node,the black line segment is the length of the road,pointDrepresents the destination location of the passenger,and pointOdenotes the origin position of the taxi.At the current location,the taxi is required to reach the passenger location quickly after receiving a passenger’s request.

Fig.1 Route simulation(References to color refer to the online version of this figure)

3.2 Problem hypothesis

According to the problem statement,we give the following assumptions:

1.Road network nodes and road side lengths are undirected graph networks whose attributes do not change over time.A taxi on each road can exit from both ends of the node.

2.The distance from turning left,turning right,going straight,or making a U-turn can be negligible.

3.When a taxi departs from any position on the road,the origin is defined as the road network node that is closest to this point.As illustrated in Fig.2,pointsAandBare road network nodes,and pointCis the passenger location point or taxi departure point,L1is the actual distance fromCtoA,andL2is the actual distance fromCtoB.IfL1＞L2,the passenger or taxi position isA.

Fig.2 Selection of the origin or destination nodes

3.3 Problem definition

According to the problem statement and assumptions,the mathematical model is defined as follows:

We define a ternary undirected graphG(V,E,W).Vis the intersection node set,V={v1,v2,···,vn},and|V|is the number of intersection nodes(|V|=n).Eis the edge set between any two intersection nodes,and|E|is the number of road sides(|E|=t).Wis the weight value ofE(the weight is measured by the value of the distance),andW={w1,w2,···,wt}.

Suppose thatO=S0is the origin node and thatD=Skis the destination node,fromOtoD.All network nodes that the taxi passes areS0,S1,···,Sk.Letwi(Si,Si+1)be the distance between two adjacent nodes,and we definef(S)as the objective function of the total distance of the taxi from pointOto pointD.Then we have

Therefore,the shortest routeLminis defined as the shortest distance:

4 APFD method

In this section,we describe the proposed APFD method in detail,including area extraction,redundant node removing,and route recommendation.

The process of the APFD method is shown in Fig.3.Fig.3a is the road network map,Ois the origin point,andDis the destination point.First of all,the coordinates ofOandDare employed to extract the area that is likely to have the optimal route and also is the effective area for method retrieval,as illustrated in Fig.3b.Then,a potential energy field is constructed in the road network area,a critical equipotential line is established according to the current coordinate position,and redundant points are removed by comparing the potential energy of each connection point with the critical potential.According to the above two steps,the efficiency of the APFD method can be improved.Finally,a distance matrix,a marker matrix,and a visited matrix are constructed,as depicted in Fig.3c.Also,three matrices mentioned above are calculated according to the node coordinates and side length data to obtain the optimal route,as plotted in Fig.3d.

4.1 Effective area extraction

We coordinate all the road network nodes in Fig.3a.The coordinates of originOare(xo,yo),and the coordinates ofDare(xd,xd).Ωis a matrix region coordinate set withOandDas the diagonal points.According to the coordinates of pointsOandD,the maximumx-coordinate,the minimumx-coordinate,the maximumy-coordinate,and the minimumy-coordinate in theΩarea can be derived:

Fig.3 Process of the APFD method:(a)simulating the road network;(b)extracting the effective area;(c)establishing the calculation matrices;(d)searching for the optimal route

According to Eqs.(3)and(4),the coordinates of the four vertices of theΩregion can be calculated as

According to expression(5),all coordinate points in theΩarea can be extracted,and the extraction method is described in Algorithm 1.

4.2 Redundant node removing

In this subsection,we introduce the method of identifying and removing redundant nodes in detail.When the algorithm selects the next node from the current node,some nodes may not form the shortest route,which are called redundant nodes.If the redundant nodes can be removed before the algorithm is executed,the efficiency of the algorithm would be effectively improved.As shown in Fig.4,pointDis the destination,Psis the current point,andPhis the former point.P1,P2,···,Pfare the points that can be reached byPs,andPhis not the arrival point selected byPs.Some of the nodes inP1,P2,···,Pfare redundant.

Fig.4 Point connection with any point

Algorithm 1 Region extraction method Require:pixel coordinates O(xo,yo)and D(xd,yd)1:n1←|xo-xd|,m1←|yo-yd|2:xmin←min(xo,xd),ymin←min(yo,yd)3:for xmin+i(i←0,1,···,n1-1)do 4: for ymin+j(j←0,1,···,m1-1)do 5: Ω←(xmin+i,ymin+j)6: end for 7:end for Ensure:Ω

To remove redundant points,we define the potential energy fieldφwith destinationDas the center in theΩregion.The potential energy function is defined as

whereξis the positive proportional gain coefficient in the potential field,ρ(q,qgoal)represents the absolute value of the distance between the current location of the taxi and the targeted position,ρ=|q-qgoal|,qis the current position,andqgoalis the targeted position.

According to Eq.(6),the potential energy distribution in theΩregion is plotted in Fig.5.We take pointDas the center,and the potential energy gradually increases outward along pointD.The potential energy fieldφis continuously distributed in theΩregion,and the dashed circle is the equipotential.Same potential energy is on the same equipotential line,and the potential energy changing from pointOto pointDis shown in Fig.6.

As illustrated in Fig.6,pointOis the farthest away point from pointDand has the largest potential energy value.The potential energy decreases continuously from pointOto pointD.PointDhas the smallest potential energy value.Moving from pointOto pointDcan be regarded as an edge movement in a direction along which the gradient gradually decreases.We define the attractive forceof pointDto any point in the potential energy as the negative gradient of the attractive potential energy:

Fig.6 Potential energy gradient direction

As illustrated in Fig.5,we take pointP3as an example.An APF method is used to remove redundant points connected to pointP3.PointP3is set as the current position point.Meanwhile,the points connected to it areP1,P2,P4,andP5.According to the gravitational Eq.(6),the potential energy relations ofP1,P2,P4,P5,andP3are

We define the equipotential line where the current position pointP3is located as the critical equipotential line.As shown in Fig.7,the red equipotential line whereP3is located is the critical equipotential line.We expect to get closer to pointDat every step.Therefore,the next step is to move in the negative gradient direction:

whereEqdenotes the potential energy value of the current position,andEqprerepresents the potential energy value of the approaching point.

Therefore,we judge the points whose potential energy values are greater than the critical equipotential as redundant points in Fig.7.PointsP1andP2are redundant points.Redundant points are directly marked as visited points during route calculation,thereby reducing calculation time and improving execution efficiency.

Fig.7 Critical equipotential line for distinguishing redundant points(References to color refer to the online version of this figure)

In special cases,as depicted in Fig.4,if the potential energy at thePspoint is less than that of each pointP1,P2,···,Pf,or the potential energy atPsis greater than the potential energy of each pointP1,P2,···,Pf,there are no redundant nodes.During route calculation,the route of each pointP1,P2,···,Pfis completely calculated,and the process of removing redundant nodes is described in Algorithm 2.

4.3 Route recommendation

As shown in Fig.8,according to the size of the coordinate point matrix of theΩarea,a marker matrix(Fig.8a),a distance matrix(Fig.8b),and a visited matrix(Fig.8c)are established in this work.

Fig.8a describes the marker matrix,which is used to mark whether the node has been visited.If the node has been visited,the mark is 1;otherwise,it is 0.Fig.8b represents the distance matrix,which is used to record the minimum distance value from the origin to the current point.At the beginning of the algorithm,the distance value of pointOis 0,and the other points are infinite.During the route calculation,the distance value of each point is continuously updated until the end of the calculation.Fig.8c illustrates the visited matrix,which is used to record the coordinates of a point before the current position.The process of the algorithm is described as follows:

Step 1:initialize the matrices

We initialize the marker matrix,distance matrix,and visited matrix in Eqs.(10)–(12):

Algorithm 2 Removing redundant nodes Require:pixel coordinates D(xd,yd)and Ps(xPs,yPs)1:Read the nodes connected to PF←■P1,P2,...,Pf■2:ρPs←|Ps-D|,ξ←1 3:EPs←12ξρ2Ps 4:for i←1,2,···,f do 5: ρPi←|Pi-D|6: EPi←12ξρ2i 7: if EP i＞EPs then 8: Delete node Pi(Pi is a redundant node)9: end if 10:end for Ensure:PM={P1,P2,...,Pm}

whereOis the origin andV1is the set of all the nodes inΩ.

In Eq.(12),when the targeted point is the initial position point,the current position is saved at the initial position point of the visited matrix,and the other positions are saved as empty.

Step 2:find the current point

The distance matrix is traversed to find the coordinate point with the smallest distance.In the marker matrix,we check whether the point has been marked.If it has been marked,we search again until the coordinate point of unmarked minimum distance is found,and then the point is regarded as the current pointPs.

Step 3:remove redundant points

The set of coordinate points connected to pointPs,PF={P1,P2,···,Pf},is extracted with Eq.(6).We calculate the potential energyEPs,EP1,EP2,···,EPf.ComparingEP1,EP2,···,EPfwithEPs,the coordinates with the potential energy greater thanEPsare redundant points,which are marked as 1 in the corresponding coordinates of the marker matrix.We extract the coordinate point set as PM={P1,P2,···,Pm}with the potential energy of the coordinate points being less thanEPs.

Step 4:update allowed access point data

The distances between all the nodes in the PM set and thePspoint are calculated,and let these beL1={l11,l12,...,l1m}.In the distance matrix,let the distance value at the coordinates of thePspoint beLand the distance value of each coordinate point in PM beL3.We addLwith all the distance values inL1to obtain the new distance values of coordinates of each point in PM,denoted asL2={l21,l22,...,l2m}.The distance values of each point in PM’s current position areL3={l31,l32,···,l3m}.At this time,compared with each distance value inL2andL3,ifl2i＜l3i,we replacel3iwithl2iinL3until all elements are compared.At this time,in the marker matrix,thePscoordinate position is marked as 1,and in the visited matrix,thePscoordinate values are stored at each coordinate position in the PM.

Step 5:calculate the route

Steps 2–4 are repeated until the destination coordinateDappears in PM,and then the calculation is stopped.

Step 6:extract the shortest route

We extract the shortest route by reverse derivation.In the visited matrix,the coordinates of the previous connection pointDk-1are extracted from the destinationDcoordinates,and we extract the coordinates ofDk-2at the coordinates ofDk-1until the coordinates of originOare extracted.To this end,the route extraction is completed.The flowchart of APFD is shown in Fig.9,and the execution process is described in Algorithm 3.

Fig.9 Overview of APFD

Algorithm 3 Route calculation Require:map node coordinates 1:Extract the effective area Ω 2:for i←1,2,···,n1-1 do//n1 is the height for j←1,2,···,m1-1 do//m1 is the width if i=0&&j=0 then Mk_max[i][j]←0//Mk_max is the marker Ds_max[i][j]←0//Vd_max is the visited m 3: 4: 5: matrix 6: atrix 7: Vd_max[i][j]←(xo,yo)//Ds_max is the distance matrix 8: else 9: Mk_max[i][j]←0 10: Ds_max[i][j]←∞11: Vd_max[i][j]←?12: end if 13: end for 14:end for 15:while point D does not exist in PF do 16: if point D exists in PF then 17: break 18: end if 19: Ps←min(Ds-max)&&Mk-max(xPs,yPs)/=1 20: Extract all the nodes connected with Ps and obtain PF={P1,P2,···,Pf}21: Calculate EPs and EPF 22: Remove redundant points to obtain PM={P1,P2,···,Pm},m≤f 23: Calculate L1={l11,l12,···,l1m}24: Add value L to each distance value in L1 to obtain L2={l21,l22,···,l2m}25: Let the distance value at the PM be L3={l31,l32,···,l3m}26: if l2i＜l3i then 27: Replace l3i with l2i in L3 28: Vd-max(PM)←Ps 29: Mk-max(Ps)←1 30: end if 31:end while 32:Obtain the optimal route sequence Q(O,Q1,Q2,···,Qk,D)Ensure:Q

5 Performance evaluation

In this section,we validate the performance of the proposed APFD method and then report the experimental results.

In the simulation and real-word maps,the APFD,AC,A*,RRT,APF,NSGA-II,PSO,and Dijkstra methods are first evaluated for the shortest route,and then the experimental results are analyzed in detail.

5.1 Experimental setup

An Intel?CoreTMi7-5557U CPU 3.1 GHz with 4 GB memory is employed on the experimental platform.The number of nodes in the simulation map is 20×40=800.The construction method of the simulation map is shown as follows:starting from the upper left,from left to right,from top to bottom.The horizontal and vertical distance between these nodes is 100±40.The distances between the four vertices of the simulation map and the upper left vertex are{0±40,0±40},{0±40,3900±40},

{1900±40,0±40},and{1900±40,3900±40},and we mark the coordinates of each network node.Considering the upper left vertex as the origin,the horizontal coordinate increases by 1 from left to right,and the vertical coordinate increases by 1 from top to bottom.The four vertex coordinates are(0,0),(0,39),(19,0),and(19,39),and the simulation map generated is illustrated in Fig.10.

Fig.10 Simulation map

Moreover,we employ the GPS trajectory data(about 50 GB)generated by 12 000 taxis in Beijing in November 2012(http://www.datatang.com)to calculate the actual distance between road network nodes on the Fourth Ring Road in Beijing in the extensive experiments.Each record of the GPS trajectory data includes longitude,latitude,and speed.We use the longitude and latitude values of each data record to locate the taxi position,and obtain the longitude and latitude values when a taxi passes through two road network nodes.The spherical distance formula and the longitude and latitude values of two road network nodes are used to calculate the actual distance between adjacent road network nodes.

5.2 Evaluation metrics

This work defines the performance improvement and efficiency improvement as metrics representing the shortest route and execution efficiency,respectively.

5.2.1 Performance improvement

Performance improvement is used to evaluate the shortest route of the algorithm.The larger the percentage of performance improvement,the better the performance of the algorithm.It is defined as

wherelmis the shortest route value of the APFD method,andltis the route value of the compared algorithm.

5.2.2 Efficiency improvement

The efficiency improvement is defined to evaluate the efficiency.The larger the multiple of effi-ciency improvement,the higher the execution effi-ciency of the algorithm.It is defined as

whereTmis the shortest time consumed when the APFD method produces the shortest route,andTtis the time consumed by the compared algorithm.

5.3 Experimental results

Twenty pairs of origin and destination points are randomly selected in the simulation map,and the shortest route and efficiency of the APFD method are evaluated in the experiments.The random coordinate points are shown in Table 1.

5.3.1 Route recommendation evaluation

In the simulation map,the APFD,AC,A*,APF,RRT,NSGA-II,and PSO methods are employed for route planning with 20 pairs of random origins and destinations.The results are shown in Table 2 and Fig.11.

Table 2 shows the total distance value of the shortest route of each method.From Table 2 and Fig.11,it can be seen that for any pair of origin and destination points,the shortest total distance of the APFD method is smaller than those of the AC,A*,APF,RRT,NSGA-II,and PSO methods.The performance improvement percentages of APFD compared with AC,A*,APF,RRT,NSGA-II,and PSO are reported in Table 3.FromTable 3,compared with AC,A*,APF,RRT,NSGAII,and PSO,the route planning ability of APFD is improved 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.As depicted in Fig.12,we select the route diagram of each method at origin(01,34)and destination(11,01)for route analysis.

Fig.11 Comparisons of the shortest route of each method with random coordinates in the simulation map

As can be seen from the experimental results,the path planning effects of AC,A*,APF NSGAII,and PSO algorithms are significantly worse than that of the APFD algorithm.The path planning effect of the RRT algorithm is similar to that of the PAFD algorithm.From Table 2,the total distances of APFD,AC,A*,APF,RRT,NSGA-II,and PSO are 3897,4244,5370,4471,4094,4007,and 4314,respectively.The total distance of APFD is obviously smaller than those of AC,A*,APF,RRT,and PSO.

Table 1 Random coordinate points

Table 2 Total distance of each method in the simulation map

The total distance difference between APFD and NSGA-II is the smallest,and we put the route of APFD and NSGA-II into the same graph,as shown in Fig.12h.Most of the planned path overlaps are different atA,B,C,andD.From these parts,it is obvious that the route of the APFD method is shorter than that of the NSGA-II method.Therefore,the APFD method is better than the NSGA-II method in terms of the total route.It is not diffi-cult to see that the APFD method has better shortest route planning performance than AC,A*,APF,RRT,NSGA-II,and PSO.

Fig.12 Comparison of the shortest route of each method with random coordinates:(a)RRT;(b)A*;(c)APFD;(d)APF;(e)AC;(f)NSGA-II;(g)PSO;(h)APFD with NSGA-II

5.3.2 Efficiency evaluation

In the simulation map,we evaluate the execution time of APFD and Dijkstra using 20 pairs of random origin and destination coordinates.The route planning results of these two methods are the same.The execution time is sorted by APFD,and the results are shown in Table 4 and Fig.13.

As depicted in Table 4 and Fig.13,using 20 pairs of random origin and destination coordinates,the execution time of the APFD method is shorter than that of the Dijkstra method.In detail,according to Eq.(14),we calculate the efficiency improvement of APFD compared with Dijkstra.In Table 4,compared with the Dijkstra method,theexecution efficiency of APFD is improved by 1.03–27.75 times.In summary,when the proposed APFD method is compared with the traditional Dijkstra method,the method has greatly improved the execution efficiency.

Fig.13 Execution time comparison between APFD and Dijkstra in the simulation map

The reason for the above experimental results is that the APFD method uses the origin and destination coordinates to remove the regions with a high possibility that the optimal path will not appear before path calculation,which greatly reduces the calculation time of the algorithm.In addition,in the path calculation,a potential energy field is established in the road network area,and a critical equipotential line is established according to the currentcoordinate position and redundant points(which are removed by comparing the potential energy of each connection point with the critical potential),thereby further improving the execution efficiency of APFD.Therefore,compared with Dijkstra,APFD is exponentially improved in terms of execution efficiency.

5.4 Case study

To verify the effectiveness of the APFD method in real scenarios,we select the road network on the Fourth Ring Road in Beijing for performance evaluation.The method evaluates the shortest route and efficiency to test the effectiveness of the APFD method in the real-world road network.

5.4.1 Route recommendation accuracy

We use 20 pairs of random origin and destination coordinates from the real-world road network in Fig.14 and conducted route planning experiments using APFD,AC,A*,APF,RRT,NSGA-II,and PSO methods to evaluate the route planning ability.The total distance of route planning is sorted by destination.The comparison of the total experimental distance is shown in Table 5 and Fig.15,andthe performance improvement of APFD compared to AC,A*,APF,RRT,NSGA-II,and PSO methods is shown in Table 6.The best route of APFD using one origin and destination pair is illustrated in Fig.16.

Fig.14 Real-world road network:(a)road network on the Fourth Ring Road in Beijing;(b)extracted road network

Fig.15 The shortest route comparison among several methods under random coordinates in the real-word map

Table 5 shows the total distance of the shortest route in the real application.It can be seen that the shortest total distance of the APFD method is shorter than those of AC,A*,APF,RRT,NSGA-II,and PSO methods in all random coordinate points.Using Eq.(13),we calculate the performance improvement of APFD compared to AC,A*,APF,RRT,NSGA-II,and PSO in Table 6.The results demonstrate that the route planning capability of APFD is improvedby 0.73%–39.49%,8.09%–84.75%,5.89%–55.85%,8.08%–44.85%,2.04%–18.35%,and 3.81%–21.55%,respectively.Fig.16 shows the best route of the APFD method with a random origin and destination.From the above experimental result analysis,we can see that APFD has better route planning capability than AC,A*,APF,RRT,NSGA-II,and PSO in terms of the total route planning distance.

Table 5 Total distance of each method in the real-word map

Table 6 Performance improvement of APFD compared with other methods in the real-word map

Fig.16 The shortest route in the real-world road network:(a)road network on the Fourth Ring Road in Beijing;(b)extracted road network

5.4.2 Route recommendation efficiency

In the real map,similar to the simulation map,we compare APFD with Dijkstra on the execution time.The route planning results of these two methods are the same.The execution time sorted by APFD is illustrated in Table 7 and Fig.17.

As shown in Table 7 and Fig.17,the execution time of APFD is shorter than that of Dijkstra.Based on Eq.(14),the execution time of APFD is 1.11–8.82 times that of Dijkstra,which is a significant improvement.In summary,execution efficiency has been greatly improved using APFD in the real-road network.

Table 7 Efficiency comparison between APFD and Dijkstra in the real-world map

Fig.17 Comparisons of the shortest route between APFD and Dijkstra in the real-world map

We randomly select 20 pairs of origin and destination coordinates on the simulation map and realword map.From the experimental results,the route planning ability of the APFD method is significantly better than those of AC,A*,APF,RRT,NSGAII,and PSO methods.Furthermore,APFD has a shorter execution time compared with the traditional Dijkstra method.

6 Conclusions and future work

To quickly and efficiently recommend optimal route for taxis,we proposed an efficient route recommendation method(named APFD)based on the APF and Dijkstra methods.We first extracted the regions in which the optimal route via the origin and destination would likely be found,and then used the APF method to remove network nodes that might not form the optimal route,namely,redundant points.Finally,the Dijkstra method was used to complete the optimal route recommendation.To validate the effectiveness of the proposed APFD method,we employed a simulation map and a real-word road network map on the Fourth Ring Road in Beijing.In these two maps,APFD,AC,A*,APF,RRT,NSGA-II,PSO,and Dijkstra methods were compared on route planning capabilities.For the comparison of the execution time of the above methods,in the simulation map and realword map,we randomly chose 20 pairs of origin and destination coordinates as the research objects for route planning.In the simulation map,compared with AC,A*,APF,RRT,NSGA-II,and PSO,the route planning capability of APFD was improved 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.In terms of execution efficiency,the APFD method proved to be 1.03–27.75 times better compared to the Dijkstra method.In the real-word map,compared to AC,A*,APF,RRT,NSGA-II,and PSO,the route planning capability of APFD was improved by 0.73%–39.49%,8.09%–84.75%,5.89%–55.85%,8.08%–44.85%,2.04%–18.35%,and 3.81%–21.55%,respectively.Compared with the Dijkstra method,the execution efficiency of the APFD method was enhanced by 1.11–8.82 times.In the simulation map and real-world map,the proposed APFD method was significantly better than AC,A*,APF,RRT,NSGA-II,and PSO in route planning.The execution of our APFD method was greatly more efficient than that of the traditional Dijkstra method.

In future work,we will increase the complexity of the road network to validate the proposed method.We will also add traffic flow parameters in the road network,so that the method can update the optimal route in real time based on the current location of the taxi and the locations of passengers.

Contributors

Wenyong ZHANG and Dawen XIA designed the research.Wenyong ZHANG,Dawen XIA,and Huaqing LI proposed the approach and performed the experiments.Guoyan CHANG,Yang HU,Yujia HUO,and Fujian FENG processed the data.Wenyong ZHANG,Dawen XIA,and Huaqing LI drafted the paper.Wenyong ZHANG,Dawen XIA,Yang HU,Yantao LI,and Huaqing LI revised and finalized the paper.

Compliance with ethics guidelines

Wenyong ZHANG,Dawen XIA,Guoyan CHANG,Yang HU,Yujia HUO,Fujian FENG,Yantao LI,and Huaqing LI declare that they have no conflict of interest.