1

An Online Ride-Sharing Path Planning Strategy for
Public Vehicle Systems

arXiv:1712.09356v1 [] 27 Dec 2017

Ming Zhu, Xiao-Yang Liu, and Xiaodong Wang, Fellow, IEEE

Abstract—As efficient traffic-management platforms, public
vehicle (PV) systems are envisioned to be a promising approach to
solving traffic congestions and pollutions for future smart cities.
PV systems provide online/dynamic peer-to-peer ride-sharing
services with the goal of serving sufficient number of customers
with minimum number of vehicles and lowest possible cost. A key
component of the PV system is the online ride-sharing scheduling
strategy. In this paper, we propose an efficient path planning
strategy that focuses on a limited potential search area for each
vehicle by filtering out the requests that violate passenger service
quality level, so that the global search is reduced to local search.
We analyze the performance of the proposed solution such as
reduction ratio of computational complexity. Simulations based
on the Manhattan taxi data set show that, the computing time
is reduced by 22% compared with the exhaustive search method
under the same service quality performance.
Index Terms—Path planning problem, potential search area,
public vehicle systems, online/dynamic peer-to-peer ride-sharing.

Cloud
Destinations

Smart phones

Pick up

Parking

Origins
Charging

PVs

Supercharger
stations

Passengers

Fig. 1. Architecture of PV systems.

I. I NTRODUCTION
Existing transportation systems are not satisfying due to
large investments, high congestions, serious pollutions and
potential health problems [1]. We hope that our transportation policies and programs can serve our economic, social,
and environmental goals. Some research shows that the total
industrial and consumer expenditure on transportation is about
10% of GDP (gross domestic product) in the world [2]. In
the USA, around 16.7% of the household income is spent
on transportation [3]. Besides the large investments, many
countries are suffering from social problems such as traffic
congestions [4] and fuel pollution-related diseases [5] brought
by transportation. The vehicle fuel pollution accounts for 31%
of all pollution in Beijing [6], and the Beijing city government
has spent $277 billion during 2011-2013 [6] on air pollution.
However, the PM2.5 (particulate matter with diameter of 2.5
micrometers or less) level is still high [7]. To address the
above problems, ride-sharing is a promising solution that is
cost-effective.
As an application of sharing economy [8], public vehicle
(PV) systems [9] [10] [11] [12] provide low-cost peer-to-peer
M. Zhu is with the Shenzhen Institutes of Advanced Technology, Chinese
Academy of Sciences, Shenzhen, China, and the Department of Computer
Science and Engineering, Shanghai Jiao Tong University, Shanghai, China,
E-mail: zhumingpassional@gmail.com, zhumingpassional@sjtu.edu.cn.
X.-Y. Liu is with the Electrical Engineering Department, Columbia University, New York City, US, and the Department of Computer Science
and Engineering, Shanghai Jiao Tong University, Shanghai, China. E-mail:
xiaoyang@ee.columbia.edu.
X. Wang is with the Department of Electrical Engineering, Columbia
University, New York, NY, 10027, USA (E-mail: wangx@ee.columbia.edu).

ride-sharing trips with ensured quality of service (QoS) for
passengers. As shown in Fig. 1, a PV system consists of three
parts: a cloud, PVs, and passengers. The blue solid lines denote
the communications between them, and the dash black lines
imply the scheduling task of a PV. In addition, future PVs
are envisioned to be self-driving electric vehicles, therefore
charging [13] is an important issue.
The operation of a PV system is as follows. If a passenger
needs a trip service, he/she sends a request (including the
earliest start time, the origin, and the destination, etc.) through
a mobile internet device (e.g., smart phone) to a cloud. The
cloud computes a path plan with a confirmed ride match
to serve him/her. He/She can access the information of the
confirmed PV through apps, e.g., vehicle ID, position, speed,
and path. PVs serve passengers by traversing from origins
(pick-up points) to destinations (drop-off points). Compared
with conventional public transportation systems such as buses
and subways which also provide ride-sharing services, there
is no last mile problem in PV systems, and PVs are more
flexible since their paths are adapted to the trip demands of
passengers, while the paths and the schedules of buses and
subways are fixed.
PV systems are also different from existing ride-sharing
systems (e.g., Uber Pool [14] and Didi [15]). Here, we
describe several important differences. 1) PV systems are
centralized systems which provide online/dynamic peer-topeer ride-sharing services, while existing ride-sharing systems
such as Uber Pool are distributed offline/static systems. 2) In
PV systems, scheduling strategies are calculated by the cloud,

2

while in existing ride-sharing systems, scheduling strategies
are negotiated by drivers and riders. 3) PVs cooperate with
each other to improve traffic efficiency, e.g., multi-hop ridesharing paths [16], while in existing ride-sharing systems,
drivers compete for more profit.
In this paper, we investigate the efficient ride-sharing path
planning problem in PV systems. The existing solutions [9]
[17] [18] become inefficient since most of them are based
on exhaustive search, and only some of them [19] considers
computational efficiency while the QoS can not be guaranteed.
We study this problem in a practical setting by exploiting
QoS constraints and geometry, and then propose a local search
solution.
The challenges of our problem are as follows. 1) There
is a trade-off between the objectives of passengers and PVs:
PVs try to serve more passengers with the minimum energy
cost or travel distance; where passengers want to arrive at
their destinations as early as possible with low cost. 2) The
online/dynamic ride-sharing in PV systems involves multiple
passengers’ utilities. If the utility of a passenger is compromised by serving some other passengers, e.g., a long detour,
he/she would choose other type of service such as taxi. 3)
When the cloud receives new trip requests, new schedules will
be calculated and paths of some PVs may change.
The contributions of this paper include the following.
• To the best of our knowledge, this is the first work
that considers computational efficiency in online/dynamic
ride-sharing for PV systems aiming at reducing the travel
distance of vehicles with QoS guarantee.
• We propose an efficient path planning strategy by restricting the search areas for PVs, reducing the global search to
local search. It is suitable for real-time implementation.
• We analyze the performance of the proposed solution,
and find that the larger is the city, the better performance
(reduction ratio of computational complexity) our proposed solution will have.
• The strategy balances the utilities of passengers and PVs,
i.e., providing high QoS (e.g., short waiting time, and less
detour) for passengers with low energy cost.
• We perform simulations with the trip requests based on
the Manhattan taxi data set to evaluate the proposed
strategy. A large amount of computation can be saved.
The travel distance of PVs is reduced, and the ridesharing for passengers can be guaranteed compared with
privately owned electric vehicles.
Related work on ride-sharing path planning problems in PV
or PV-like systems is described in Section II. In Section III,
we present the problem formulation. Section IV and Section
V detail the solution and its performance analysis respectively.
Section VI provides simulation results. Section VII concludes
this paper.
II. R ELATED W ORK
Some ride-sharing path planning strategies are restricted to
some special cases such as common origins or destinations.
In particular, Massobrio et al. [20] propose evolutionary algorithms to solve the one-origin-multi-destination taxi-sharing

problem, where the QoS metrics include the total trip cost and
time delay of passengers. Naoum-Sawaya et al. [21] present
a stochastic mixed integer programming model to optimize
the allocation of cars to employees (from homes to work
places) while taking into account the unforeseen events of car
unavailability. It only focuses on ride-sharing with common
destinations in large organizations, e.g., companies, hospitals,
and universities. Shang et al. [17] propose a collective travel
planning query to find the lowest cost path connecting multiple
origins and a destination with limited number of meeting
points. However, all the above solutions can not be used
in the multi-origin-multi-destination scenario, which is more
common in the real world.
Most of current ride-sharing path planning strategies in the
multi-origin-multi-destination scenario are exhaustive search
methods, which incur high computational load at the cloud.
Zhu et al. [9] propose an algorithm to reduce travel distance
of vehicles with QoS constraints for passengers, e.g., detour,
which needs to try each request and calculate corresponding detour constraints. Goel et al. [22] propose a solution
which selects the optimal fixed positions of pick-up points
to maximize the vehicle occupancy rates while preserving the
passenger privacy and safety, where passengers do not need to
provide their precise home or work positions. To maximize the
vehicle occupancy and minimize the travel time with limited
detour, Jung et al. [18] propose a hybrid-simulated annealing
to dynamically assign passenger requests for online/dynamic
ride-sharing, which is computationally expensive especially
when the number of requests is large since multiple random
perturbations and a large number of iterations are needed.
Less work focuses on how to reduce the computational
complexity and restrict the search areas in online/dynamic
ride-sharing in PV or PV-like systems [19]. To reduce the total
travel distance of taxis, Ma et al. [19] propose an efficient ridesharing path planning solution in serving dynamic queries,
where “lazy shortest path” calculation is used by means of
partitioning the whole road network into multiple grids, and
the status of each vehicle should be updated according to
preset intervals. This work only considers how to reduce
the computational complexity based on the current distance
between vehicles and origins/destinations of requests. Ota
et al. [23] propose a real-time and data-driven simulation
framework to achieve the efficient analysis of taxi ride sharing
by means of exploring parallelism and cache-coherent shortest path index, which also considers different stakeholders’
interests and constraints, e.g., the waiting time, the maximum
number of additional stops, the maximum number of shared
trips.
In summary, most online/dynamic ride-sharing solutions in
PV or PV-like systems are based on computationally expensive
exhaustive search. Only a few solutions focus on reducing
the computational complexity [19] [23]. However, the road
network should be divided into cells and the states of vehicles
should be frequently updated, making the methods complicated. Our proposed solution in this paper is more efficient,
easy to implement, and can be used in large cities. Moreover,
the QoS level of passengers can be guaranteed, e.g., short
waiting time and less detour.

3

III. PV R IDE -S HARING P LANNING P ROBLEM
In this section, we first present preliminaries for our
problem, and then detail the problem formulation and NPcompleteness.
A. Preliminaries
We assume that all PVs in a city constitute a set P, and all
requests constitute a set R. Let Ru be a set of unscheduled
requests, and Rs be a set of scheduled requests. We assume
that once the ride match between any request r and PVs has
been S
confirmed by the cloud, it does not change. Let Rs =
Rs,1 Rs,2 , where Rs,1 is a set of requests being served (has
been picked up yet not dropped off) by PVs and Rs,2 is the
set of requests waiting to be served (the ride match
S has been
confirmed yet not picked up). Clearly, R = Ru Rs .
In the PV ride-sharing planning (PVRSP) problem, each
request r ∈ R should be served by a corresponding PV, while
on the path of any PV, it can serve other unscheduled requests
if there exist available seats. Let r = (n, t, o, d) ∈ R denote
a trip request, where n is the number of passengers, t is the
earliest start time, o is the origin (pick-up point), and d is
the destination (drop-off point). We assume the passengers
using the same request should be served together by a PV.
For request r1 ∈ Rs,1 , it has been picked up so that its origin
is not important anymore and only its destination should be
reached. However, for request r2 ∈ Rs,2 , both the origin and
the destination should be reached with the origin preceding
the destination. Let p ∈ P denote a PV or its current position.
Next, to describe our problem clearly, we introduce three
definitions: schedule, service list, and path. And then we
present an example to discuss their changes in the execution
of a path planning strategy in PV systems.
Definition III.1. The schedule for any request r = (n, t, o, d),
means that if a PV p is scheduled to r with the earliest
start time t, p will transverse through the origin o and the
destination d with o preceding d, and meanwhile p will pick
up r (n passengers) at o, and drop off r at d.
In Definition III.1, a schedule mainly determines the ride
match between the request and PVs, and the precedence constraints between the origin and the destination. The schedule
for a request makes sure that this request will be transported
from the origin to the destination.
Definition III.2. The service list of any PV p, denoted by Lp ,
is a list of requests p has to serve, including the requests being
served (have been picked up by p, yet have not arrived at their
destinations), and the requests waiting to be served (scheduled
to p, yet have not been picked up), while the requests dropped
off by p are not included.
In Definition III.2, the service list Lp of PV p clearly points
out which requests should be served and implies where to pick
up or drop off corresponding passengers. Let L be a set of
service lists of all PVs. Lp has two parts, the requests being
served, and the requests waiting to be served by p. Once a new
request is assigned to PV p, it will be put to the service list.
Once a scheduled request is dropped off at its destination, it

TABLE I
VARIABLES AND NOTATIONS
n
t
o
d
δ
∆
b
B
w
W
C
Lp
Qp
D(i, j)
E(i, j)
Tr
P
p
ps
r
R
Rs
Rs,1
Rs,2
Lp
L
Qp
Q
η
Â1 /A1
Â2 /A2
Â/A
Âopt /Aopt
β̂/β
β̂ opt /β opt
α̂/α
α̂opt /αopt

number of passengers of r.
earliest start time of r.
origin of r.
destination of r.
detour ratio of request r.
maximum detour ratio.
buffer distance of request r.
buffer distance threshold.
waiting time of request r.
waiting time threshold.
capacity of PVs.
service list of PV p.
path of PV p.
shortest path distance from position i to j.
Euclidean distance from position i to j.
travel distance of request r.
a set of all PVs in a city.
a PV.
position of PV p at the schedule time of r.
a request.
a set of all requests.
a set of scheduled requests.
a set of requests being served.
a set of requests waiting to be served.
service list of PV p.
a set of service lists of all PVs.
path of PV p.
a set of paths of all PVs.
ratio of PSA and optimal PSA (PSAopt ).
PSA of p if the furthest request r has been picked up,
and A1 = |Â1 |.
PSA of p if the furthest request r has not been picked
up, and A2 = |Â2 |.
PSA of PV p, and A = |Â|.
PSAopt of p, and Aopt = |Aˆopt |.
PSA determined by (o, d), and β = |β̂|.
PSAopt determined by (o, d), and β opt = |β̂ opt |.
PSA determined by (ps , o), and α = |α̂|.
PSAopt determined by (ps , o), and αopt = |α̂opt |.

will be removed from the service list. We see that, the service
list is determined by both the ride-sharing planning strategy
and the motion states of PVs, and it dynamically changes over
time.
Definition III.3. The path of PV p, denoted by Qp , is a
sequence of points p has to serve, which includes the current
position of this PV, the destinations of the requests being
served by it and the origin-destination pairs of the requests
waiting to be served by it.
In Definition III.3, we see that the path of each PV dynamically changes over time, and is composed of the current
position of this PV, the origin-destination pairs of requests
waiting to be served and the destinations of requests being
served. Let Q be a set of paths of all PVs. All the important
variables and notations in this article are summarized in
Table I, where PSA is the abbreviation of “potential search
area” which will be detailed in the subsequent sections, and
the unit of D(i, j), E(i, j), Tr , b, and B is km.
We take an example to illustrate the changes of the schedule,
path, and service list. We assume the previous service list of
PV p is {1, 2, 3}, and the previous path is {x → o1 → o2 →
o3 → d2 → d1 → d3 } where x is the current position of p.

4

The change of path has two cases. First, the service list does
change while the path changes. For example, after a certain
time, the path becomes {x0 → o2 → o3 → d2 → d1 → d3 }
where x0 is the new position of p. Second, both the service
list and the new path change. For example, after a certain
time, the cloud receives a new request r4 , and calculates the
new ride-sharing path, and finally assigns p to serve r4 . The
service list of p becomes {1, 2, 3, 4}, and the path becomes
{x0 → o1 → o2 → o3 → o4 → d2 → d1 → d3 → d4 }.
B. Problem Formulation and NP-Completeness
To improve the profits, PVs try to serve more passengers
with less travel distance; however, this reduces the user satisfaction. To improve the service quality, passengers want to
arrive their destinations as early as possible, i.e., to reduce the
waiting time and travel time. To balance the utilities of PVs
and passengers, we consider the total utilities of both sides to
achieve the best social welfare.
The detour ratio of a request is considered as the passenger
QoS. We assume p serves r. With respect to request r, the
actual travel distance Tr is not shorter than D(o, d), the
shortest path distance from the origin o to the destination d.
The detour ratio is defined as δ = (Tr − D(o, d)) / D(o, d).
The QoS constraint is then δ ≤ ∆ where ∆ is the maximum
detour ratio set by the cloud, which aims at preserving the
comfort [6] of passengers.
The latest arrival time is not considered here for several
reasons. 1) It is hard to accurately predict the speed due to
traffic congestions, emergencies, and accidents, although some
researchers have proposed new solutions [24]. 2) It is hard to
ensure that a passenger can arrive at his/her destination before
the latest arrival time he/she set, even taking a car or taxi.
The PVRSP problem is formulated as follows. Given a set
of PVs P on the road networks with the current service lists
L and paths Q, a set of scheduled requests Rs,2 waiting to
be served, and a set of unscheduled requests Ru , the cloud
determines the new service lists L0 and new paths Q0 of all
PVs ensuring that all requests can be served from origins to
destinations with QoS constraints (the detour ratio is no larger
than the maximum value ∆), which aims to reduce the total
travel distance of PVs and the waiting time of passengers with
QoS guarantee.
Now, we discuss the NP-completeness of the PVRSP problem. It is known to all that the dial-a-ride problem (DARP)
[25] is NP-complete [25], which is a special case of the
PVRSP problem. Therefore, the PVRSP problem is also NPcomplete.
Here, we mention the differences between the two problems
PVRSP and DARP. In the DARP problem, all vehicles are
based at a single depot, whereas, in the PVRSP problem, vehicles are distributed at different locations. The DARP problem
is an offline/static ride-sharing process, i.e., all requests are
known and all passengers stay at their origins waiting to be
served, and it does not consider serving other unscheduled
requests on the vehicle paths. On the other hand, the PVRSP
problem focuses on online/dynamic ride-sharing so that more
complex scenarios should be considered, e.g., the precedence

o''
o'

o

p

d

Fig. 2. PSA determined by the furthest request r which has been picked up:
Â1 = β̂.

constraints between current positions of PVs and the origindestination pair of each request, and the predetermined match
between each scheduled request and the corresponding PV.
IV. P ROPOSED S OLUTION
In this section, we first introduce some heuristics to restrict
the potential search areas for PVs, and then describe a key
routine of calculating the insertion cost of an origin-destination
pair, and then propose an algorithm for online updating PV
ride-sharing paths, and finally use an example to illustrate the
algorithm.
A. Heuristics
The potential search area (PSA), is an area that points out
that the origins or/and destinations of requests in this area
are possible to served with ensured QoS (denoted by detour),
while the other requests violating QoS constraints are not in
this area and should be excluded.
We name r as the furthest request if its destination d is
the last point on the path of the PV which serves r. In
the following, we discuss PSA in two conditions, i.e., if the
furthest request has been picked up or not. Then, we first
describe two cases of PSA for a request, and then derive the
PSA of a PV. Here, the PSA of a request and the PSA of a
PV are two distinct concepts, while the latter is derived from
the former.
1) The furthest request has been picked up
We assume p serves r. As shown in Fig. 2, if we insert
new points (origins or destinations of other requests) between
p and d. we should restrict an area such that δ (the detour
ratio of r) should not exceed its maximum value ∆.
Lemma IV.1. Any point (the origin or destination of any
request) inserted between o and d should fall in an ellipse
determined by o and d, otherwise, the QoS will be violated.
Proof. In Fig. 2, a point, e.g., o0 (origin of r0 ) will be inserted
between o and d. Let D(i, . . . , j) and E(i, . . . , j) denote the
shortest path distance and Euclidean distance from the first to
the last location among positions (i, i + 1, . . . , j) respectively.
Obviously, (1 + ∆)D(o, d) ≥ D(o, o0 , o00 , d) ≥ E(o, o0 , o00 , d),
i.e., if we draw an ellipse centering at o and d with the major
axis (1 + ∆)D(o, d), the insertion points should fall in this
ellipse. Otherwise, δ (the detour ratio of r) will exceed the
maximum value ∆, and the QoS of r will be violated.
To simplify the computation, instead of an ellipse (denoted
by the dashed blue line in Fig. 2), we use the corresponding

5

B. A Key Routine

ps

p

o

d

Fig. 3. PSA S
determined by the furthest request r which has not been picked
up: Â2 = α̂ β̂.

rectangle (denoted by the solid blue rectangle in Fig. 2) to
check if the points satisfy the QoS constraints. The enlarged
area is limited, which is denoted by the shadowed areas in
Fig. 2. We know D(o, d) ≥ E(o, d). The PSA determined by
(o, d) is denoted by β̂. Let β = |β̂|, which is shown by
β = (1 + ∆) D(o, d)

p

(1 + ∆)2 D2 (o, d) − E 2 (o, d).

Finally, we get the PSA of p if the furthest request r has been
picked up by Â1 = β̂. Let A1 = |Â1 |, therefore, A1 = β.
2) The furthest request has not been picked up
Let the schedule time denote the time when schedule of
r is confirmed. To limit the waiting time of r, we introduce
the buffer distance, b (km) with a threshold B (km), which
denotes the travel distance of p from the schedule time to its
pick-up time. Here, we should record the position of PV p at
the schedule time of r, which is denoted by ps just as shown
in Fig. 3. Similarly, we can get the PSA determined by (ps , o)
which is denoted by α̂ with α = |α̂|, and the PSA determined
by (o, d) which is denoted by β̂ with β = |β̂|. We obtain
the PSA of p if the furthest request r has not been picked up
denoted by Â2 with A2 = |Â2 | through the union of α̂ and β̂.

Calculating the insertion cost of an origin-destination pair
is a key routine in the proposed algorithm. For a new request
r ∈ Ru , its origin o has to be visited before its destination d.
Therefore, if p decides to take request r, both o and d need to
be inserted into its current path with the precedence constraint
being satisfied.
Definition IV.1. Assume that r is taken by p. The insertion
cost φr,p,i,j at (i, j) is the additional travel distance of p if
inserting an origin-destination pair (o, d) of r at the ith and
j th positions respectively on the path of p with o precedes d.
Let Qp = {θ0 , θ1 , . . . , θK } denote the current path of p,
where θ0 is the position of this PV. Let D(θi , . . . , θj ) =
D(θi , θi+1 ) + . . . , +D(θj−1 , θj ) (i < j) denote the sum of
shortest path distance from θi to θi+1 , . . . and to θj . (3)∼(6)
describe four cases. The first case given by (3) means that d
is not the last point of the path, and o immediately precedes
d. The second case given by (4) means that d is the last point,
and o immediately precedes d. The third case given by (5)
means that d is the last point, and o does not immediately
precede d. The fourth case given by (6) means that d is not
the last point, and o does not immediately precede d. Let a
function Qp = INSERT(r, p, i, j) returns Qp (the path of p) by
inserting the origin o and the destination d of r at the ith and
j th positions respectively on the path of p.
φr,p,i,j

if 0 ≤ i ≤ K − 1, j = i + 1,
φr,p,i,j

if i = K, j = i + 1,
φr,p,i,j

Next, we discuss the PSA of a PV. We assume that request r
with the origin o and the destination d is the furthest request.
The request r0 with the destination d0 is a request which is
being served by p. We choose the PSA determined by the
furthest request (i.e., r) not others (e.g., r0 ) as the PSA of PV
p. The reason is that, if we choose r0 to calculate PSA of p,
we only consider the insertion positions between the current
position of p and d0 , such that the insertion positions between
d0 and d are ignored.
Let Â denote the PSA of PV p with A = |Â|, which has
two cases and is determined by if the furthest request r has
been picked up:
(
β̂,
if r has been picked up,
Â =
(1)
S
α̂ β̂, otherwise,
and
(
A=

=

β,
if r has been picked up,
S
|α̂ β̂|, otherwise.

(2)

=

(4)

D(θi , o, θi+1 ) + D(θK , d) − D(θi , θi+1 ),
if 0 ≤ i ≤ K − 1, j = K + 1,

φr,p,i,j

(3)

= D(θK , o, d),

p

W 2 − E 2 (ps , o),
[
Â2 = α̂ β̂.
α=W

= D(θi , o, d, θi+1 ) − D(θi , θi+1 ),

(5)

D(θi , o, θi+1 ) + D(θj , d, θj+1 )
−D(θi , θi+1 ) − D(θj , θj+1 ),
if 0 ≤ i ≤ K − 1, j ≤ K, j 6= i + 1.

(6)

C. Algorithm
The basic idea of the proposed solution is that, we draw
a search area for each PV in three cases according to the
insertion positions of origin-destination pairs of requests which
ensures that serving the requests out of this search area leads
to the violation of QoS, so that we only search requests in this
limited search area instead of the whole city.
Here, we discuss three insertion cases using PSA on the
paths of PVs according to the insertion positions of requests.
In order to insert the origin-destination pair of a new request
r, select a position θi (0 ≤ i ≤ K) of path of p to insert o
after θi . Then from the positions after o select another position
θj (i + 1 ≤ j ≤ K + 1) to insert d. As shown in Fig. 4, there
are three cases according to the final insertion positions of the
origin and the destination:
Case A: None of the origin (o1 ) and the destination (d1 )
becomes the last point of the new path.

6

insertion cost for all PVs. Lines 23∼26 imply that, if the cloud
can find a suitable PV to serve the request, the path and the
service list of this PV should be updated, and this request
will be removed from the set of unscheduled requests. Lines
27∼28 means that, if destination of the newly inserted request
becomes the last point on the path, the PSA of this PV should
also be updated, since the PSA is determined by the furthest
request.

Case A

ps

p

o

o1

ps

p

o

o2

d1

d

Case B

d

d2

Algorithm 1: PSAP
Case C

ps

p

o

d

o3

d3

Fig. 4. Corresponding PSA in three insertion cases.

Case B: The destination (d2 ) becomes the last point of the new
path, while the origin (o2 ) does not precede d2 immediately.
Case C: The destination (d3 ) becomes the last point of the
new path, and the origin (o3 ) precedes the d3 immediately.
In Fig. 4, we can see the corresponding PSA in three
insertion cases. d is the last point on the path before new
requests are inserted. (oi , di ) is the origin-destination pair of
request ri (i ∈ {1, 2, 3}). The three requests r1 , r2 , and r3
belong to cases A, B, and C respectively. The red lines denote
the previous PSA of this PV, and the green lines in cases B
and C denote the new PSA of this PV. Fig. 4 implies that the
PSA in cases B and C has changed since the destination of
the newly inserted request becomes the last point on the path.
Finally, we discuss case C: all points of the previous path
of p fall in the PSA α̂, which is determined by the current
position of p and o since the PSA determined by o and d can
be ignored.
If we only consider restricting an area for each PV, there
may exist some “dead zones” such that some unscheduled
requests do not satisfy QoS constraints of any PSA of PVs for
a long time. To avoid this condition, we introduce a waiting
time threshold W for each request. Let w denote the waiting
time for request r. If w is larger than a threshold W , we
directly calculate the insertion cost, ignoring the check about
the buffer distance and PSA.
Algorithm 1 details the proposed solution named as PSAbased path planning algorithm (PSAP). Here, δ 0 and b0 are the
detour ratio and buffer distance of request r0 respectively. At
some time t0 , the cloud selects the unscheduled requests Ru ,
whose earliest start time is not later than t0 . Then the cloud
sorts requests Ru in the descending order of their waiting
time. In this algorithm, we assume PSA of all PVs have been
calculated using (1) and (2), which can be inferred by line 28.
The waiting time of requests is balanced in line 2 such
that the waiting time of each request will not be too long.
Lines 5∼6 check capacity constraints. Lines 9∼14 mean that,
this algorithm first checks if the origin and/or destination of
the request are/is in PSA, and then calculates the insertion
cost in three cases (A, B, and C). In lines 15 and 19, the
QoS constraint is checked. Line 21 calculates the minimum
insertion cost for PV p, and line 22 calculates the minimum

Input: Ru , set of unscheduled requests;
{Qp }p∈P , current paths of PVs;
{Lp }p∈P , current service lists of PVs;
Output: R0u , new set of unscheduled requests;
{L0p }p∈P , new service lists of PVs;
{Q0p }p∈P , new paths of PVs;
01: Initialization:{Q0p } ← {Qp },{L0p } ← {Lp },R0u ← Ru ;
02: Sort the unscheduled requests in the descending
order of their waiting time;
03: for r ∈ Ru do
04: for p ∈ P do
05:
if |L0p | + n > C then
06:
φr,p ← ∞;
07:
else
08:
if w ≤ W
09:
if o ∈ Â AND d ∈ Â
10:
Calculate {φr,p,i,j }i,j of case A;
11:
if o ∈ Â AND d ∈
/ Â
12:
Calculate {φr,p,i,j }i,j of case B;
13:
if All points on path of p fall in α̂
14:
Calculate {φ
S r,p,i,j }i,j of case C;
15:
if ∃ r0 ∈ {r Lp }, δ 0 > ∆ OR b0 > B
16:
φr,p,i,j ← ∞;
17:
else
18:
Calculate {φS
r,p,i,j }i,j ;
19:
if ∃ r0 ∈ {r Lp }, δ 0 > ∆
20:
φr,p,i,j ← ∞;
21:
φr,p ← min{φr,p,i0 ,j 0 }i0 ,j 0 ;
22: φr ← φr,p0 ,i00 ,j 00 = min{φr,p }p ;
23: if φr 6= ∞ then
24:
Q0p0 ← INSERT(r, p0 , i00 , j 00 ); // Update path
S
25:
L0p0 ← L0p0 {r}; // Update service list
26:
R0u ← {R0u \r}; // Update the set of unscheduled requests
27:
if d becomes the last point on path of p0
28:
Calculate A0 ; // Update PSA of p0

D. Example
Fig. 5 shows an example to illustrate the PASP algorithm,
which has two stages. In the first stage, a PV serves three
requests 1, 2, and 3, i.e., the service list is {1, 2, 3}, and the
current path is {x → o2 → o3 → d1 → d3 → d2 } where
x is the current position of this PV, oi is the pick-up point
of request i and di is the drop-off point of request i with
i = {1, 2, 3, 4, 5}. We can see that request 1 has been picked
up and others are still waiting to be served. Now, the cloud

7

Input

New request:
Service list:

Algorithm

Output/Input

4

5

1 2 3

1 2 3 4

PSAP
Path:

x o2 o3 d1 d3 d2

Algorithm

Output

1 2 3 4 5

PSAP
x/x’ o2 o3 d1 d3 d2 o4 d4

x’ o2 o3 o5 d1 d3 d5 d2 o4 d4

Fig. 5. An example of PSAP.

receives a new request 4, while only the case C satisfies QoS
constraints, therefore, the new path becomes {x → o2 →
o3 → d1 → d3 → d2 → o4 → d4 } and the new service
list becomes {1, 2, 3, 4}.
In the second stage, the position of this PV becomes x0 ,
and request 1 still has not been dropped off, and requests 2,
3, and 4 have not been picked up, and now the cloud receives
a new request 5. PSAP finds that only case A satisfies QoS
constraints, and the path {x0 → o2 → o3 → o5 → d1 → d3 →
d5 → d2 → o4 → d4 } achieves the minimum insertion cost,
which becomes the new path and {1, 2, 3, 4, 5} becomes the
new service list.
V. P ERFORMANCE A NALYSIS
In this section, we first compare our solution with the
exhaustive search, and then present properties about the gap
between PSA and optimal PSA (PSAopt ) on the performance,
and finally we analyze the reduction ratio of computational
complexity.
A. PSAP vs. Exhaustive Search
The exhaustive search (ES) method has to try each insertion
position in the path of each PV, i.e., ignoring the process of
checking requests which insertion case they belong to and
directly calculating the insertion cost through (3)∼(6). The
other process is the same as that of PSAP. We see that
ES can be revised from PSAP: lines (9)∼(14) are replaced
by “Calculate {φr,p,i,j }p,i,j through (3)∼(6)” by trying each
insertion position over all PVs, such that a large amount of
computation is needed in ES. We see that PSAP and ES
have the same service quality performance while different
computational complexity. PSAP can greatly improve the computational efficiency by restricting the search areas compared
with ES since PSAP only tries a part of requests and others
are excluded.
Here, we present more details in PSAP to show its advantages. As shown in Fig. 2, some requests which violate
QoS are excluded, since the detour of at least a request is
larger than ∆ if they are not inserted in PSA. The scenario in
Fig. 3 is similar. The travel distance of the PV from schedule
time to pick-up time is limited, and the detour is limited.
Therefore, the QoS of requests is preserved. However, all the
above scenarios which violating QoS will be calculated in ES,
leading to a large amount of computation.
B. Gap between PSA and PSAopt
Definition V.1. If the furthest request r has been picked up, the
optimal PSA (PSAopt ) of PV p is the ellipse centering at (o, d),

otherwise, is the union of two ellipses centering at (ps , o) and
(o, d) respectively, just as discussed in Section IV-A.
In practice, we use PSA instead of PSAopt since the enlarged
area is limited. We take two examples to discuss PSAopt . In
Fig. 2, PSAopt is the ellipse and the PSA is the corresponding
rectangle. In Fig. 3, PSAopt is the union of two ellipses and
the PSA is the union of two corresponding rectangles. We see
that the PSA is always a litter larger than PSAopt .
Here, we discuss the gap between PSA and PSAopt to show
how much computational complexity is enlarged using PSA
than the latter one. Let Â denotes PSA of p with A = |Â|,
and Âopt denotes PSAopt of p with Aopt = |Âopt |, and let η
denote the ratio of PSA and PSAopt , which is formulated as (7).
Obviously, η > 1. In practice, we hope the gap between PSA
and PSAopt is smaller since this means more computational
complexity is saved, i.e., the smaller η is, the more efficient
the PSAP will be.
A
(7)
η = opt .
A
Theorem V.1. With respect to any PV p, if the furthest request
r has been picked up, the ratio of PSA and PSAopt η = AAopt =
4
π.
Theorem V.1 can be obtained according to the area of the
ellipse and corresponding rectangle. Next, let’s discuss the gap
between PSA and PSAopt of any PV p. Let r denote the furthest
request on path of p.
From Fig. 3, we know that, if the furthest request has not
been picked up, the PSA (or PSAopt ) of the PV is obtained by
union of two PSA (or PSAopt ) determined by the request. Now
let α̂opt denote PSAopt determined by (ps , o) with αopt = |α̂opt |,
and β opt denote PSAopt determined by (o, d) with β opt = |β̂ opt |,
opt
opt
and Â
denote PSAopt T
of PV p with Aopt = |Aˆopt |. Let Â
=
S opt
T opt
opt
opt
α̂
β̂ . Let µ̂ = α̂ β̂ with µ = |µ̂| and ν̂ = α̂
β̂
with ν = |ν̂|. Clearly, µ̂ ⊇ ν̂, and µ ≥ ν.
Theorem V.2. With respect to any PV p, no matter if the
A
furthest
request r has been picked up or not,
h
i η = Aopt ∈

(4−π)µ
4
max 1, π4 + π(α4ν−πµ
opt +β opt ) , π + π(αopt +β opt −ν) .
Proof. From (1), (2), and Theorem V.1, we know that η is
involved by the state of the furthest request. Now, we discuss
the first case, i.e., the furthest request r has not been picked
up. From Theorem V.1, we know that,
β
4
α
= opt = .
opt
α
β
π
Considering of the definition of µ and ν, we get the following:
A = α + β − µ,
Aopt = αopt + β opt − ν,
α+β−µ
η = opt
.
α + β opt − ν
And then η is reformulated as
4
4ν − πµ
.
η= +
π π(αopt + β opt − ν)
Considering that η > 1, we get
4
4ν − πµ 
4
(4 − π)µ
≤η ≤ +
max 1, +
.
opt
opt
opt
π π(α + β )
π π(α + β opt − ν)

8

Then, we discuss the second case, i.e., the furthest request
r has been picked up. Obviously, µ = ν = 0, and η = π4 . So
the above inequality about the scope of η is still workable.
Finally, Theorem V.2 is proved.

C. Reduction Ratio of Computational Complexity
Reduction ratio of computational complexity (RRCC) includes three cases: A, B, and C. Let MA , MB , and MC denote
the number of insertion times of origin-destination pairs in
PSAP in cases A, B, and C. Let NA , NB , and NC denote the
number of insertion times of origin-destination pairs in ES in
three cases. Let ψA , ψB , and ψC denote RRCC in three cases.
For example, in case A, we record MA and NA , and then ψA
is obtained by
ψA = (NA − MA ) / NA .
ψB and ψC can be obtained in a similar way. In this subsection,
we discuss the estimation for RRCC since it directly affects
the computational complexity of PSAP: the larger RRCC is,
the more efficient PSAP will be.
Computing PSA involves several square operations, and
computing if the origin or destination is in PSA only involves linear operations. Both of them have less computational
complexity than the shortest path algorithm such as Dijkstra
algorithm and calculating the minimum insertion cost [9].
Therefore, the cost of computing PSA and computing if the
origin or destination is in PSA can be ignored when we analyze
RRCC.
Let S denote the area of the whole road network. If the
PSA is smaller, more requests will be excluded, and the PSAP
solution will be more efficient. For example, now we insert an
origin-destination pair (o0 , d0 ) of request r0 based on PSA Â.
In case A, both o0 and d0 are in the PSA Â.
We assume that the event o0 ∈ Â is independent with
another event d0 ∈ Â. In case A, the probability of o0 , d0 ∈ Â
2
A
0
is A
S 2 . In case B, the probability of o ∈ Â is S . In case C,
make sure that all the points on the path should fall in the
PSA determined by the current position of p and o.
Generally, the execution time of case A is more than case B,
and the execution time of case C is the minimum among three
cases, which can be inferred from Section IV-C. The execution
time of case C is not meaningful since it needs at most
one calculation for one request. We focus on mathematical
expectation of RRCC in cases A and B, which are obtained
by
A2
,
S2
A
E(ψB ) = 1 − ,
S

E(ψA ) = 1 −

(8)
(9)

where E means the mathematical expectation.
On the current path of p Qp = {θ0 , θ1 , . . . , θK }, we insert
o and d. Let i be the insertion position of o, and we get the

following:
NA =

K−1
X

(K − i) =

i=1

1
K(K − 1),
2

(10)

NB = K − 1,

(11)

NC = 1.

(12)

The total reduced number of insertion times of origindestination pairs using PSAP compared with ES is denoted
by I, and we obtain its mathematical expectation by
E(I) = NA E(ψA ) + NB E(ψB ) + NC E(ψC )
≈ NA E(ψA ) + NB E(ψB )




A
1
A2
= K(K − 1) 1 − 2 + (K − 1) 1 −
, (13)
2
S
S
where case C can be ignored since NC is much smaller than
NA and NB .
2
A
Obviously, A
S 2 ≤ S ≤ 1 and we get E(ψA ) ≥ E(ψB ). From
(10)∼(12), we know NA ≥ NB ≥ NC . From (13), we get
that, cases A and B almost determine RRCC since generally
NA E(ψA ) ≥ NB E(ψB ) ≥ NC E(ψC ).
VI. P ERFORMANCE E VALUATION
In this section, we first describe the simulation settings, and
then present the results to evaluate the performance of our
proposed solution.
A. Simulation Settings
Simulation settings include: PV setting, privately owned
electric vehicle (POEV) setting, road map data, taxi data, and
parameter setting.
PV Setting: We use electric vehicles, Tesla Model-S [26]
to study the transportation patterns of PVs, although they are
not self-driving vehicles now. The number of seats of each
PV is 5. Assuming that all PVs travel along the shortest path
between any two positions (origins or destinations of requests)
with the identical speed 30 km/h. The initial positions of PVs
are randomly distributed in the road network which follows
a uniform distribution. PVs always travel to serve passengers
as long as new requests are assigned, and PVs stay at their
positions if no requests are assigned to them.
POEV Setting: We also use the Tesla Model-S [26] to
explore the traffic characteristics of POEVs. The settings of
POEVs are the same as PVs except that POEVs only provide
the origin-to-destination ride service along the shortest path
instead of ride-sharing services. Clearly, the number of POEVs
is the half the number of requests if each POEV is used twice
a day, which is much larger than that of PVs.
Road Map Data: We use the Manhattan road network
with 60 km2 in New York City to perform PSAP and ES,
which is depicted by Fig. 6 where black lines denote road
segments, and green points denote nodes. The road map is
extracted through the openstreetmap [27] with six types of
ways: primary, secondary, tertiary, motorway, motorway link,
and residential. Finally, 3,900 ways and 29,792 nodes are
filtered.

9

Fig. 6. Manhattan in New York City.

The black circle and black square in Fig. 6 are the origin
and the destination of a request respectively. We assume that
this request is the furthest and is just picked up by a PV at
the origin, and the corresponding PSA and PSAopt are denoted
by the red rectangle and the red ellipse respectively. We can
see that, in case A, the search area denoted by the PSA is
much smaller than the whole road network, which implies
that the search space is largely reduced and the computational
efficiency is improved.
Taxi Data: We use the taxi data set (yellow records) of the
New York City on March 1, 2016 [28]. Each record contains
several useful fields for our study, including pick-up time,
drop-off time, trip distance, latitudes/longitudes of origins,
latitudes/longitudes of destinations, fares, tax, tip, and total
payment. Then the trip records with origin-destination pairs
falling in Mahattan are selected.
Let’s discuss three traffic characteristics in the Mahattan taxi
data set. The first one is the distribution of these trip requests
(only in Manhattan) in each hour on March 1 (Tuesday), 2016,
which is shown by Fig. 7. The busiest time occurs at 8:00 and
18:00 respectively in morning and evening rush hours. The
second one is the PDF of trip fare, which is presented by
Fig. 8. We know that most of the trip fare is between 5∼15
US dollars. The third one is the PDF of trip distance, which is
depicted by Fig. 9. We can see that most of the trip distance
is less than 6 km.
We assume the pick-up time of each request is equal to
the earliest start time. All PVs travel as the ride-sharing path
computed by the cloud, and stop at the destinations of requests
for the next schedule task. To make the performance more
stable, we select the requests with Euclidean distance no less
than 3 km, and then the total number of trip requests of the
day in Mahattan is 75,014, and the number is reduced to 3,112
in the period 11:00∼11:59.
Parameter Setting: Passengers prefer low detour ratio,
which reflects the QoS of passengers and will be widely
accepted if the value is not larger than the maximum value
∆ = 0.2. The waiting time threshold W (minute) is 4. If W
is too large, some requests which fall in dead zones may have
to wait for long time, however, if it is too small, the effect of
PSAP is not clear since it directly calculate the insertion cost
ignoring the check about PSA. The buffer distance threshold
B (km) is set to 6. If B is set too large, the PSA of PVs
may be too large just as the whole city and PSAP may spend
more time on computing the paths of PVs, while if it is too
small, most requests will fall in the limited search area and
they will be assigned only after the waiting time is larger than
the threshold W .
We implement PSAP and ES through a computer with an

Intel Core-i7 (3.4 GHz and 32 GB of RAM) using C++ under
Windows OS. In the 24-hour simulations, the time begins at
3:00 for two reasons. 1) This time is one of the most important
shift handover time in taxi companies in many cities such as
Shenzhen [29]. 2) The number of trip requests of this time
is almost the minimum of one day in multiple cities such as
Shanghai [9], Tokyo [30], and New York City [28].
B. Results
Here, we introduce two metrics: sharing rate and saved
travel distance. 1) The sharing rate should imply the traffic
sharing scenario in PV systems, and is denoted by the following
] of requests being served
.
(14)
sharing rate =
] of moving vehicles
We see that the sharing rate of POEVs does not change and is
always 1 since there is no sharing among different requests. 2)
The saved travel distance is denoted by the sum of the shortest
path distance of each origin-destination pair of requests minus
the total travel distance of PVs. We see that the saved travel
distance implies the amount of saved energy of transportation
systems.
We know that PSAP and ES have the same service quality performance, therefore, we compare the computational
complexity of PSAP and ES, and then present the traffic
performance of PVs using PSAP and POEVs to explore their
transportation patterns.
The simulation results are presented in six items: computation time comparison, RRCC, total travel distance comparison,
utilization rate, sharing rate, and saved travel distance. And
finally, the energy efficiency and particular features of PV
systems are discussed.
The first metric is the computation time, which is shown by
Fig. 10 where the number of requests varies from 100 to 900
during 11:00∼11:59 and the number of PVs is 70. We get that,
when the number of requests increases, the computing time
of PSAP and ES both increases, however, the computing time
using PSAP is reduced by 22% compared with ES. ES tries all
the possible insertion positions while PSAP only tries a part of
them since the requests violating QoS constraints are excluded.
From (8) and (9), we know that, if the urban area increases,
more computation will be reduced using PSAP, i.e., PSAP will
have better performance in traffic big data scenarios.
The second metric is RRCC, which is displayed by Fig. 11
where the number of PVs is 70, and the number of requests is
set to 700, 800, and 900 respectively during 11:00∼11:59. We
see that, the RRCC in case A is much higher than that in case
B, and the RRCC in case C is between the other two cases.
The results can be inferred from (8) and (9). For example,
when the number of requests is 900, the RRCC in three cases
A, B and C is 40.2%, 15.1%, and 31.8% respectively. The
result can be explained as follows. In case A, both the origin
and destination of a new request should be in PSA of the PV,
while in case B, only the origin should be in PSA. Therefore,
the number of requests which satisfy case A is much smaller
than that of case B. In case C, all the points of the current path
of one PV should fall in PSA, which is related to the number

10

Fig. 7. Distribution of requests in one day.

Fig. 8. PDF of trip fare.

Fig. 9. PDF of trip distance.

Fig. 10. Computation time comparison.

Fig. 11. RRCC in three cases.

Fig. 12. Total travel distance comparison.

of requests which are being served and waiting to be served,
therefore, it is hard to predict the result in case C under such
particular constraints.
Next, we put 500∼800 PVs to the system to serve 75,014
requests of the day. The average waiting-travel time of requests
is (18.7, 14.1), (3.2, 13.7), (2.5, 13.1) and (2.1, 12.7) minutes
using 500, 600, 700, and 800 PVs respectively. This means
that if more PVs are put to the system, the waiting and travel
time will be less, since the service quality level will improve
with less passengers sharing one vehicle.
The third metric is the total travel distance, which is plotted
by Fig. 12. We see that, when we put more than 500 PVs
to serve passengers, the total travel distance of PVs increases
slowly since passengers share common paths during their trips.
The travel distance of PVs is reduced by 24%∼39% compared
with that by POEVs when the number of PVs varies from 500
to 800.
The fourth metric is the utilization rate, which is depicted
by Fig. 13. We can see that, when we put 500 PVs to the
system, during 8:00∼24:00, almost all PVs are busy on serving
passengers since the number of PVs is too small to serve such
a large number of requests. While if we put more PVs, e.g.,
800, the utilization rate of PVs almost increases to one during
peak time such as 8:00, yet decreases obviously during nonpeak time such as 12:00.
The fifth metric is the sharing rate, which is presented by
Fig. 14. We see that, the less PVs do we put, the larger the
sharing rate will be. At non-peak time such as 4:00, the sharing
rate is less than one, since very few passengers share PVs,

however, PVs have to travel some distance to pick up them.
However, at peak time such as 19:00, the sharing rate improves
obviously since more passengers share PVs.
The sixth metric is the saved travel distance, which is shown
by Fig. 15. We can see that, at non-peak time, the saved travel
distance is very small, even is negative at 4:00, since very few
passengers share PVs at this time. However, at peak time, the
saved travel distance increases largely especially at 8:00 and
18:00 since the more passengers join ride-sharing, the more
the saved travel distance will be.
Now, we discuss the energy efficiency of PV systems. We
assume the travel distance of PVs and POEVs is positively
correlated with the energy consumption. From Fig. 12, we
can infer that the average energy cost will be dropped by
24%∼39%. In PV systems, although passengers may sacrifice
some comfort during their trips, the discomfort emerged from
ride-sharing is limited since PASP tries to balance the waiting
time of passengers and restrict the detour of each passenger
to a tolerated scope. Therefore, the QoS of passengers is
guaranteed, and the low-cost ride-sharing will attract more
passengers to choose PV systems.
Here, we discuss the particular features of PV systems in
peak and non-peak time. According to Fig. 12 and Fig. 15
which show the total travel distance and the saved travel
distance, respectively, we can infer that, if too many PVs join
the system, the profits will be reduced for the sake of parking
fees, however, too few PVs can save more travel distance with
the cost of degrading the service quality level of passengers.
At traffic peak time, the saved travel distance is much more

11

Fig. 13. Utilization rate.

Fig. 14. Sharing rate.

than that in non-peak time, since more passengers share PVs.
Therefore, the number of PVs put to the system is an important
factor which balances the PV system profits and passenger
QoS. We conclude that PV systems are more practical and
profitable in traffic peak time of crowd urban areas, however,
in traffic non-peak time or suburban areas with few passengers,
the performance of PV systems is as good as that in the former
scenario.
VII. D ISCUSSION AND C ONCLUSION
To deal with the online/dynamic ride-sharing path planning
problem for PV systems, we propose a solution based on
a limited potential search area for each vehicle to filter out
the requests that violate passenger QoS constraints such as
detour, therefore, the global search is reduced to local search
and the computational complexity is reduced. It also considers
the comfort of passengers (e.g., waiting time and detour) and
the total travel distance of PVs. Therefore, passengers can
enjoy their peer-to-peer ride-sharing services with sacrificing
a little ride comfort. We also analyze the reduction ratio of
computational complexity using the proposed solution, which
is related to the current paths and service lists of vehicles,
and the locations of origin-destination pairs of unscheduled
requests. Through our simulations based on Manhattan taxi
data sets, the computation time of the proposed approach is
greatly reduced than the exhaustive search method, and the
average energy cost for each passenger by PVs is largely
reduced compared with that by private owned electric vehicles.
Here, we consider less about the passenger preferences, and
in the future we will focus on the ride-sharing path planning
methods with more preferences, e.g., the maximum number
of shared persons, the pick-up/drop-off point selection, and
the point of interest selection. In addition, we will design
the ride-sharing path planning solutions aiming at solving the
common last mile problem from homes or work places to
subway stations or bus stops.
R EFERENCES
[1] T. Litman, “Transportation and public health,” Annual review of public
health, vol. 34, pp. 217–233, 2013.
[2] A. E. Pisarski, “The transportation challenge-moving the us economy
(2008),”

Fig. 15. Saved travel distance.

[3] “Commuting in america 2013: The national report on commuting
patterns and trends (2013).”
http://www.prtctransit.org/docs/Commuting in America 2013.pdf.
[4] M. Zhu, J. Hu, L. Kong, W. Shu, and M.-Y. Wu, “An algorithm of
lane change using two-lane nasch model in traffic networks,” in IEEE
International Conference on Connected Vehicles and Expo (ICCVE),
pp. 241–246, 2013.
[5] P. Hystad, P. A. Demers, K. C. Johnson, R. M. Carpiano, and M. Brauer,
“Long-term residential exposure to air pollution and lung cancer risk,”
LWW Epidemiology, vol. 24, no. 5, pp. 762–772, 2013.
[6] M. Zhu and M.-Y. Wu, “Traffic efficiency improvement and passengers
comfort in ridesharing systems in vanets,” in IEEE International Conference on Connected Vehicles and Expo (ICCVE), pp. 116–121, 2015.
[7] “Beijing air pollution: Real-time air quality index (aqi) (2017).”
http://aqicn.org/city/beijing/.
[8] J. Hamari, M. Sjöklint, and A. Ukkonen, “The sharing economy: Why
people participate in collaborative consumption,” Wiley Online Library
Journal of the Association for Information Science and Technology,
vol. 67, no. 9, pp. 2047–2059, 2016.
[9] M. Zhu, X.-Y. Liu, F. Tang, M. Qiu, and M.-Y. Wu, “Public vehicles
for future urban transportation,” IEEE Transactions on Intelligent Transportation Systems (TITS), vol. 17, no. 12, pp. 3344–3353, 2016.
[10] M. Zhu, X.-Y. Liu, and X. Wang, “Joint transportation and charging
scheduling in public vehicle systems - a game theoretic approach,”
(under review) IEEE Transactions on Intelligent Transportation Systems
(TITS), 2017.
[11] M. Zhu, X.-Y. Liu, M. Qiu, and M.-Y. Wu, “Traffic big data based path
planning strategy in public vehicle systems,” in IEEE/ACM International
Symposium of Quality of Service (IWQoS), 2016.
[12] M. Zhu, L. Kong, X.-Y. Liu, and M.-Y. Wu, “A public vehicle system
with multiple origin-destination pairs on traffic networks,” in IEEE
Global Communications Conference (GLOBECOM), pp. 1–6, 2015.
[13] M. Zhu, X.-Y. Liu, L. Kong, and M.-Y. Wu, “The charging-scheduling
problem for electric vehicle networks,” in IEEE Wireless Communications and Networking Conference (WCNC), pp. 3178–3183, 2014.
[14] “Homepage of uber (2017).”
https://www.uber.com/.
[15] “Homepage of didi (2017).”
http://www.xiaojukeji.com.
[16] M. Zhu, X.-Y. Liu, M. Qiu, and M.-Y. Wu, “Transfer problem in a cloudbased public vehicle system with sustainable discomfort,” Springer
Mobile Networks and Applications (MONET), vol. 21, no. 5, pp. 890–
900, 2016.
[17] S. Shang, L. Chen, Z. Wei, C. S. Jensen, J.-R. Wen, and P. Kalnis,
“Collective travel planning in spatial networks,” IEEE Transactions on
Knowledge and Data Engineering (TKDE), vol. 28, no. 5, pp. 1132–
1146, 2016.
[18] J. Jung, R. Jayakrishnan, and J. Y. Park, “Dynamic shared-taxi dispatch algorithm with hybrid-simulated annealing,” Wiley Online Library
Computer-Aided Civil and Infrastructure Engineering, vol. 31, no. 4,
pp. 275–291, 2016.
[19] S. Ma, Y. Zheng, and O. Wolfson, “Real-time city-scale taxi ridesharing,” IEEE Transactions on Knowledge and Data Engineering (TKDE),
vol. 27, no. 7, pp. 1782–1795, 2015.
[20] R. Massobrio, G. Fagúndez, and S. Nesmachnow, “Multiobjective evolutionary algorithms for the taxi sharing problem,” Inderscience Publishers

12

[21]

[22]
[23]
[24]
[25]
[26]
[27]
[28]
[29]

[30]

(IEL) International Journal of Metaheuristics, vol. 5, no. 1, pp. 67–90,
2016.
J. Naoum-Sawaya, R. Cogill, B. Ghaddar, S. Sajja, R. Shorten, N. Taheri,
P. Tommasi, R. Verago, and F. Wirth, “Stochastic optimization approach
for the car placement problem in ridesharing systems,” Elsevier Transportation Research Part B: Methodological, vol. 80, pp. 173–184, 2015.
P. Goel, L. Kulik, and K. Ramamohanarao, “Optimal pick up point
selection for effective ride sharing,” IEEE Transactions on Big Data
(TBDATA), vol. 3, no. 2, pp. 154–168, 2017.
M. Ota, H. Vo, C. Silva, and J. Freire, “Stars: Simulating taxi ride sharing
at scale,” IEEE Transactions on Big Data (TBDATA), 2016.
N. G. Polson and V. O. Sokolov, “Deep learning for short-term traffic
flow prediction,” Elsevier Transportation Research Part C: Emerging
Technologies, vol. 79, pp. 1–17, 2017.
M. A. Masmoudi, K. Braekers, M. Masmoudi, and A. Dammak, “A
hybrid genetic algorithm for the heterogeneous dial-a-ride problem,”
Elsevier Computers & Operations Research, vol. 81, pp. 1–13, 2017.
“Homepage of tesla model-s (2017).”
http://my.teslamotors.com/models/design.
“Homepage of openstreetmap (2017).”
http://www.openstreetmap.org/.
“New york city taxi and limousine commission (tlc) trip data (2017).”
http://www.nyc.gov/html/tlc/html/about/trip record data.shtml.
Z. Tian, T. Jung, Y. Wang, F. Zhang, L. Tu, C. Xu, C. Tian, and X.-Y. Li,
“Real-time charging station recommendation system for electric-vehicle
taxis,” IEEE Transactions on Intelligent Transportation Systems (TITS),
vol. 17, no. 11, pp. 3098–3109, 2016.
B. Atasoy, T. Ikeda, X. Song, and M. E. Ben-Akiva, “The concept
and impact analysis of a flexible mobility on demand system,” Elsevier Transportation Research Part C: Emerging Technologies, vol. 56,
pp. 373–392, 2015.

Ming Zhu is now a postdoctoral researcher and
assistant researcher in Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences,
Shenzhen, China. He received the PhD degree in
Computer Science and Engineering in Shanghai Jiao
Tong University, Shanghai, China. A part of this
work is finished in Shanghai Jiao Tong University.
His research interests are in the area of big data,
artificial intelligence, internet of things, and wireless
communications.

Xiao-Yang Liu received his B.Eng. degree in computer science from Huazhong University of Science
and Technology, China, in 2010. He is currently a
joint PhD in the Department of Electrical Engineering, Columbia University, and in the Department of
Computer Science and Engineer, Shanghai Jiao Tong
University.
His research interests include tensor theory, deep
learning, nonconvex optimization, big data analysis
and homomorphic encryption, cyber-security and
wireless communication.

Xiaodong Wang (S’98-M’98-SM’04-F’08) received
the Ph.D. degree in electrical engineering from
Princeton University. He is currently a Professor
of electrical engineering with Columbia University,
New York NY, USA. His research interests fall in
the general areas of computing, signal processing,
and communications. He has authored extensively
in these areas. He has authored the book entitled
Wireless Communication Systems: Advanced Techniques for Signal Reception, (Prentice Hall, 2003).
His current research interests include wireless communications, statistical signal processing, and genomic signal processing.
He has served as an Associate Editor of the IEEE TRANSACTIONS ON
COMMUNICATIONS, the IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, the IEEE TRANSACTIONS ON SIGNAL PROCESSING,
and the IEEE TRANSACTIONS ON INFORMATION THEORY. He is an ISI
Highly Cited Author. He received the 1999 NSF CAREER Award, the 2001
IEEE Communications Society and Information Theory Society Joint Paper
Award, and the 2011 IEEE Communication Society Award for Outstanding
Paper on New Communication Topics.

