1

Taxi Dispatch with Real-Time Sensing Data in Metropolitan Areas:
A Receding Horizon Control Approach

arXiv:1603.04418v1 [] 14 Mar 2016

Fei Miao, Student Member, IEEE, Shuo Han, Member, IEEE, Shan Lin, John A. Stankovic, Fellow, IEEE and
ACM, Desheng Zhang, Sirajum Munir, Hua Huang, Tian He, and George J. Pappas Fellow, IEEE

Abstract—Traditional taxi systems in metropolitan areas often
suffer from inefficiencies due to uncoordinated actions as system
capacity and customer demand change. With the pervasive
deployment of networked sensors in modern vehicles, large
amounts of information regarding customer demand and system
status can be collected in real time. This information provides
opportunities to perform various types of control and coordination for large-scale intelligent transportation systems. In this
paper, we present a receding horizon control (RHC) framework
to dispatch taxis, which incorporates highly spatiotemporally
correlated demand/supply models and real-time GPS location
and occupancy information. The objectives include matching
spatiotemporal ratio between demand and supply for service
quality with minimum current and anticipated future taxi idle
driving distance. Extensive trace-driven analysis with a data set
containing taxi operational records in San Francisco shows that
our solution reduces the average total idle distance by 52%, and
reduces the supply demand ratio error across the city during one
experimental time slot by 45%. Moreover, our RHC framework
is compatible with a wide variety of predictive models and
optimization problem formulations. This compatibility property
allows us to solve robust optimization problems with corresponding demand uncertainty models that provide disruptive event
information.
Note to Practitioners—With the development of mobile sensor
and data processing technology, the competition between traditional “hailed on street” taxi service and “on demand” taxi
service has emerged in the US and elsewhere. In addition, large
amounts of data sets for taxi operational records provide potential
demand information that is valuable for better taxi dispatch
systems. Existing taxi dispatch approaches are usually greedy
algorithms focus on reducing customer waiting time instead of
total idle driving distance of taxis. Our research is motivated
by the increasing need for more efficient, real-time taxi dispatch
methods that utilize both historical records and real-time sensing
information to match the dynamic customer demand. This paper
suggests a new receding horizon control (RHC) framework
aiming to utilize the predicted demand information when making
taxi dispatch decisions, so that passengers at different areas of a
city are fairly served and the total idle distance of vacant taxis are
This work was supported by NSF grant numbers CNS-1239483, CNS1239108, CNS-1239226, and CPS-1239152 with project title: CPS: Synergy:
Collaborative Research: Multiple-Level Predictive Control of Mobile Cyber
Physical Systems with Correlated Context. The preliminary conference version
of this work can be found in [19].
F. Miao, S. Han and G. J. Pappas are with Department of Electrical and
Systems Engineering, University of Pennsylvania, Philadelphia PA, 19104,
USA 19014. Email: {miaofei, hanshuo, pappasg}@seas.upenn.edu.
S. Lin and H. Huang are with Department of Electrical and Computer Engineering, Stony Brook University, Long Island, NY 11794, USA.
Email:{shan.x.lin, hua. huang}@stonybrook.edu}.
J.A. Stankovic and S. Munir are with Department of Computer
Science, University of Virginia, Charlottesville, VA 22904, USA. Email:
stankovic@cs.virginia.edu, sm7hr@virginia.edu.
D. Zhang and T. He are with Department of Computer Science
and Engineering, University of Minnesota, Minneapolis, MN 55455, USA.
Email:{tianhe, zhang}@cs.umn.edu

reduced. We formulate a multi-objective optimization problem
based on the dispatch requirements and practical constraints.
The dispatch center updates GPS and occupancy status information of each taxi periodically and solves the computationally
tractable optimization problem at each iteration step of the RHC
framework. Experiments for a data set of taxi operational records
in San Francisco show that the RHC framework in our work can
redistribute taxi supply across the whole city while reducing total
idle driving distance of vacant taxis. In future research, we plan
to design control algorithms for various types of demand model
and experiment on data sets with a larger scale.
Index Terms—Intelligent Transportation System, Real-Time
Taxi Dispatch, Receding Horizon Control, Mobility Pattern

I. I NTRODUCTION
More and more transportation systems are equipped with
various sensors and wireless radios to enable novel mobile
cyber-physical systems, such as intelligent highways, traffic
light control, supply chain management, and autonomous
fleets. The embedded sensing and control technologies in these
systems significantly improve their safety and efficiency over
traditional systems. In this paper, we focus on modern taxi
networks, where real-time occupancy status and the Global
Positioning System (GPS) location of each taxi are sensed
and collected to the dispatch center. Previous research has
shown that such data contains rich information about passenger
and taxi mobility patterns [31], [24], [23]. Moreover, recent
studies have shown that the passenger demand information
can be extracted and used to reduce passengers’ waiting time,
taxi cruising time, or future supply rebalancing cost to serve
requests [16], [25], [32].
Efficient coordination of taxi networks at a large scale is
a challenging task. Traditional taxi networks in metropolitan
areas largely rely on taxi drivers’ experience to look for
passengers on streets to maximize individual profit. However,
such self-interested, uncoordinated behaviors of drivers usually result in spatiotemporal mismatch between taxi supply
and passenger demand. In large taxi companies that provide
dispatch services, greedy algorithms based on locality are
widely employed, such as finding the nearest vacant taxi to
pick up a passenger [18], or first-come, first-served. Though
these algorithms are easy to implement and manage, they
prioritize immediate customer satisfaction over global resource
utilization and service fairness, as the cost of rebalancing the
entire taxi supply network for future demand is not considered.
Our goal is to utilize real-time information to optimize taxi
network dispatch for anticipated future idle driving cost and
global geographical service fairness, while fulfilling current,
local passenger demand. To accomplish such a goal, we

2

incorporate both system models learned from historical data
and real-time taxi data into a taxi network control framework.
To the best of our knowledge, this is the first work to consider
this problem. The preliminary version of this work can be
found in [19], and more details about problem formulation,
algorithm design, and numerical evaluations are included in
this manuscript.
In this paper, we design a computationally efficient moving
time horizon framework for taxi dispatch with large-scale realtime information of the taxi network. Our dispatch solutions in
this framework consider future costs of balancing the supply
demand ratio under realistic constraints. We take a receding
horizon control (RHC) approach to dynamically control taxis
in large-scale networks. Future demand is predicted based
on either historical taxi data sets [5] or streaming data [31].
The real-time GPS and occupancy information of taxis is also
collected to update supply and demand information for future
estimation. This design iteratively regulates the mobility of
idle taxis for high performance, demonstrating the capacity of
large-scale smart transportation management.
The contributions of this work are as follows,
• To the best of our knowledge, we are the first to design
an RHC framework for large-scale taxi dispatching. We
consider both current and future demand, saving costs under constraints by involving expected future idle driving
distance for re-balancing supply.
• The framework incorporates large-scale data in real-time
control. Sensing data is used to build predictive passenger
demand, taxi mobility models, and serve as real-time
feedback for RHC.
• Extensive trace driven analysis based on a San Francisco
taxi data set shows that our approach reduces average
total taxi network idle distance by 52% as in Figure 5, and
the error between local and global supply demand ratio
by 45% as in Figure 7, compared to the actual historical
taxi system performance.
• Spatiotemporal context information such as disruptive
passenger demand is formulated as uncertainty sets of
parameters into a robust dispatch problem. This allows
the RHC framework to provide more robust control
solutions under uncertain contexts as shown in Figure 8.
The error between local and global supply demand ratio
is reduced by 25% compared with the error of solutions
without considering demand uncertainties.

perspective in work [30], but the real-time location information
is not utilized in the algorithm. Seow et.al focus on minimizing
total customer waiting time by concurrently dispatching multiple taxis and allowing taxis to exchange their booking assignments [27]. A shortest time path taxi dispatch system based
on real-time traffic conditions is proposed by Lee et.al [15].
In [26], [13], [25], authors aim to maximize drivers’ profits
by providing routing recommendations. These works give
valuable results, but they only consider the current passenger
requests and available taxis. Our design uses receding horizon
control to consider both current and predicted future requests.
Various mobility and vehicular network modeling techniques have been proposed for transportation systems [6],
[4]. Researchers have developed methods to predict travel
time [8], [11] and traveling speed [2], and to characterize
taxi performance features [16]. A network model is used to
describe the demand and supply equilibrium in a regulated
market is investigated [29]. These works provide insights
to transportation system properties and suggest potential enhancement on transportation system performance. Our design
takes a step further to develop dispatch methods based on
available predictive data analysis.
There is a large number of works on mobility coordination
and control. Different from taxi services, these works usually
focus on region partition and coverage control so that coordinated agents can perform tasks in their specified regions [7],
[1], [12]. Aircraft dispatch system and air traffic management
in the presence of uncertainties have been addressed [3],
[28], while the task models and design objectives are different from taxi dispatching problem. Also, receding horizon
control (RHC) has been widely applied for process control,
task scheduling, and multi-agent transportation networks [20],
[14], [17]. These works provide solid results for related
mobility scheduling and control problems. However, none of
these works incorporates both the real-time sensing data and
historical mobility patterns into a receding horizon control
design, leveraging the taxi supply based on the spatiotemporal
dynamics of passenger demand.
The rest of the paper is organized as follows. The background of taxi monitoring system and control problems are
introduced in Section II. The taxi dispatch problem is formally
formulated in Section III, followed by the RHC framework
design in Section IV. A case study with a real taxi data set
from San Francisco to evaluation the RHC framework is shown
in Section V. Concluding remarks are made in Section VI.

A. State-of-the-Art
There are three categories of research topics related to our
work: taxi dispatch systems, transportation system modeling,
and multi-agent coordination and control.
A number of recent works study approaches of taxi dispatching services or allocating transportation resources in
modern cities. Zhang and Pavone [32] designed an optimal
rebalancing method for autonomous vehicles, which considers
both global service fairness and future costs, but they didn’t
take idle driving distance and real-time GPS information into
consideration. Truck schedule methods to reduce costs of
idle cruising and missing tasks are designed in the temporal

II. TAXI D ISPATCH P ROBLEM : M OTIVATION AND S YSTEM
Taxi networks provide a primary transportation service
in modern cities. Most street taxis respond to passengers’
requests on their paths when passengers hail taxis on streets.
This service model has successfully served up to 25% public
passengers in metropolitan areas, such as San Francisco and
New York [10], [21]. However, passenger’s waiting time
varies at different regions of one city and taxi service is not
satisfying. In the recent years, ”on demand” transportation
service providers like Uber and Lyft aim to connect a passenger directly with a driver to minimize passenger’s waiting

3

time. This service model is still uncoordinated, since drivers
may have to drive idly without receiving any requests, and
randomly traverse to some streets in hoping to receive a
request nearby based on experience.
Our goal in this work is a centralized dispatch framework to
coordinate service behavior of large-scale taxi Cyber-Physical
system. The development of sensing, data storage and processing technologies provide both opportunities and challenges to
improve existing taxi service in metropolitan areas. Figure 1
shows a typical monitoring infrastructure, which consists
of a dispatch center and a large number of geographically
distributed sensing and communication components in each
taxi. The sensing components include a GPS unit and a trip
recorder, which provides real-time geographical coordinates
and occupancy status of every taxi to the dispatch center via
cellular radio. The dispatch center collects and stores data.
Then, the monitoring center runs the dispatch algorithm to
calculate a dispatch solution and sends decisions to taxi drivers
via cellular radio. Drivers are notified over the speaker or on
a special display.
Given both historical data and real-time taxi monitoring information described above, we are capable to learn spatiotemporal characteristics of passenger demand and taxi mobility
patterns. This paper focuses on the dispatch approach with
the model learned based on either historical data or streaming
data. One design requirement is balancing spatiotemporal taxi
supply across the whole city from the perspective of system
performance. It is worth noting that heading to the allocated
position is part of idle driving distance for a vacant taxi. Hence,
there exists trade-off between the objective of matching supply
and demand and reducing total idle driving distance. We
aim at a scalable control framework that directs vacant taxis
towards demand, while balancing between minimum current
and anticipated future idle driving distances.
III. TAXI D ISPATCH P ROBLEM F ORMULATION
Informally, the goal of our taxi dispatch system is to schedule vacant taxis towards predicted passengers both spatially
and temporally with minimum total idle mileage. We use
supply demand ratio of different regions within a time period
as a measure of service quality, since sending more taxis
for more requests is a natural system-level requirement to
make customers at different locations equally served. Similar
Dispatch Center

Passenger
Distribution

Taxi
Mobility
Real-Time
Control

Cellular
Ratio
GPS

Pickup & Delivery

Figure 1.

Occupancy
Sensing

A prototype of the taxi dispatch system

service metric of service node utilization rate has been applied
in resource allocation problems, and autonomous driving car
mobility control approach [32].
The dispatch center receives real-time sensing streaming
data including each taxi’s GPS location and occupancy status
with a time stamp periodically. The real-time data stream is
then processed at the dispatch center to predict the spatiotemporal patterns of passenger demand. Based on the prediction,
the dispatch center calculates a dispatch solution in real-time,
and sends decisions to vacant taxis with dispatched regions to
go in order to match predicted passenger demands.
Besides balancing supply and demand, another consideration in taxi dispatch is minimizing the total idle cruising
distance of all taxis. A dispatch algorithm that introduces large
idle distance in the future after serving current demands can
decrease total profits of the taxi network in the long run. Since
it is difficult to perfectly predict the future of a large-scale
taxi service system in practice, we use a heuristic estimation
of idle driving distance to describe anticipated future cost associated with meeting customer requests. Considering control
objectives and computational efficiency, we choose a receding
horizon control approach. We assume that the optimization
time horizon is T , indexed by k = 1, . . . , T , given demand
prediction during time [1, T ].
Notation
In this paper, we denote 1N as a length N column vector
of all 1s, and 1TN is the transpose of the vector. Superscripts
of variables as in X k , X k+1 denote discrete time. We denote
the j-th column of matrix X k as X·jk .
A. Supply and demand in taxi dispatch
We assume that the entire area of a city is divided into n
regions such as administrative sub-districts. We also assume
that within a time slot k, the total number of passenger
requests at the j-th region is denoted by rjk . We also use
rk , [r1k , . . . , rnk ] ∈ R1×n to denote the vector of all
requests. These are the demands we want to meet during time
k = 1, . . . , T with minimal idle driving cost. Then the total
number of predicted requests in the entire city is denoted by
n
P
Rk =
rjk .
j=1

We assume that there are total N vacant taxis in the entire
city that can be dispatched according to the real-time occupancy status of all taxis. The initial supply information consists
of real-time GPS position of all available taxis, denoted by
P 0 ∈ RN ×2 , whose i-th row Pi0 ∈ R1×2 corresponds to the
position of the i-th vacant taxi. While the dispatch algorithm
does not make decisions for occupied taxis, information of
occupied taxis affects the predicted total demand to be served
by vacant taxis, and the interaction between the information of
occupied taxis and our dispatch framework will be discussed
in section IV.
The basic idea of the dispatch problem is illustrated in
Figure 2. Specifically, each region has a predicted number of
requests that need to be served by vacant taxis, as well as locations of all vacant taxis with IDs given by real-time sensing

4

Parameters
N
n
rk ∈ R1×n
C k ∈ [0, 1]n×n
P 0 ∈ RN ×2
Wi ∈ Rn×2
α ∈ RN
β ∈ R+
Rk ∈ R+
Variables
X k ∈ {0, 1}N ×n
P k ∈ [0, 1]N ×n
dki ∈ R+

Description
the total number of vacant taxis
the number of regions
the total number of predicted requests to be served by current vacant taxis at each region
matrix that describes taxi mobility patterns during one time slot
the initial positions of vacant taxis provided by GPS data
preferred positions of the i-th taxi at n regions
the upper bound of distance each taxi can drive for balancing the supply
the weight factor of the objective function
total number of predicted requests in the city
Description
the dispatch order matrix that represents the region each vacant taxi should go
predicted positions of dispatched taxis at the end of time slot k
lower bound of idle driving distance of the i-th taxi for reaching the dispatched location
Table I
PARAMETERS AND VARIABLES OF THE RHC PROBLEM (8).

{1,2,3}

{4,5}

1
[4]

2
[1]

{4,5}

1
[4]

2
[1]
adjacent
region

{4}

{2}

{1,2,3}

{4}

{2}

dispathing
solution

4
[9]

3
[2]

4
[9]

{7,8}

{6}

{7,8}

1TN X·jk
3
[2]

{6}

demand ratio for time slot k is defined as the total number of
vacant taxis decided by the total number of customer requests
during time slot k. When the supply demand ratio of every
region equals to that of the whole city, we have the following
equations for j = 1, . . . , n, k = 1, . . . , T ,

{6}

(a) A dispatch solution – taxi 2 goes (b) A dispatch solution – taxi 2 goes
to region 4, and taxi 4 goes to region to region 4, taxi 4 goes to region 3,
4.
and taxi 6 goes to region 4.
Figure 2.
Unbalanced supply and demand at different regions before
dispatching and possible dispatch solutions. A circle represents a region, with
a number of predicted requests ([·] inside the circle) and vacant taxis ({ taxi
IDs } outside the circle) before dispatching. A black dash edge means adjacent
regions. A red edge with a taxi ID means sending the corresponding vacant
taxi to the pointed region according to the predicted demand.

information. We would like to find a dispatch solution that
balances the supply demand ratio, while satisfying practical
constraints and not introducing large current and anticipated
future idle driving distance. Once dispatch decisions are sent to
vacant taxis, the dispatch center will wait for future computing
a new decision problem until updating sensing information in
the next period.
B. Optimal dispatch under operational constraints
The decision we want to make is the region each vacant taxi
should go. With the above initial information about supply and
predicted demand, we define a binary matrix X k ∈ {0, 1}N ×n
k
as the dispatch order matrix, where Xij
= 1 if and only if the
i-th taxi is sent to the j-th region during time k. Then
X k 1n = 1N , k = 1, . . . , T
must be satisfied, since every taxi should be dispatched to one
region during time k.
1) Two objectives: One design requirement is to fairly serve
the customers at different regions of the city — vacant taxis
should be allocated to each region according to predicted
demand across the entire city during each time slot. To
measure how supply matches demand at different regions, we
use the metric—supply demand ratio. For region j, its supply

rjk

=

1TN X·jk
rjk
N
,
⇐⇒
=
,
Rk
N
Rk

(1)

For convenience, we rewrite equation (1) as the following
equation about two row vectors
1 T k
1
1 X = k rk , k = 1, · · · , T.
(2)
N N
R
However, equation (2) can be too strict if used as a constraint,
and there may be no feasible solutions satisfying (2). This
is because decision variables X k , k = 1, . . . , T are integer
matrices, and taxis’ driving speed is limited that they may not
be able to serve the requests from any arbitrary region during
time slot k. Instead, we convert the constraint (2) into a soft
constraint by introducing a supply-demand mismatch penalty
function JE for the requirement that the supply demand ratio
should be balanced across the whole city, and one objective
of the dispatch problem is to minimize the following function
JE =

T
X
k=1

1 T k
1
1N X − k r k
N
R

.

(3)

1

The other objective is to reduce total idle driving distance of
all taxis. The process of traversing from the initial location to
the dispatched region will introduce an idle driving distance for
a vacant taxi, and we consider to minimize such idle driving
distance associated with meeting the dispatch solutions.
We begin with estimate the total idle driving distance associated with meeting the dispatch solutions. For the convenience
of routing process, the dispatch center is required to send the
GPS location of the destination to vacant taxis. The decision
variable X k only provides the region each vacant taxi should
go, hence we map the region ID to a specific longitude and
latitude position for every taxi. In practice, there are taxi
stations on roads in metropolitan areas, and we assume that
each taxi has a preferred station or is randomly assigned one at
every region by the dispatch system. We denote the preferred
geometry location matrix for the i-th taxi by Wi ∈ Rn×2 , and

5

[Wi ]j , where each row of Wi is a two-dimensional geometric
position on the map. The j-th row of Wi is the dispatch
k
position sent to the i-th taxi when Xij
= 1.
k
Once Xi is chosen, then the i-th taxi will go to the location
Xik Wi , because
equation holds
P the following
k
k
Xik Wi = q6=j Xiq
[Wi ]q + Xij
[Wi ]j = [Wi ]j ∈ R1×2 .
k
k
k
With a binary vector Xi that Xij = 1, Xiq
= 0 for q 6= j,
k
we have Xiq Wi = [0 0] for q 6= j. Since Wi does not need
to change with time k, the preferred location of each taxi at
every region in the city is stored as a matrix W, stored in
the dispatch center before the process of calculating dispatch
solutions starts. When updating information of vacant taxis,
matrix Wi is also updated for every current vacant taxi i.
The initial position Pi0 is provided by GPS data. Traversing
from position Pi0 to position Xi1 Wi for predicted demand will
introduce a cost, since the taxi drives towards the dispatched
locations without picking up a passenger. Hence, we consider
minimizing the total idle driving distance introduced by dispatching taxis. Driving in a city is approximated as traveling
on a grid road. To estimate the distance without knowing the
exact path, we use the Manhattan norm or one norm between
two geometric positions, which is widely applied as a heuristic
distance in path planning algorithms [22]. We define dki ∈ R as
the estimated idle driving distance of the i-th taxi for reaching
the dispatched location Xik Wi . For k = 1, a lower bound of
d1i is given by
d1i

>

kPi0

−

Xi1 Wi k1 ,

i = 1, . . . , N.

=f

k

(Xik−1 Wi ),

k

f :R

1×2

→R

1×2

,

(5)

where f k is a convex function, called a mobility pattern
function. To reach the dispatched location Xik Wi at the
beginning of time k from position Pik−1 , the approximated
driving distance is
dki > kf k (Xik−1 Wi ) − Xik Wi k1 .

(6)

The process to calculate a lower bound for dki is illustrated in
Figure 3.
Within time slot k, the distance that every taxi can drive
should be bounded by a constant vector αk ∈ RN :
dk 6 α k .
Total idle driving distance of all vacant taxis though time k =
1, . . . , T to satisfy service fairness is then denoted by
JD =

T X
N
X

dki .

min.

X k ,dk

J = JE + βJD

(4)

For k > 2, to estimate the anticipated future idle driving
distance induced by reaching dispatched position Xik Wi at
time k, we consider the trip at the beginning of time slot k
starts at the end location of time slot k − 1. However, during
time k − 1, taxis’ mobility patterns are related to pick-up
and drop-off locations of passengers, which are not directly
controlled by the dispatch center. So we assume the predicted
ending position for a pick-up location Xik−1 Wi during time
k − 1 is related to the starting position Xik−1 Wi as follows:
Pik−1

distance is nonzero only when a vacant taxi is dispatched to
a different region. We also require that the estimated distance
is a closed form function of the locations of the original and
dispatched regions, without knowledge about accurate traffic
conditions or exact time to reach the dispatched region. Hence,
in this work we use Manhattan norm to approximate the idle
distance—it is a closed form function of the locations of the
original and dispatched regions. When accessibility information of the road traffic network is considered in estimating
street-level distances, for the case that a taxi may not drive on
rectangular grids to pick up a passenger (for instance, when a
U-turn is necessary), Lee et.al have proposed a shortest time
path approach to pick up passengers in shortest time [15].
2) An RHC problem formulation: Since there exists a tradeoff between two objectives as discussed in Section II, we
define a weight parameter β k when summing up the costs
related to both objectives. A list of parameters and variables
is shown in Table I. When mixed integer programming is not
efficient enough for a large-scale taxi network regarding to the
problem size, one standard relaxation method is replacing the
k
k
constraint Xij
∈ {0, 1} by 0 ≤ Xij
≤ 1.
To summarize, we formulate the following problem (8)
based on the definitions of variables, parameters, constraints
and objective function

=
s.t

d1i
dki

>

T
X

1
1 T k
1 X − k rk
N N
R

k=1
kPi0
k

− Xi1 Wi k1 ,
(Xik−1 Wi ) −

> kf

i = 1, . . . , N,
k

k

d 6α ,

!
dki

i=1

i = 1, . . . , N,
Xik Wi k1 ,

k = 1, 2, . . . , T,

X 1n = 1N ,
06

1

N
X

k = 2, . . . , T,

k

k
Xij

+β

k

k = 1, 2, . . . , T,

6 1, i ∈ {1, . . . , N }, j ∈ {1, . . . , n}.
(8)

After getting an optimal solution X 1 of problem (8), for the
i-th taxi, we may recover binary solution through rounding
by setting the largest value of Xi1 to 1, and the others to
0. This may violate the constraint of d0i , but since we set a
conservative upper bound αk , and the rounding process will
return a solution that satisfies dki 6 αk +  with bounded ,
the dispatch solution can still be executed during time slot k.
Latitude

Estimated distance
Possible paths
Longitude

(7)

k=1 i=1

It is worth noting that the idle distance we estimate here is
the region-level distance to pick up predicted passengers — the

Figure 3. Illustration of the process to estimate idle driving distance to the
dispatched location for the i-th taxi at k = 2: predict ending location of
k = 1 denoted by EPi1 in (9), get the distance between locations EPi1 and
Xi2 Wi denoted by d2i in (10).

6

C. Discussions on the optimal dispatch formulation
1) Why use supply demand ratio as a metric: An intuitive
measurement of the difference between the number of vacant
taxis and predicted total requests at all regions is:
n
P
e=
|skj − rjk |,
j=1

where skj is the total number of vacant taxis sent to the j-th
region. However, when the total number of vacant taxis and
requests are different in the city, this error e can be large even
under the case that more vacant taxis are already allocated to
busier regions and fewer vacant taxis are left to regions with
less predicted demand. We do not have an evidence whether
the dispatch center already fairly allocates supply according
to varying demand given the value of the above error e.
2) The meaning of αk : For instance, when the length of
time slot k is one hour, and αk is the distance one taxi can
traverse during 20 minutes of that hour, this constraint means
a dispatch solution involves the requirement that a taxi should
be able to arrive the dispatched position within 20 minutes
in order to fulfill predicted requests. With traffic condition
monitoring and traffic speed predicting method [2], αk can
be adjusted according to the travel time and travel speed
information available for the dispatch system. This constraint
also gives the dispatch system the freedom to consider the
fact that drivers may be reluctant to drive idly for a long
distance to serve potential customers, and a reasonable amount
of distance to go according to predicted demand is acceptable.
The threshold αk is related to the length of time slot. In
general, the longer a time slot is, the larger αk can be, because
of constraints like speed limit.
3) One example of mobility pattern function f k : When
taxi’s mobility pattern duringPtime slot k is described by a
n
k
matrix C k ∈ Rn×n satisfying j=1 Cij = 1, where Cij
is the
probability that a vacant taxi starts within region i will end
within region j during time k. From the queueing-theoretical
perspective such probability transition matrix approximately
describes passenger’s mobility [32]. Given Xik−1 and the
mobility pattern matrix C k−1 ∈ [0, 1]n×n , the probability of
ending at each region for taxi i is
p=

n
X
k−1
[C k−1 ]j I(Xij
= 1) = Xik−1 C k−1 ∈ R1×n ,
j=1

k−1
where the indicator function I(Xij
= 1) = 1 if and
k−1
k−1
only if Xij = 1, and [C
]j is the j-th row of C k−1 .
However, introducing a stochastic formula in the objective
function will cause high computational complexity for a largescale problem. Hence, instead of involving the probability of
taking different paths in the objective function to formulate a
stochastic optimization problem, we take the expected value
of the position of i-th taxi by the end of time k − 1

Pik−1 =

n
X

pj [Wi ]j = pWi = Xik−1 C k−1 Wi .

(9)

j=1

Here Pik−1 ∈ R1×2 is a vector representing a predicted ending
location of the i-th taxi on the map at each dimension. Then a
lower bound of idle driving distance for heading to Xik Wi to

meet demand during k is given by the distance between Pik−1
defined as (9) and Xik Wi .
dki > k(Xik−1 C k−1 − Xik )Wi k1 .

(10)

In particular, when the transition probability C k , k = 1, . . . , T
is available, we can replace the constraint about dki by dki >
k(Xik−1 C k−1 − Xik )Wi k1 .
It is worth noting that dki is a function of Xik−1 and
k
Xi , and the estimation accuracy of idle driving distance
to dispatched positions Xik (k = 2, . . . , T ) depends on the
predicting accuracy of the mobility pattern during each time
slot k, or Pik−1 . The distance d1 is calculated based on realtime GPS location P 0 and dispatch position X 1 , and we use
estimations d2 , . . . , dT to measure the anticipated future idle
driving distances for meeting requests.
The error of estimated C k mainly affects the choice of idle
distance dk when the true ending region of a taxi by the end
of time slot k is not as predicted based on its starting region at
time slot k. This is because C k determines the constraint for
dk (k = 2, 3, . . . , T ) as described by inequality (10). However,
the system also collects real-time GPS positions to make a new
decision based on the current true positions of all taxis, instead
of only applying predicted locations provided by the mobility
pattern matrix. According to constraint (4) distance d1 is
determined by GPS sensing data P 0 and dispatch decision
X 1 , and only X 1 will be executed sent to vacant taxis as
the dispatch solutions after the system solving problem (8).
From this perspective, real-time GPS and occupancy status
sensing data is significant to improve the system’s performance
when we utilize both historical data and real-time sensing data.
We also consider the effect of an inaccurate mobility pattern
estimation C k when choosing the prediction time horizon T —
large prediction horizon will induce accumulating prediction
error in matrix C k and the dispatch performance will even
be worse. Evaluation results in Section V show how real-time
sensing data helps to reduce total idle driving distance and
how the mobility pattern error of different prediction horizon
T affects the system’s performance.
4) Information on road congestion and passenger destination: When road congestion information is available to the
dispatch system, function in (5) can be generalized to include
real-time congestion information. For instance, there is a high
probability that a taxi stays within the same region during one
time slot under congestions.
We do not assume that information of passenger’s destination is available to the system when making dispatch decisions,
since many passengers just hail a taxi on the street or at taxi
stations instead of reserving one in advance in metropolitan
areas. When the destination and travel time of all trips are
provided to the dispatch center via additional software or devices as prior knowledge, the trip information is incorporated
to the definition of ending position function (5) for problem
formulation (8). With more accurate trip information, we get a
better estimation of future idle driving distance when making
dispatch decisions for k = 1.
5) Customers’ satisfaction under balanced supply demand
ratio: The problem we consider in this work is reaching
fair service to increase global level of customers’ satisfaction,

7

which is indicated by a balanced supply demand ratio across
different regions of one city, instead of minimizing each individual customer’s waiting time when a request arrives at the
dispatch system. Similar service fairness metric has been applied in mobility on demand systems [32], and supply demand
ratio considered as an indication of utilization ratio of taxis
is also one regulating objective in taxi service market [29].
For the situation that taxi i will not pick up passengers in its
original region but will be dispatched to another region, the
dispatch decision results from the fact that global customers’
satisfaction level will be increased. For instance, when the
original region of taxi i has a higher supply demand ratio
than the dispatched region, going to the dispatched region
will help to increase customer’s satisfaction in that region. By
sending taxi i to some other region, customers’ satisfaction in
the dispatched region can be increased, and the value of the
supply-demand cost-of-mismatch function JE can be reduced
without introducing much extra total idle driving distance JD .
D. Robust RHC formulations
Previous work has developed multiple ways to learn passenger demand and taxi mobility patterns [2], [8], [13], and
accuracy of the predicted model will affect the results of
dispatch solutions. We do not have perfect knowledge of
customer demand and taxi mobility models in practice, and
the actual spatial-temporal profile of passenger demands can
deviate from the predicted value due to random factors such
as disruptive events. Hence, we discuss formulations of robust
taxi dispatch problems based on (8).
Formulation (8) is one computationally tractable approach
to describe the design requirements with a nominal model.
One advantage of the formulation (8) is its flexibility to adjust
the constraints and objective function according to different
conditions. With prior knowledge of scheduled events that
disturb the demand or mobility pattern of taxis, we are able
to take the effects of the events into consideration by setting
uncertainty parameters. For instance, when we have basic
knowledge that total demand in the city during time k is
about R̃k , but each region rjk belongs to some uncertainty
set, denoted by an entry wise inequality
R1k  rk  R2k ,
n
k
k
given R1 ∈ R and R2 ∈ Rn . Then
k
k
rjk ∈ [R1j
, R2j
], j = 1, . . . , n

Theorem 1. The robust RHC problem (12) is equivalent to
the following computationally efficient convex optimization
problem


T
n
N
X
X
X

J0 =
min
tkj + β k
dki 
X k ,dk ,tk

constraints of problem (8).
(12)

j=1

k=1

1N X·jk
−
s.t tkj ≥
N
1N X·jk
tkj ≥
−
N
j = 1, . . . , n,

i=1
k
R1j

R̃k
k
R2j

, tkj ≥

k
R1j

R̃k
k
R2j

, tkj ≥
R̃k
R̃k
, k = 1, . . . , T,

1N X·jk
,
N
1N X·jk
−
,
N
−

(13)

constraints of problem (8).
Proof: In the objective function, only the first term is
related to rk . To avoid the maximize expression over an
uncertain rk , we first optimize the term over rk for any fixed
X k . Let X·jk represent the j-th column of X k , then
1 k
1 T k
1N X −
r
N
R̃k
1
n
X
rjk
1 T k
1 X −
= max
N N ·j R̃k
R1k r k R2k
j=1
max

R1k r k R2k

=

n
X
j=1

max

k ,Rk ]
rjk ∈[R1j
2j

(14)

rjk
1 T k
1N X·j −
.
N
R̃k

The second equality holds because each rjk can be optimized
k
k
separately in this equation. For R1j
≤ rjk ≤ R2j
, we have
k
R1j

≤

rjk

≤

k
R2j

.
R̃k
R̃k
R̃k
Then the problem is to maximize each absolute value in (14)
for j = 1, . . . , n. Consider the following problem for x, a, b ∈
R to examine the character of maximization problem over an
absolute value:
(
|x − a|, if x > (a + b)/2
max |x − x0 | =
x0 ∈[a,b]
|x − b|, otherwise

(11)

is an uncertainty parameter instead of a fixed value as in
problem (8). Without additional knowledge about the change
of total demand in the whole city, we denote R̃k as the
approximated total demand in the city under uncertain rjk for
each region. By introducing interval uncertainty (11) to rk and
fixing R̃k on the denominator, we have the following robust
optimization problem (12)
!
N
T
X
X
1 k
1 T k
k
k
1 X −
r
+β
di
min.
max
N N
X k ,dk
R1k r k R2k
R̃k
1
i=1
k=1
s.t.

The robust optimization problem (12) is computationally
tractable, and we have the following Theorem 1 to show the
equivalent form to provide real-time dispatch decision.

= max{|x − a|, |x − b|}
= max{x − a, a − x, x − b, b − x}.
Similarly, for the problem related to rjk , we have
max

k ,Rk ]
rjk ∈[R1j
2j

(
=max

rjk
1N X·jk
−
N
R̃k

k
1N X·jk
R1j
−
,
N
R̃k

k
1N X·jk
R2j
−
N
R̃k

(15)

)
.

Thus, with slack variables tk ∈ Rn , we re-formulate the robust
RHC problem as (13).
Taxi mobility patterns during disruptive events can not be
easily estimated (in general), however, we have knowledge

8

such as a rough number of people are taking part in a
conference or competition, or even more customer reservations
because of events in the future. The uncertain set of predicted
demand rk can be constructed purely from empirical data such
as confidence region of the model, or external information
about disruptive events. By introducing extra knowledge besides historical data model, the dispatch system responds to
such disturbances with better solutions than the those without
considering model uncertainties. Comparison of results of (13)
and problem (8) is shown in Section V.
IV. RHC F RAMEWORK D ESIGN
Demand and taxi mobility patterns can be learned from
historical data, but they are not sufficient to calculate a
dispatch solution with dynamic positions of taxis when the
positions of the taxis change in real time. Hence, we design
an RHC framework to adjust dispatch solutions according to
real-time sensing information in conjunction with the learned
historical model. Real-time GPS and occupancy information
then act as feedback by providing the latest taxi locations, and
demand-predicting information for an online learning method
like [31]. Solving problem (8) or (12) is the key iteration step
of the RHC framework to provide dispatch solutions.
RHC works by solving the cost optimization over the
window [1, T ] at time k = 1. Though we get a sequence
of optimal solutions in T steps – X 1 , . . . , X T , we only
send dispatch decisions to vacant taxis according to X 1 . We
summarize the complete process of dispatching taxis with both
historical and real-time data as Algorithm 1, followed by a
detail computational process of each iteration. The lengths of
time slots for learning historical models (t1 ) and updating realtime information (t2 ) do not need to be the same, hence in
Algorithm 1 we consider a general case for different t1 , t2 .

Algorithm 1: RHC Algorithm for real-time taxi dispatch
Inputs: Time slot length t1 minutes, period of sending
dispatch solutions t2 minutes (t1 /t2 is an integer); a
preferred station location table W for every taxi in the
network; estimated request vectors r̂(h1 ),
h1 = 1, . . . , 1440/t1 , mobility patterns fˆ(h2 ),
h2 = 1, . . . , 1440/t2 ; prediction horizon T ≥ 1.
Initialization: The predicted requests vector r = r̂(h1 )
for corresponding algorithm start time h1 .
while Time is the beginning of a t2 time slot do
(1) Update sensor information for initial position of
vacant taxis P 0 and occupied taxis P 00 , total number
of vacant taxis N , preferred dispatch location
matrices Wi .
if time is the beginning of an h1 time slot then
Calculate r̂(h1 ) if the system applies an online
training method; count total number of occupied
taxis no (h1 ); update vector r.
end
(2) Update the demand vectors rk based on predicted
demand r̂(h1 ) and potential service ability of no (h1 )
occupied taxis; update mobility functions f k (·) (for
example, C k ), set up values for idle driving distance
threshold αk and objective weight β k ,
k = 1, 2, . . . , T . (3) if there is knowledge of demand
rk as an uncertainty set ahead of time then
solve problem (13);
else
solve problem (8) for a certain demand model;
end
(4) Send dispatch orders to vacant taxis according to
the optimal solution of matrix X 1 . Let h2 = h2 + 1.
end
Return:Stored sensor data and dispatch solutions.

A. RHC Algorithm
Remark 1. Predicted values of requests r̂(h1 ) depend on the
modeling method of the dispatch system. For instance, if the
system only applies historical data set to learn each r̂(h1 ),
r̂(h1 ) is not updated with real-time sensing data. When the
system applies online training method such as [31] to update
r̂(h1 ) for each h1 , values of r, rk are calculated based on the
real-time value of r̂(h1 ).
1) Update r: We receive sensing data of both occupied
and vacant taxis in real-time. Predicted requests that vacant
taxis should serve during h1 is re-estimated at the beginning
of each h1 time. To approximate the service capability when
an occupied taxi turns into vacant during time h1 , we define
the total number of drop off events at different regions as a
vector dp(h1 ) ∈ Rn×1 . Given dp(h1 ), the probability that a
drop off event happens at region j is
(16)

roj (h1 ) = dpdj (h1 ) × no (h1 )e,
where d·e is the ceiling function, no (h1 ) is the total number
of current occupied taxis at the beginning of time h1 provided
by real-time sensor information of occupied taxis. Let
r = r̂(h1 ) − ro (h1 ),
then the estimated service capability of occupied taxis is
deducted from r for time slot h1 .
2) Update rk for problem (8): We assume that requests
are uniformly distributed during h1 . Then for each time k of
length t2 , if the corresponding physical time is still in the
current h1 time slot, the request is estimated as an average
part of r; else, it is estimated as an average part for time slot
h1 + 1, h1 + 2, . . . , etc. The rule of choosing rk is
(1
if (k + h2 − 1)t2 ≤ h1 t1
H r,
k
r = 1 l (k+h2 −1)t2 m
, otherwise
H r̂
t1

where dpj (h1 ) is the number of drop off events at region
j during h1 . We assume that an occupied taxi will pick up
at least one passenger within the same region after turning
vacant, and we approximate future service ability of occupied
taxis at region j during time h1 as

where H = t1 /t2 .
3) Update rk for robust dispatch (13): When there are
disruptive events and the predicted requests number is a range
r̂(h1 ) ∈ [R̂1 (h1 ), R̂2 (h1 )], similarly we set the uncertain set
of rk as the following interval for the computationally efficient

pdj (h1 ) = dpj (h1 )/1n dp(h1 ),

9

form of robust dispatch problem (13)
h
i

1

R̂
(h
)
−
r
(h
),
R̂
(h
)
−
r
(h
)
,
1
1
o
1
2
1
o
1

 H
k
r ∈
if (k
h +h
mi
l2 − 1)t2 ≤ mh1 t1 , l


 1 R̂ ( (k+h2 −1)t2 ), R̂ ( (k+h2 −1)t2 ) , o.w.
2
1
H
t1
t1
4) Spatial and temporal granularity of Algorithm 1: The
main computational cost of each iteration is on step (3), and
t2 should be no shorter than the computational time of the
optimization problem. We regulate parameters according to
experimental results based on a given data set, since there are
no closed form equations to decide optimal design values of
these parameters.
For the parameters we estimate from a given GPS dataset,
the method we use in the experiments (but not restricted to it)
will be discussed in Section V. The length of every time slot
depends on the predict precision of prediction, desired control
outcome, and the available computational resources. We can
set a large time horizon to consider future costs in the long
run. However, in practice we do not have perfect predictions,
thus a large time horizon may amplify the prediction error over
time. Applying real-time information to adjust taxi supply is
a remedy to this problem. Modeling techniques are beyond
the scope of this work. If we have perfect knowledge of
customer demand and taxi mobility models, we can set a
large time horizon to consider future costs in the long run.
However, in practice we do not have perfect predictions, thus
a large time horizon may amplify the prediction error over
time. Likewise, if we choose a small look-ahead horizon, then
the dispatch solution may not count on idle distance cost of
the future. Applying real-time information to adjust taxi supply
is a remedy to this problem. With an approximated mobility
pattern matrix C k , the dispatch solution with large T is even
worse than small T .
5) Selection process of parameters β k , αk , and T : The
process of choosing values of parameters for Algorithm 1
is a trial and adjusting process, by increasing/decreasing the
parameter value and observing the changing trend of the
dispatch cost, till a desired performance is reached or some
turning point occurs that the cost is not reduced any more.
For instance, objective weight β k is related to the objective of
the dispatch system, whether it is more important to reach fair
service or reduce total idle distance. Some parameter is related
to additional information available to the system besides realtime GPS and occupancy status data; for instance, αk can be
adjusted according to the average speed of vehicles or traffic
conditions during time k as discussed in subsection III-C2.
Adjustments of parameters such as objective weight β k , idle
distance threshold αk , prediction horizon T when considering
the effects of model accuracy, control objectives are shown in
Section V. A formal parameter selection method is a direction
for future work.
B. Multi-level dispatch framework
We do not restrict the data source of customer demand – it
can be either predicted results or customer reservation records.
Some companies provide taxi service according to the current

requests in the queue. For reservations received by the dispatch
center ahead of time, the RHC framework in Algorithm 1 is
compatible with this type of demand information — we then
assign value of the waiting requests vector rk , taxi mobility
function f k in (8) according to the reservations, and the
solution is subject to customer bookings.
For customer requests received in real-time, a multi-level
dispatch framework is available based on Algorithm 1. The
process is as follows: run Algorithm 1 with predicted demand
rk , and send dispatch solutions to vacant taxis. When vacant
taxis arrive at dispatched locations, the dispatch center updates
real-time demand such as bookings that recently appear in the
system, then the dispatch method based on current demand
such as the algorithm designed by Lee et al. [15] can be
applied. By this multi-level dispatch framework, vacant taxis
are pre-dispatched at a regional level according to predicted
demand using the RHC framework, and then specific locations
to pick up a passenger who just booked a taxi is sent to a
vacant taxi according to the shortest time path [15], with the
benefit of real-time traffic conditions.
V. C ASE S TUDY: M ETHOD E VALUATION
We conduct trace-driven simulations based on a San Francisco taxi data set [24] summarized in Table II. In this data
set, a record for each individual taxi includes four entries: the
geometric position (latitude and longitude), a binary indication
of whether the taxi is vacant or with passengers, and the Unix
epoch time. With these records, we learn the average requests
and mobility patterns of taxis, which serve as the input of
Algorithm 1. We note that our learning model is not restricted
to the data set used in this simulation, and other models [31]
and date sets can also be incorporated.
We implement Algorithm 1 in Matlab using the optimization
toolbox called CVX [9]. We assume that all vacant taxis follow
the dispatch solution and go to suggested regions. Inside a
target region, we assume that a vacant taxi automatically
picks up the nearest request recorded by the trace data, and
we calculate the total idle mileage including distance across
regions and inside a region by simulation. The trace data
records the change of GPS locations of a taxi in a relatively
small time granularity such as every minute. Moreover, there
is no additional information about traffic conditions or the
exact path between two consecutive data points when they
were recorded. Hence, we consider the path of each taxi as
connected road segments determined by each two consecutive
points of the trace data we use in this section. Assume the
latitude and longitude values of two consecutive points in the
trace data are [lx1 , ly1 ] and [lx2 , ly2 ], for a short road segment,
the mileage distance between the two points (measured in one
minute) is approximated as being proportional to the value
(|lx1 − lx2 | + |ly1 − ly2 |). The geometric location of a taxi is
directly provided by GPS data. Hence, we calculate geographic
distance directly from the data first, and then convert the result
to mileage.
Experimental figures shown in Subsection V-B and V-D are
average results of all weekday data from the data set II. Results
shown in Subsection V-C are based on weekend data.

10

Taxicab GPS Data set
Number of Taxis Data Size
500
90M B

Collection Period
05/17/08-06/10/08

Record Number
1, 000, 000

ID
Date and Time

Format
Status
Direction
Speed
GPS Coordinates

600

Average requests number during a weekday
Region 3
Region 4
Region 7
Region 10

400

600

Average requests number during weekends
Region 3
Region 4
Region 7
Region 10

400

200

0

Average requests number

Average requests number

Table II
S AN F RANCISCO DATA IN THE E VALUATION S ECTION . G IANT BASEBALL GAME IN AT&T PARK ON M AY 31, 2008 IS A DISRUPTIVE EVENT WE USE FOR
EVALUATING THE ROBUST OPTIMIZATION FORMULATION .

200

2

4

6

8 10 12 14 16 18 20 22 24
Time: hour

0

2

4

6

Average drop off events number of a weekday
600
Region 3
Region 4
Region 7
400
Region 10
200

0

2

4

6

8 10 12 14 16 18 20 22 24
Time: hour

(b) Requests during weekends

Average drop off events number

Average drop off events number

(a) Requests during weekdays

8 10 12 14 16 18 20 22 24
Time: hour

Average drop off events during weekends
Region 3
Region 4
Region 7
Region 10

600
400
200
0

2

4

6

8 10 12 14 16 18 20 22 24
Time: Hour

(c) Drop off during weekdays
(d) Drop off during weekends
Figure 4. Requests at different hours during weekdays and weekends, for four selected regions. A given historical data set provides basic spatiotemporal
information about customer demands, which we utilize with real-time data to dispatch taxis.

A. Predicted demand based on historical data
Requests during different times of a day in different regions
vary a lot, and Figure 4(a) and Figure 4(b) compare bootstrap
results of requests r̂(h1 ) on weekdays and weekends for
selected regions. This shows a motivation of this work—
necessary to dispatch the number of vacant taxis according
to the demand from the perspective of system-level optimal
performance. The detailed process is described as follows.
The original SF data set does not provide the number of
pick up events, hence one intuitive way to determine a pick
up (drop off) event is as follows. When the occupancy binary
turns from 0 to 1 (1 to 0), it means a pick up (drop off) event
has happened. Then we use the corresponding geographical
position to determine which region this pick up (drop off)
belongs to; use the time stamp data to decide during which
time slot this pick up (drop off) happened. After counting
the total number of pick up and drop off events during
each time slot at every region, we obtain a set of vectors
rd0 (hk ), dpd0 (hk ), d0 = 1, . . . , d, where d is the number of
days for historical data . In the following analysis, each time
slot h1 is the time slot of predicting demand model chosen
by the RHC framework. The SF data set includes about 24
days of data, so we use d = 18 for weekdays, and d = 6
for weekends. The bootstrap process for a given sample time
number B = 1000 is given as follows.

(a) Randomly sample a size d dataset with replacement from
the data set {r1 (h1 ), . . . , rd (h1 )}, calculate
r̂1 (h1 ) =

d
1 X
rd0 (h1 ), for h1 = 1, . . . , 1440/h1 .
d 0
d =1

(b) Repeat step (a) for (B − 1) times, so that we have B
estimates for each h1 ,
r̂b (h1 ), b = 1, . . . , B.
The estimated mean value of P
r̂(h1 ) based on B samples is
B
1
r̂(h1 ) = B l=1 r̂l (h1 ).
(c) Calculate the sample variance of the B estimates of r(h1 )
for each h1 ,
V̂r̂(h1 ) =

B
B
1 X b
1 X l
(r̂ (h1 ) −
r̂ (h1 )).
B
B
b=1

(17)

l=1

To estimate the demand range for robust dispatch problem (13) according to historical data, we construct the uncertain set of demand rk based on the mean and variance of the
bootstrapped demand model. For every region j, the boundary
of demand interval is defined as
q
R̃1,j (h1 ) = r̂j (h1 ) − V̂r̂(h1 ),j ,
q
(18)
R̃2,j (h1 ) = r̂j (h1 ) + V̂r̂(h1 ),j ,

11

B. RHC with real-time sensor information
To estimate a mobility pattern matrix Ĉ(h2 ), we define a
matrix T (h2 ), where T (h2 )ij is the total number of passenger
trajectories that starting at region i and ending at region j
during time slot h2 . We also apply
P bootstrap process to get
T̂ (h2 ), and Ĉ(h2 )ij = T̂ (h2 )ij /( T̂ (h2 )ij ). Table III shows
j

Average total idle distance: mile

one row of Ĉ(h2 ) for 5:00-6:00 pm during weekdays, the
transition probability for different regions. The average cross
validation error for estimated mobility matrix Ĉ(h2 ) of time
slot h2 , h2 = 1, . . . , 24 during weekdays is 34.8%, which
is a reasonable error for estimating total idle distance in the
RHC framework when real-time GPS and occupancy status
data is available. With only estimated mobility pattern matrix
Ĉ(h2 ), the total idle distance is reduced by 17.6% compared
with the original record without a dispatch method, as shown
in Figure 5. We also tested the case when the dispatch
algorithm is provided with the true mobility pattern matrix
C k , which is impossible in practice, and the dispatch solution
reduces the total idle distance by 68% compared with the
original record. When we only have estimated mobility pattern
matrices instead of the true value to determine ending locations
and potential total idle distance for solving problem (8) or (13),
updating real-time sensing data compensates the mobility
pattern error and improves the performance of the dispatch
framework.
Real-time GPS and occupancy data provides latest position
information of all vacant and occupied taxis. When dispatching
available taxis with true initial positions, the total idle distance
600
480

Idle distance comparison
Dispatch with RT information
Dispatch without RT information
No dispatch

360
240
120
0

2

4

6

8 10 12 14 16 18 20 22 24
Time: Hour
Figure 5. Average idle distance comparison for no dispatch, dispatch without
real-time data, and dispatch with real-time GPS and occupancy information.
Idle distance is reduced by 52% given real-time information, compared with
historical data without dispatch solutions.

Figure 6. Heat map of passenger picking-up events in San Francisco (SF)
with a region partition method. Region 3 covers several busy areas, include
Financial District, Chinatown, Fisherman Wharf. Region 7 is mainly Mission
District, Mission Bay, the downtown area of SF.

is reduced by 52% compared with the result without dispatch
methods, as shown in Figure 5, which is compatible with
the performance when both true mobility pattern matrix C k
and real-time sensing data are available. This is because the
optimization problem (8) returns a solution with smaller idle
distance cost given the true initial position information P 0 ,
instead of estimated initial position provided only by mobility
pattern of the previous time slot in the RHC framework.
Figure 5 also shows that even applying dispatch solution
calculated without real-time information is better than non
dispatched result.
Based on the partition of Figure 6, Figure 7 shows that the
supply demand ratio at each region of the dispatch solution
with real-time information is closest to the supply demand
ratio of the whole city, and the error N1 1TN X k − R1k rk 1
is reduced by 45% compared with no dispatch results. Even
the supply demand ratio error of dispatching without realtime information is better than no dispatch solutions. We still
allocate vacant taxis to reach a nearly balanced supply demand
ratio regardless of their initial positions, but idle distance is
increased without real-time data, as shown in Figure 5. Based
on the costs of two objectives shown in Figures 5 and 7,
the total cost is higher without real-time information, mainly
results from a higher idle distance.
C. Robust taxi dispatch
One disruptive event of the San Francisco data set is
Giant baseball at AT&T park, and we choose the historical
record on May 31, 2008 as an example to evaluate the robust
optimization formulation (12). Customer request number for
Supply demand ratio

where r̂j (h1 ) is the average value of each step (b) and V̂r̂(h1 ),j
is the variance of estimated request number defined in (17).
This one standard deviation range is used for evaluating the
performance of robust dispatch framework in this work.
Estimated drop off events vectors dp(h1 ) are also calculated
via a similar process. Figure 4(c) and 4(d) show bootstrap
results of passenger drop off events dp(h1 ) on weekdays and
weekends for selected regions.
For evaluation convenience, we partition the city map to
regions with equal area. To get the longitude and latitude
position Wi ∈ Rn×2 of vacant taxi i, we randomly pick up a
station position in the city drawn from the uniform distribution.

2.0

Supply demand ratio under different conditions
Global supply demand ratio

1.7

Dispatch without RT information

1.4

Dispatch with RT information
No dispatch

1.1
0.8
0.5

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Region ID
Figure 7.
Supply demand ratio of the whole city and each region for
different dispatch solutions. With real-time GPS and occupancy data, the
supply demand ratio of each region is closest to the global level. The supply
demand ratio mismatch error is reduced by 45% with real-time information,
compared with historical data without dispatch solutions.

12

Region ID
Transit probability
Region ID
Transit probability

1
0.0032
9
0.0001

2
0.0337
10
0.0050

3
0.5144
11
0.0340

4
0.0278
12
0.0136

5
0.0132
13
0.0018

6
0.0577
14
0.0082

7
0.1966
15
0.0248

8
0.0263
16
0.0396

Table III
A N ESTIMATION OF STATE TRANSITION MATRIX BY BOOTSTRAP : ONE ROW OF MATRIX Ĉ(hk )
2
1.998
1.718
5.434

10
2.049
1.096
13.009

without dispatch
2.664
4. 519
47.854

Table IV
AVERAGE COST COMPARISON FOR DIFFERENT VALUES OF β k .

areas near AT&T park is affected, especially Region 7 around
the ending time of the game, which increases about 40% than
average value.
Figure 8 shows that with dispatch solution of the robust
optimization formulation (12), the supply demand mismatch
error N1 1TN X k − R1k rk 1 is reduced by 25% compared with
the solution of (8) and by 46% compared with historical
data without dispatch. The performance of robust dispatch
solutions does not vary significantly and depends on what type
of predicted uncertain demand is available when selecting the
formulation of robust dispatch method. Even under solutions
of (8), the total supply demand ratio error is reduced 28%
compared historical data without dispatch. In general, we
consider the factor of disruptive events in a robust RHC
iteration, thus the system level supply distribution responses
to the demand better under disturbance.
D. Design parameters for Algorithm 1

Supply demand ratio

Parameters like the length of time slots, the region division
function, the objective weight parameter and the prediction
horizon T of Algorithm 1 affect the results of dispatching cost
in practice. Optimal values of parameters for each individual
data set can be different. Given a data set, we change one
parameter to a larger/smaller value while keep others the
same, and compare results to choose a suboptimal value of
the varying parameter. We compare the cost of choosing
different parameters for Algorithm 1, and explain how to adjust
parameters according to experimental results based on a given
historical data set with both GPS and occupancy record.
How the objective weight of (8) – β k affects the cost:
The cost function includes two parts –the idle geographical
distance (mileage) cost and the supply demand ratio mismatch
1.8
1.5
1.3

Supply demand ratio comparison
Global supply demand ratio
Robust optimization (9)
Optimization (8)
No dispatch

1.0
0.7
0.4

2

4

6

8
10 12 14 16
Region ID
Figure 8. Comparison of supply demand ratio at each region under disruptive
events, for solutions of robust optimization problems (12), problem (8) in the
RHC framework, and historical data without dispatch. With the roust dispatch
solutions of (12), the supply demand ratio mismatch error is reduced by 46%.

cost. This trade-off between two parts is addressed by β k , and
the weight of idle distance increases with β k . A larger β k
returns a solution with smaller total idle geographical distance,
while a larger error between supply demand ratio, i.e., a larger
1 k
1 T
k
value. The two components of the cost
N 1N X − R k r
1
with different β k by Algorithm 1, and historical data without
Algorithm 1 are shown in Table IV. The supply demand ratio
mismatch is shown in the s/d error column.
We calculate the total cost as (s/d error +β k × idle distance)
(Use β k = 10 for the without dispatch column). Though with
β k = 0 we can dispatch vacant taxis to make the supply
demand ratio of each region closest to that of the whole city, a
larger idle geographical distance cost is introduced compared
with β k = 2 and β = 10. Compare the idle distance when
β k = 0 with the data without dispatch, we get 23% reduction;
compare the supply demand ratio error of β k = 10 with the
data without dispatch, we get 32%.
Average total idle distance during different hours of one
day for a larger β k is smaller, as shown in Figure 10. The
supply demand ratio error at different regions of one time slot
is increased with larger β k , as shown in Figure 9.
How to set idle distance threshold αk : Figure 11 compares
the error between local supply demand ratio and global supply
demand ratio. Since we directly use geographical distance
Supply demand ratio for different
Global supply demand ratio
k
=0

1.5
Supply demand ratio

0
0.645
3.056
0.645

1.3

k

1.1

k

=10

k

=2

0.9
0.7
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Region ID

Figure 9. Comparison of supply demand ratios at each region during one
time slot for different β k values. When β k is smaller, we put less cost weight
on idle distance that taxis are allowed to run longer to some region, and taxi
supply matches with the customer requests better.

Average total idle distance: mile

βk
s/d error
idle distance
total cost

Average total idle distance for different
=0
=2
180
= 10
240

120

60

0

2

4

6

8

10 12 14 16 18 20 22 24

Time: hour

Figure 10. Average total idle distance of taxis at different hours. When β k
is larger, the idle distance cost weights more in the total cost, and the dispatch
solution causes less total idle distance.

13

Supply demand ratio for different

Supply demand ratio

5

k

k

=0.02
global supply demand ratio
No dispatch
k
=0.002

4
3

k

2

=0.08

1
0

8
10 12 14 16
Region ID
Figure 11. Comparison of supply demand ratios at each region during one
time slot for different αk . When αk is larger, vacant taxis can traverse longer
to dispatched locations and match with customer requests better.

4

6

Total idle distance for different region partitions
4 regions
120 16 regions
64 regions
0 100 regions
256 regions
360

Average total idle distance: mile

90
60
30
0

8 10 12 14 16 18 20 22 24
Time: hour
Figure 13. Average total idle distance at different time of one day compared
for different prediction horizons.When T = 4, idle distance is decreased at
most hours compared with T = 2. For T = 8 the costs are worst.

120
0

240

4

6

8 10 12 14 16 18 20 22 24
Time: hour
Figure 12. Average total idle distance of all taxis during one day, for different
region partitions. Idle distance decreases with a larger region-division number,
till the number increases to a certain level.

6

t2=1 hour

t2=30 mins
t2=10 mins

180

t2 = 1 min

120
60
2

8 10 12 14 16 18 20 22 24
Time: hour
Figure 14. Comparison of average total idle distance for different t2 – the
length of time slot for updating sensor information. With a smaller t2 , the cost
is smaller. But when t2 = 1 is too small to complete calculating problem (8),
the dispatch result is not guaranteed to be better than t2 = 10.

4

6

Supply/demand ratio at each region for different t2
1.7
1.5
1.3
1.1

Global supply/demand ratio
t2=10 mins
t2=30 mins
t2=1 min
t2=1h

0.9
0.7
0.5

2

4

Average total idle distance for different t2

240

240

2

distance of vacant taxis at most hours of one day decreases
as T increases. For T = 8 the driving distance is the largest.
Theoretical reasons are discussed in Section IV.
Decide the length of time slot t2 : For simplicity, we choose
the time slot t1 as one hour, to estimate requests. A smaller
time slot t2 for updating GPS information can reduce the
total idle geographical distance with real-time taxi positions.
However, one iteration of Algorithm 1 is required to finish in
less than t2 time, otherwise the dispatch order will not work for
the latest positions of vacant taxis, and the cost will increase.
Hence t2 is constrained by the problem size and computation
capability. Figure 14 shows that smaller t2 returns a smaller
idle distance, but when t2 = 1 Algorithm 1 can not finish
one step iteration in one minute, and the idle distance is not
reduced. The supply demand ratio at each region does not vary
much for t2 = 30, t2 = 10 minutes and t2 = 1 hour, as shown
in Figure 15. Comparing two parts of costs, we get that t2
mainly affects the idle driving distance cost in practice.

Supply/demand ratio

Average total idle distance:mile

2

Average total idle distance for different T
T=8
T=2
150
T=4
120
180

Average total idle distance: mile

measured by the difference between longitude and latitude
values of two points (GPS locations) on the map, the threshold
value αk is small — 0.1 difference in GPS data corresponds
to almost 7 miles distance on the ground. When αk increase,
the error between local supply demand ratio and global supply
demand ratio decreases, since vacant taxis are more flexible
to traverse further to meet demand.
How to choose the number of regions: In general, the
dispatch solution of problem (8) for a vacant taxi is more
accurate by dividing a city into regions of smaller area, since
the dispatch is closer to road-segment level. However, we
should consider other factors when deciding the number of
regions, like the process of predicting requests vectors and
mobility patterns based on historical data. A linear model we
assume in this work is not a good prediction for future events
when the region area is too small, since pick up and drop off
events are more irregular in over partitioned regions. While
Increasing n, we also increase the computation complexity.
Note that the area of each region does not need to be the
same as we divide the city in this experiment.
Figure 12 shows that the idle distance will decrease with a
larger region division number, but the decreasing rate slows
down; while the region number increases to a certain level,
the idle distance almost keeps steady.
How to decide the prediction Horizon T : In general,
when T is larger, the total idle distance to get a good supply
demand ratio in future time slots should be smaller. However,
when T is large enough, increasing T can not reduce the
total idle distance any more, since the model prediction error
compensates the advantage of considering future costs. For
T = 2 and T = 4, Figure 13 shows that the average total idle

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Region ID

Figure 15. Comparison of the supply demand ratio at different regions for
different lengths of time slot t2 . For t2 = 30, t2 = 10 mins and t2 = 1 hour,
results are similar. For t2 = 1 min, the supply demand ratio is even worse at
some regions, since the time slot is too short to complete one iteration.

14

VI. C ONCLUSION
In this paper, we propose an RHC framework for the
taxi dispatch problem. This method utilizes both historical
and real-time GPS and occupancy data to build demand
models, and applies predicted models and sensing data to
decide dispatch locations for vacant taxis considering multiple
objectives. From a system-level perspective, we compute suboptimal dispatch solutions for reaching a globally balanced
supply demand ratio with least associated cruising distance
under practical constraints. Demand model uncertainties under
disruptive events are considered in the decision making process
via robust dispatch problem formulations. By applying the
RHC framework on a data set containing taxi operational
records in San Francisco, we show how to regulate parameters such as objective weight, idle distance threshold, and
prediction horizon in the framework design process according
to experiments. Evaluation results support system level performance improvements of our RHC framework. In the future, we
plan to develop privacy-preserving control framework when
data of some taxis are not shared with the dispatch center.
R EFERENCES
[1] I. Amundson and X. D. Koutsoukos. A survey on localization
for mobile wireless sensor networks. In Mobile Entity Localization and Tracking in GPS-less Environnments, pages 235–254.
Springer Berlin Heidelberg, 2009.
[2] M. Asif, J. Dauwels, C. Goh, A. Oran, E. Fathi, M. Xu,
M. Dhanya, N. Mitrovic, and P. Jaillet. Spatio and temporal patterns in large-scale traffic speed prediction. IEEE Transactions
on Intelligent Transportation Systems, (15):797–804, 2014.
[3] M. E. Berge and C. A. Hopperstad. Demand driven dispatch: A
method for dynamic aircraft capacity assignment, models and
algorithms. Operations Research, 41(1):153–168, 1993.
[4] S. Blandin, D. Work, P. Goatin, B. Piccoli, and A. Bayen.
A general phase transition model for vehicular traffic. SIAM
Journal on Applied Mathematics, 71(1):107–127, 2011.
[5] E. Bradley. Bootstrap methods: Another look at the jackknife.
The Annals of Statistics, 7(1-26), 1979.
[6] D. R. Choffnes and F. E. Bustamante. An integrated mobility
and traffic model for vehicular wireless networks. In Proceedings of the 2nd ACM International Workshop on Vehicular Ad
Hoc Networks, pages 69–78, 2005.
[7] J. Cortes, S. Martinez, T. Karatas, and F. Bullo. Coverage
control for mobile sensing networks. IEEE Transactions on
Robotics and Automation, 20(2):243–255, 2004.
[8] R. Ganti, M. Srivatsa, and T. Abdelzaher. On limits of travel
time predictions: Insights from a new york city case study. In
IEEE 34th ICDCS, pages 166–175, June 2014.
[9] M. Grant and S. Boyd. CVX: Matlab software for disciplined
convex programming, version 2.1. http://cvxr.com/cvx, 2014.
[10] Hara Associates Inc. and Corey, Canapary& Galanis.
http://www.sfmta.com/sites/default/files/Draft%20SF%
20UserSurvey%2055%20WEB%20version04042013.pdf.
[11] J. Herrera, D. Work, R. Herring, X. Ban, Q. Jacobson, and
A. Bayen. Evaluation of traffic data obtained via GPS-enabled
mobile phones: The Mobile Century field experiment. Transportation Research Part C, 18(4):568–583, 2010.
[12] A. Howard, M. Matarić, and G. Sukhatme. Mobile sensor
network deployment using potential fields: A distributed, scalable solution to the area coverage problem. In Distributed
Autonomous Robotic Systems 5. Springer Japan, 2002.
[13] Y. Huang and J. W. Powell. Detecting regions of disequilibrium
in taxi services under uncertainty. In Proceedings of the 20th
International Conference on Advances in Geographic Information Systems, number 10, pages 139–148, 2012.

[14] K.-D. Kim. Collision free autonomous ground traffic: A
model predictive control approach. In Proceedings of the
4th ACM/IEEE International Conference on Cyber-Physical
Systems, number 10, pages 51–60, 2013.
[15] D.-H. Lee, R. Cheu, and S. Teo. Taxi dispatch system based on
current demands and real-time traffic conditions. Transportation
Research Record:Journal of the Transportation Research Board,
8(1882):193–200, 2004.
[16] B. Li, D. Zhang, L. Sun, C. Chen, S. Li, G. Qi, and Q. Yang.
Hunting or waiting? discovering passenger-finding strategies
from a large-scale real-world taxi dataset. In IEEE International Conference on Pervasive Computing and Communications Workshops (PERCOM Workshops), pages 63–38, 2011.
[17] W. Li and C. Cassandras. A cooperative receding horizon
controller for multivehicle uncertain environments. IEEE Transactions on Automatic Control, 51(2):242–257, 2006.
[18] Z. Liao. Real-time taxi dispatching using global positioning
systems. Communications of the ACM, 46(5):81–83, May 2003.
[19] F. Miao, S. Lin, S. Munir, J. A. Stankovic, H. Huang, D. Zhang,
T. He, and G. J. Pappas. Taxi dispatch with real-time sensing
data in metropolitan areas: A receding horizon control approach.
In Proceedings of the 6th ACM/IEEE International Conference
on Cyber-Physical Systems, ICCPS ’15, pages 100–109, 2015.
[20] R. Negenborn, B. D. Schutter, and J. Hellendoorn. Multi-agent
model predictive control for transportation networks: Serial
versus parallel schemes. Engineering Applications of Artificial
Intelligence, 21(3):353 – 366, 2008.
[21] New York City Taxi and Limousine Commission.
http://www.nyc.gov/html/tlc/downloads/pdf/tot survey results
02 10 11.pdf.
[22] C. Petres, Y. Pailhas, P. Patron, Y. Petillot, J. Evans, and
D. Lane. Path planning for autonomous underwater vehicles.
IEEE Transactions on Robotics, 23(2):331–341, 2007.
[23] S. Phithakkitnukoon, M. Veloso, C. Bento, A. Biderman, and
C. Ratti. Taxi-aware map: Identifying and predicting vacant
taxis in the city. In the First International Joint Conference on
Ambient Intelligence, pages 86–95, 2010.
[24] M. Piorkowski, N. Sarafijanovic-Djukic, and M. Grossglauser.
A parsimonious model of mobile partitioned networks with
clustering. In First International Communication Systems and
Networks and Workshops (COMSNETS), pages 1–10, 2009.
[25] J. W. Powell, Y. Huang, F. Bastani, and M. Ji. Towards reducing taxicab cruising time using spatio-temporal profitability
maps. In Proceedings of the 12th International Conference on
Advances in Spatial and Temporal Databases, number 19, pages
242–260, 2011.
[26] M. Qu, H. Zhu, J. Liu, G. Liu, and H. Xiong. A cost-effective
recommender system for taxi drivers. In 20th ACM SIGKDD
International Conference on KDD, pages 45–54, 2014.
[27] K.-T. Seow, N. H. Dang, and D.-H. Lee. A collaborative multiagent taxi-dispatch system. IEEE Transactions on Automation
Science and Engineering, 7(3):607–616, 2010.
[28] C. Tomlin, G. Pappas, and S. Sastry. Conflict resolution for air
traffic management: a study in multiagent hybrid systems. IEEE
Transactions on Automatic Control, 43(4):509–521, 1998.
[29] H. Yang, S. Wong, and K. Wong. Demand supply equilibrium
of taxi services in a network under competition and regulation.
Transportation Research Part B: Methodological, 36:799–819,
2002.
[30] J. Yang, P. Jaillet, and H. Mahmassani. Real-time multivehicle
truckload pickup and delivery problems. Transportation Science, 38(2):135–148, 2004.
[31] D. Zhang, T. He, S. Lin, S. Munir, and J. A. Stankovic. Dmodel:
Online taxicab demand model from big sensor data in. In IEEE
International Congress on Big Data, pages 152–159, 2014.
[32] R. Zhang and M. Pavone. Control of robotic mobility-ondemand systems: a queueing-theoretical perspective. In Proceedings of Robotics: Science and Systems, July 2014.

15

Fei Miao (S’13) received the B.Sc. degree in
Automation from Shanghai Jiao Tong University,
Shanghai, China in 2010. Currently, she is working toward the Ph.D. degree in the Department of
Electrical and Systems Engineering at University of
Pennsylvania. Her research interests include datadriven real-time control frameworks of large-scale
interconnected cyber-physical systems under model
uncertainties, and resilient control frameworks to
address security issues of cyber-physical systems.
She was a Best Paper Award Finalist at the 6th
ACM/IEEE International Conference on Cyber-Physical Systems in 2015.

Shuo Han (S’08-M’14) received the B.E. and M.E.
degrees in Electronic Engineering from Tsinghua
University, Beijing, China in 2003 and 2006, and
the Ph.D. degree in Electrical Engineering from the
California Institute of Technology, Pasadena, USA in
2013. He is currently a postdoctoral researcher in the
Department of Electrical and Systems Engineering at
the University of Pennsylvania. His current research
interests include control theory, convex optimization,
applied probability, and their applications in largescale interconnected systems.

Dr. Shan Lin is an assistant professor of the
Electrical and Computer Engineering Department at
Stony Brook University. He received his PhD in
computer science at the University of Virginia in
2010. His PhD dissertation is on Taming Networking
Challenges with Feedback Control. His research is
in the area of networked systems, with an emphasis
on feedback control based design for cyber-physical
systems and sensor systems. He works on wireless
network protocols, interoperable medical devices,
smart transportation systems, and intelligent sensing
systems.

Professor John A. Stankovic is the BP America
Professor in the Computer Science Department at
the University of Virginia. He is a Fellow of both
the IEEE and the ACM. He has been awarded an
Honorary Doctorate from the University of York.
He won the IEEE Real-Time Systems Technical
Committee’s Award for Outstanding Technical Contributions and Leadership. He also won the IEEE
Technical Committee on Distributed Processing’s
Distinguished Achievement Award. He has seven
Best Paper awards, including one for ACM SenSys
2006. Stankovic has an h-index of 105 and over 40,000 citations. Prof.
Stankovic received his PhD from Brown University.

Desheng Zhang is a Research Associate at Department of Computer Science and Engineering of the
University of Minnesota. Previously, he was awarded
his Ph.D in Computer Science from University of
Minnesota. His research includes big data analytics, mobile cyber physical systems, wireless sensor
networks, and intelligent transportation systems. His
research results are uniquely built upon large-scale
urban data from cross-domain urban systems, including cellphone, smartcard, taxi, bus, truck, subway,
bike, personal vehicle, electric vehicle, and road
networks. Desheng designs and implements large-scale data-driven models
and real-world services to address urban sustainability challenges.

Sirajum Munir received his PhD in Computer
Science from the University of Virginia in 2014.
He is currently working at Bosch Research and
Technology Center as a Research Scientist. His
research interest lies in the areas of cyber-physical
systems, wireless sensor and actuator networks, and
ubiquitous computing. He has published papers in
major conferences in these areas, two of which
were nominated for best paper awards at ACM/IEEE
ICCPS.

Hua Huang received the BE degree from Huazhong
University of Science and Technology in 2012, MS
degree in Temple University in 2014. He is currently
working towards the PhD degree in the Department
of Electrical and Computer Engineering in the Stony
Brook University. His research interests include activity recognition in wearable devices and smart
building, device-free indoor localization, deployment
and scheduling in wireless sensor networks.

Dr. Tian He is currently an associate professor in the
Department of Computer Science and Engineering
at the University of Minnesota-Twin City. Dr. He
is the author and co-author of over 200 papers in
premier network journals and conferences with over
17,000 citations (H-Index 52). Dr. He is the recipient
of the NSF CAREER Award, George W. Taylor
Distinguished Research Award and McKnight LandGrant Professorship, and many best paper awards
in networking. His research includes wireless sensor
networks, cyber-physical systems, intelligent transportation systems, real-time embedded systems and distributed systems.

George J. Pappas (S’90-M’91-SM’04-F’09) received the Ph.D. degree in electrical engineering
and computer sciences from the University of California, Berkeley, CA, USA, in 1998. He is currently the Joseph Moore Professor and Chair of the
Department of Electrical and Systems Engineering,
University of Pennsylvania, Philadelphia, PA, USA.
He also holds a secondary appointment with the
Department of Computer and Information Sciences
and the Department of Mechanical Engineering and
Applied Mechanics. He is a Member of the GRASP
Lab and the PRECISE Center. He had previously served as the Deputy
Dean for Research with the School of Engineering and Applied Science. His
research interests include control theory and, in particular, hybrid systems,
embedded systems, cyber-physical systems, and hierarchical and distributed
control systems, with applications to unmanned aerial vehicles, distributed
robotics, green buildings, and bimolecular networks. Dr. Pappas has received
various awards, such as the Antonio Ruberti Young Researcher Prize, the
George S. Axelby Award, the Hugo Schuck Best Paper Award, the George
H. Heilmeier Award, the National Science Foundation PECASE award and
numerous best student papers awards at ACC, CDC, and ICCPS.

