Dynamic Taxi Service Planning by Minimizing Cruising Distance Without Passengers Page: 7,006

                                
IEEE EZ. Luo et al.: Dynamic Taxi Service Planning by Minimizing Cruising Distance Without Passengers

a pruning algorithm to speed up the searching process
is proposed.
3) A proof of the monotonicity of the PCD evaluation
model [13]. The PCD model takes account of the prob-
ability of taking a passenger along the route and can be
used in a more widely situation.
The remainder of this paper is organized as follows.
Section II reviews the related works on route recommenda-
tion. Section III presents the problem formulation and the
system framework. Section IV presents the proposed method
for taxis recommendation based on the PCD model. This
section discusses the PCD evaluation model and the route
recommendation algorithm. Section V discusses our exper-
imental results using real-world taxi tracer data. Section VI
concludes the paper with a summary and future work.
II. RELATED WORKS
In recent years, there are many research on taxi route rec-
ommendation [11], [12], [14]-[17]. Ge et al. [10] propose a
taxi recommendation system to find shortest potential travel
distance (PTD) for taxi driver to pick up a passenger. The
taxi route recommendation system tries to provide an efficient
route for taxi drivers using massive trajectory data. The mas-
sive taxi trajectory data also used in other area such as predict
human mobility style [18] and find fastest route [19] [20].
Substantial attention has also been given to the algo-
rithm of taxi dispatching to improve the performance of
transportation systems. Miao et al. [21] design a data-driven
distributional robust vehicle balancing method to improve
the average system performance. Seow et al. [22] focus on
more globally increasing customer satisfaction by concur-
rently dispatching multiple taxis to the same number of
customers in the same geographical region and allowing
taxis to exchange their booking assignments. Miao et al. [23]
propose a receding horizon control framework for large-
scale taxi dispatching considering both current and future
demand. Zhang and Pavone [24] develop a closed-loop, real-
time rebalancing policy for autonomous vehicles to ensure
acceptable quality of service.
Ma et al. [25], [26] concern the real-time taxi share system,
which tries to save energy by share a taxi among different
people who have overlap trajectory. The main problem they
try to solve is how to balance the need for taxi drivers and
passengers. It is also important to make a real-time decision
in the dynamic environment.
The recommendation problem complexity and improve
the performance is also important. Statistics show that most
recommendation problems are exponentially [27]. So some
research [8], [28] try to use a data structure such as KD-tree
and variant to minimize search. In this paper, we propose
an algorithm for a group of competing taxis at a different
position to minimize the overall potential cruising distance.
Our previous conference paper [13] propose a PCD evaluate
model. The model is correct in a more wide condition than
previous widely used PTD model. In this paper, we provide a

C,  D2=100m-4,
P1=0.5        P2-0.7
PoTaxi
C3  D  0m    C
FIGURE 1. Two candidate path at time tp. PoTaxi is the current position of
a taxi which require recommendation. node C; is the recommended
pick-up point, P; pick-up rate at the point, D; is the distance from node
C,1 to node C;.
proof of monotonically of PCD function and based on which
we propose a recommendation method which considers the
impact of the current recommendation on the next.
III. OVERVIEW
A. PROBLEM FORMATION
The route recommendation problem is to find an optimal
route. Here we define the optimal route to be which have a
minimal PCD to pick up a customer. And the PCD is defined
as a function of a taxi's current position PoTaxi, current time
tp, the route R which the taxi will follow. So the PCD function
is PCD(Po Taxi, tp, R) where the route R is a serial of pick-up
points, i.e., R = {C1-> C2 -  ... -> CK}. The length of
route R denotes as I R  = K, the number of pick-up points.
In some occation, we also denote the current position of a taxi
(PoTaxi) as Co.
Currently, most researchers agree that the conditional prob-
ability for getting a passenger at a pickup point and the
cruising distance to that point is a good representation of
the route property. So, the PCD is PCD(PoTaxi, tp, PR, DR)
where PR = {P1, P2,.-, PK } denotes the picking-up rate at
the pick-up points along route R; DR =  {D1, D2, ...,DK I
represents the distance from previous pickup point to the
current pickup point along route R.
So, the optimal path recommendation problem is to mini-
mize the route to pick-up points: minRERset PCD(PoTaxi, tp,
PR, DR) where Rset is the set of route R, which is generated
from a potential pick-up point set C and which are generated
from tracers of experience taxi driver.
The taxis route recommendation problem is to recommend
optimal route for each taxi driver in different position to
minimize the overall potential cruising distance. Given a set
of the position (PoTset), a set of taxis (Mset), current time (tp),
the taxis route recommendation problem can be formulated
as: arg min  pEPOTset LmEMset(p) PCD(p, tp, PR, DR) Fig. 1
shows an example of two possible paths at a time period tp.
The widely used evaluation model PTD consider-
ing pickup cruising distance described as: PTD    =
Yn_1 P(CJiR, tp)D(Ci_, Ci) Where P(CJiR, tp) is the con-
ditional probability of picking up passengers along route R
at point Ci. This model is correct only if two routes have
the same probability; otherwise, this is not applicable. As an
example in Fig. 1, according to PTD definitioan, the PTD
of route R1 would be P1D1 + (1 - P1)P2(D1 + D2) = 120

VOLUME 6, 2018

70006