An economic approach to vehicle dispatching for ride sharing
Mengjing Chen, Weiran Shen, Pingzhong Tang, and Song Zuo
IIIS, Tsinghua University ∗

arXiv:1707.01625v2 [] 1 Mar 2018

March 2, 2018
Abstract
Over the past few years, ride-sharing has emerged as an effective way to relieve traffic congestion. A key problem
for these platforms is to come up with a revenue-optimal (or GMV-optimal) pricing scheme and an induced vehicle
dispatching policy that incorporate geographic and temporal information. In this paper, we aim to tackle this problem
via an economic approach.
Modeled naively, the underlying optimization problem may be non-convex and thus hard to compute. To this
end, we use a so-called “ironing” technique to convert the problem into an equivalent convex optimization one via a
clean Markov decision process (MDP) formulation, where the states are the driver distributions and the decision
variables are the prices for each pair of locations. Our main finding is an efficient algorithm that computes the exact
revenue-optimal (or GMV-optimal) randomized pricing schemes. We characterize the optimal solution of the MDP
by a primal-dual analysis of a corresponding convex program. We also conduct empirical evaluations of our solution
through real data of a major ride-sharing platform and show its advantages over fixed pricing schemes as well as
several prevalent surge-based pricing schemes.

1

Introduction

The recently established applications of shared mobility, such as ride-sharing, bike-sharing, and car-sharing, have been
proven to be an effective way to utilize redundant transportation resources and to optimize social efficiency (Cramer
and Krueger, 2016). Over the past few years, intensive researches have been done on topics related to the economic
aspects of shared mobility (Crawford and Meng, 2011; Kostiuk, 1990; Oettinger, 1999).
Despite these researches, the problem of how to design revenue optimal prices and vehicle dispatching schemes
has been largely open and one of the main research agendas in sharing economics. There are at least two challenges
when one wants to tackle this problem in the real-world applications. First of all, due to the nature of transportation,
the price and dispatch scheme must be geographically dependent. Secondly, the price and dispatch scheme must take
into consideration the fact that supplies and demands in these environments may change over time. As a result, it
may be difficult to compute, or even to represent a price and dispatch scheme for such complex environments.
Traditional price and dispatch schemes for taxis (Laporte, 1992; Gendreau et al., 1994; Ghiani et al., 2003) and
airplanes (Gale and Holmes, 1993; Stavins, 2001; McAfee and Te Velde, 2006) do not capture the dynamic aspects of
the environments: taxi fees are normally calculated by a fixed rate of distance and time and the prices of flight tickets
are sold via relatively long booking periods, while in contrast, the customers of shared vehicles make their decisions
instantly.
The dynamic ride-sharing market studied in this paper is also known to have imbalanced supply and demand,
either globally in a city or locally in a particular time and location. Such imbalance in supply and demand is known to
cause severe consequences on revenues (e.g, the so-called wild goose chase phenomenon (Castillo et al., 2017)). Surging
price is a way to balance dynamic supply and demand (Chen and Sheldon, 2015) but there is no known guarantee that
surge based pricing can dispatch vehicles efficiently and solve the imbalanced supplies and demands. Traditional
dispatch schemes (Laporte, 1992; Gendreau et al., 1994; Ghiani et al., 2003) focus more on the algorithmic aspect of
static vehicle routing, without consider pricing. However, vehicle dispatching and pricing problem are tightly related,
since a new price scheme will surely induces a change on supply and demand since the drivers and passengers are
strategic. In this paper, we aim to come up with price schemes with desirable induced supplies and demands.
∗ Contacts:

ccchmj@qq.com, {emersonswr, kenshinping, songzuo.z}@gmail.com

1

1.1

Our contribution

In this paper, we propose a graph model to analyze the vehicle pricing and dispatching problem mentioned above. In
the graph, each node refers to a region in the city and each edge refers to a possible trip that includes a pair of origin
and destination as well as a cost associated with the trip on this edge. The design problem is, for the platform, to set a
price and specify the vehicle dispatch for each edge at each time step. Drivers are considered to be non-strategic in
our model, meaning that they will accept whatever offer assigned to them. The objective of the platform can either be
its revenue or the GMV or any convex combination between them.
Our model naturally induces a Markov Decision Process (MDP) with the driver distributions on each node as
states, the price and dispatch along each edge as actions, and the revenue as immediately reward. Although the
corresponding mathematical program is not convex (thus computationally hard to compute) in general, we show that
it can be reduced to a convex one without loss of generality. In particular, in the resulting convex program where the
throughput along each source and destination pair in each time period are the variables, all the constraints are linear
and hence the exact optimal solutions can be efficiently computed (Theorem 3.1).
We further characterize the optimal solution via primal-dual analysis. In particular, a pricing scheme is optimal
if and only if the marginal contribution of the throughput along each edge equals to the system-wise marginal
contribution of additional supply minus the difference of the long term contributions of unit supply at the origin and
the destination (see Section 5).
We also perform extensive empirical analysis based on a public dataset with more than 8.5 million orders. We
compare our policy with other intensively studied policies such as surge pricing (Chen and Sheldon, 2015; Cachon
et al., 2016; Castillo et al., 2017). Our simulations show that, in both the static and the dynamic environment, our
optimal pricing and dispatching scheme outperforms surge pricing by 17% and 33%. Interestingly, our simulations
show that our optimal policy has much stronger ability in dispatching the vehicles than other policies, which results
directly in its performance boost (see Section 6).

1.2

Related work

Driven by real-life applications, a large number of researches have been done on ride-share markets. Some of them
employ queuing networks to model the markets (Iglesias et al., 2016; Banerjee et al., 2015; Tang et al., 2016). Iglesias
et al. (2016) describe the market as a closed, multi-class BCMP queuing network which captures the randomness of
customer arrivals. They assume that the number of customers is fixed, since customers only change their locations
but don’t leave the network. In contrast, the number of customer are dynamic in our model and we only consider
the one who asks for a ride (or sends a request to the platform). Banerjee et al. (2015) also use a queuing theoretic
approach to analyze the ride-share markets and mainly focus on the behaviors of drivers and customers. They assume
that the drivers enter or leave the market with certain possibilities. Bimpikis et al. (2016) take account for the spatial
dimension of pricing schemes in ride-share markets. They price for each region and their goal is to rebalance the
supply and demand of the whole market. However, we price for each routing and aim to maximize the total revenue
or social welfare of the platform. We also refer the readers to the line of researches initiated by (Ma et al., 2013) for
the problems about the car-pooling in the ride-sharing systems (Alonso-Mora et al., 2017; Zhao et al., 2014; Chan and
Shaheen, 2012).
Many works on ride-sharing consider both the customers and the drivers to be strategic, where the drivers
may reject the requests or leave the system if the prices are too low (Banerjee et al., 2015; Fang et al., 2017). As we
mentioned, if the revenue sharing ratios between the platform and the drivers can be dynamic, then the pricing
problem and the revenue sharing problem could be independent and hence the drivers are non-strategic in the pricing
problem. In addition, the platform can also increase the profit by adopting dynamic revenue sharing schemes (Balseiro
et al., 2017).
Another work closely related to ours is by Banerjee et al. (2017). Their work is concurrent and has been developed
independently from ours. In particular, the customers arrive according to a queuing model and their pricing policy is
state-independent and depends on the transition volume. Both their and our models are built upon the underlying
Markovian transitions between the states (the distribution of drivers over the graph). The major differences are: (i) our
model is built for the dynamic environments with a very large number of customers (each of them is non-atomic) to
meet the practical situations, while theirs adopts discrete agent settings; (ii) they overcome the non-convexity of the
problem by relaxation and focus only on concave objectives, which makes this work hard to use for real applications,
while we solve the problem via randomized pricing and transform the problem to a convex program; (iii) they prove

2

approximation bounds of the relaxation problem, while we give exact optimal solutions of the problem by efficiently
solving the convex program.

2

Model

A passenger (she) enters the ride-sharing platform and sends a request including her origin and destination to the
platform. The platform receives the request and determines a price for it. If user accepts the price, then the platform
may decide whether to send a driver (he) to pick her up. The platform is also able to dispatch drivers from one place to
another even there is no request to be served. By the pricing and dispatching methods above, the goal of maximizing
revenue or social welfare of the entire platform can be achieved. Our model incorporates the two methods into a
simple pricing problem. In this section, we define basic components of our model and consider two settings: dynamic
environments with a finite time horizon and static environments with an infinite time horizon. Finally we reduce the
action space of the problem and give a simple formulation.
Requests We use a strongly connected digraph G = (V, E) to model the geographical information of a city.
Passengers can only take rides from nodes to nodes on the graph. When a passenger enters the platform, she expects
to get a ride from node s to node t, and is willing to pay at most x ≥ 0 for the ride. She then sends to the platform a
request, which is associated with the tuple e = (s, t). Upon receiving the request, The platform sets a price p for it. If
the price is accepted by the passenger (i.e., x ≥ p), then the platform tries to send a driver to pick her up. We say that
the platform rejects the request, if no driver is available.
A request is said to be accepted if both the passenger accepts the price p and there are available drivers. Otherwise,
the request is considered to end immediately.
Drivers Clearly, within each time period, the total number of accepted requests starting from s cannot be more
than the number of drivers available at s. Formally, let q(e) denote the total number of accepted request along edge e,
then:
Õ
q(e) ≤ w(v), ∀v ∈ V,
(2.1)
e∈OUT(v)

where OUT(v) is the set of edges starting from v and w(v) is the number of currently available drivers at node v.
In particular, we assume that both the total number of drivers and the number of requests are very large, which is
often the case in practice, and consider each driver and each request to be non-atomic. For simplicity, we normalize
the total amount of drivers on the graph to be 1, thus w(v) is a real number in [0, 1]. We also normalize the number of
requests on each edge with the total number of drivers. Note that the amount of requests on an edge e can be more
than 1, if there are more requests on e than the total drivers on the graph.
Geographic Status For each accepted request on edge e, the platform will have to cover a transportation cost cτ (e)
for the driver. In the meanwhile, the assigned driver, who currently at node s, will not be available until he arrives
the destination t. Let ∆τ(e) be the traveling time from s to t and τ be the timestep of the driver leaving s. He will be
available again at timestep τ + ∆τ(e) on node t. Formally, the amount of available drivers on any v ∈ V is evolving
according to the following equations:
Õ
Õ
wτ+1 (v) = wτ (v) −
qτ (e) +
qτ+1−∆τ(e) (e),
(2.2)
e ∈OUT(v)

e∈IN(v)

where IN(v) is the set of edges ending at v. Here we add subscripts to emphasize the timestamp for each quantity. In
particular, throughout this paper, we focus on the discrete time step setting, i.e., τ ∈ N.
Demand Function As we mentioned, the platform could set different prices for the requests. Such prices may
vary with the request edge e, time step t, and the driver distribution but must be independent of the passenger’s
private value x as it is not observable. Formally, let Dτ (·|e) : R+ → R+ be the demand function of edge e, i.e., Dτ (p|e)
is the amount of requests on edge e with private value x ≥ p in time step τ.1 Then the amount of accepted requests
qτ (e) ≤ E[Dτ (pτ (e)|e)], where the expectation is taken over the potential randomness of the pricing rule pτ (e).2
1 In

practice, such a demand function can be predicted from historical data Tong et al. (2017); Moreira-Matias et al. (2013).
randomized pricing rule may set different prices for the requests on the same edge e.

2 The

3

Design Objectives In this paper, we consider a class of state-irrelevant objective functions. A function is stateirrelevant if its value only depends on the amount of accepted request on each edge q(e) but not the driver distribution
of the system w(v). Note that a wide range of objectives are included in our class of objectives, such as the revenue of
the platform:
Õ
REVENUE(p, q) =
E[(pτ (e) − cτ (e)) · qτ (e)],
e,τ

and the social welfare of the entire system:
WELFARE(p, q) =

Õ

E[(x − cτ (e)) · qτ (e)].

e,τ

In general, our techniques work for any state-irrelevant objectives. Let g(p, q) denote the general objective
function and the dispatching and pricing problem can be formulated as follows:
Õ
maximize
g(pτ (e), qτ (e)|e)
(2.3)
e,τ

subject to

(2.1) and (2.2).

Static and Dynamic Environment In general, our model is defined for a dynamic environment in the sense that
the demand function Dτ and the transportation cost cτ could be different for each time step τ. In particular, we study
the problem (2.3) in general dynamic environments with finite time horizon from τ = 1 to T, where the initial driver
distribution w1 (v) is given as input.
In addition, we also study the special case with static environment and infinite time horizon, where Dτ ≡ D and
cτ ≡ c are consistent across each time step.

2.1

Reducing the action space

In this section, we rewrite the problem to an equivalent reduced form by incorporating the action of dispatching
into pricing, i.e., using p to express q. The idea is straightforward: (i) for the requests rejected by the platform, the
platform could equivalently set an infinitely large price; (ii) if the platform is dispatching available drivers (without
requests) from node s to t, we can create virtual requests from s to t with 0 value and let the platform sets price 0 for
these virtual requests. In fact, we can assume without loss of generality that D(0|e) ≡ 1, the total amount of drivers,
because one can always add enough virtual requests for the edges with maximum demand less than 1 or remove the
requests with low values for the edges with maximum demand exceeds the total driver supply, 1.
As a result, we may conclude that q(e) ≤ D(p|e). Since our goal is to maximize the objective g(p, q), raising prices
to achieve the same amount of flow q(e) (such that E[D(p|e)] = q(e)) never eliminates the optimal solution. In other
words,
Observation 2.1. The original problem is equivalent to the following reduced problem, where the flow variables qτ (e)
are uniquely determined by the price variables pτ (e):
Õ
maximize
g(pτ (e), Dτ (pτ (e)|e))
e,τ

subject to

qτ (e) = E[D(pτ (e)|e)]

(2.4)

(2.1) and (2.2).

3

Problem Analysis

In this section, we demonstrate how the original problem (2.4) can be equivalently rewritten as a Markov decision
process with a convex objective function. Formally,
Theorem 3.1. The original problem (2.4) of the instance hG, D, g, ∆τi is equivalent to a Markov decision process problem
of another instance hG 0, D 0, g 0, ∆τ 0i with g 0 being convex.
The proof of Theorem 3.1 will be immediate after Lemma 3.2 and 3.4. The equivalent Markov decision process
problem could be formulated as a convex program, and hence can be solved efficiently.
4

3.1

Unifying travel time

Note that the original problem (2.4), in general, is not a MDP by itself, because the current state wτ+1 (v) may depend
on the action qτ+1−∆τ(e) in (2.2). Hence our first step is to equivalently map the original instance to another instance
with traveling time is always 1, i.e., ∆τ(e) ≡ 1:
Lemma 3.2 (Unifying travel time). The original problem (2.4) of an general instance hG, D, g, ∆τi is equivalent to the
problem of a 1-travel time instance hG 0, D 0, g 0, ∆τ 0i, where ∆τ 0(·) ≡ 1.
Intuitively, we tackle this problem by adding virtual nodes into the graph to replace the original edges. This
operation splits the entire trip into smaller ones, and at each time step, all drivers become available.
Proof. For edges with traveling time ∆τ(e) = 1, we are done.
e
For edges with traveling time ∆τ(e) > 1, we add ∆τ(e) − 1 virtual nodes into the graph, i.e., v1e, . . . , v∆τ(e)−1
, and
the directed edges connecting them to replace the original edge e, i.e.,
e
e
e
E 0(e) = {(s, v1e ), (v1e, v2e ), . . . , (v∆τ(e)−2
, v∆τ(e)−1
), (v∆τ(e)−1
, t)},
Ø
Ø
e
E0 =
E 0(e), V 0 =
{v1e, . . . , v∆τ(e)−1
} ∪ V.
e ∈E

e ∈E

We set the demand function of each new edge e 0 ∈ E 0(e) to be identical to those of the original edge e: D 0(·|e 0) ≡ D(·|e).
An important but natural constraint is that if a driver handles a request on edge e of the original graph, then he
must go along all edges in E 0(e) of the new graph, because he cannot leave the passenger halfway. To guarantee this,
we only need to guarantee that all edges in E 0(e) have the same price. Also, we need to split the objective of traveling
along e into the new edges, i.e., each new edge has objective function
g 0(p, q|e 0) = g(p, q|e)/∆τ(e), ∀e 0 ∈ E 0(e).
One can easily verify that the above operations increase the graph size to at most maxe ∈E ∆τ(e)∗ times of that of
the original one. In particular, there is a straightforward bijection between the dispatching behaviors of the original
G = (V, E) and the new graph G 0 = (V 0, E 0). Hence we can always recover the solution to the original problem.

3.2

Flow formulation and randomized pricing

By Lemma 3.2, the original problem (2.4) can be formulated as an MDP:
Definition 3.3 (Markov Decision Process). The vehicle pricing and dispatching problem is a Markov decision process,
denoted by a tuple (G, D, g, S, A, W), where G = (V, E) is the given graph, D is the demand function, objective g is the
reward function, S = ∆(V) is the state space including all possible driver distributions over the nodes, A is the action
space, and W is the state transition rule:
Õ
Õ
wτ+1 (v) = wτ (v) −
qτ (e) +
qτ (e).
(3.1)
e∈OUT(v)

e ∈IN(v)

However, by naïvely using the pricing functions pτ (e) as the actions, the induced flow qτ (e) = E[Dτ (pτ (e)|e)],
in general, is neither convex nor concave. In other words, both the reward g and the state transition W of the
corresponding MDP is non-convex. As a result, it is hard to solve the MDP efficiently.
In this section, we show that by formulating the MDP with the flows qτ (e) as actions, the corresponding MDP is
convex.
Lemma 3.4 (Flow-based MDP). In the MDP (G, D, g, S, A, W) with all possible flows as the action set A, i.e., A = [0, 1] |E | ,
the state transition rules are linear functions of the flows and the reward functions g are convex functions of the flows.
Proof. To do this, we first need to rewrite the prices pτ (e) as functions of the flows qτ (e). In general, since the prices
could be randomized, the inverse function of qτ (e) = E[Dτ (pτ (e)|e)] is not unique.

5

Note that conditional on fixed flows qτ (e), the state transition of the MDP is also fixed. In this case, different
prices yielding such specific flows only differs in the rewards. In other words, it is without loss of generality to let the
inverse function of prices be as follows:
pτ (e) = arg max gτ (pτ (e), qτ (e)|e), s.t. qτ (e) = E[Dτ (pτ (e)|e)].
p

In particular, since the objective function g we studied in this paper is linear and weakly increasing in the prices
p and the demand function D(p|e) is decreasing in p, the inversed price function could be defined as follows:
• Let gτ (q|e) = gτ (Dτ−1 (q|e), q|e), i.e., the objective obtained by setting the maximum fixed price p = Dτ−1 (q|e)
such that the induced flow is exactly q;
• Let ĝτ (q|e) be the ironed objective function, i.e., the smallest concave function that upper-bounds gτ (q|e) (see
Figure 1);
• For any given qτ (e), the maximum objective on edge e is ĝτ (qτ (e)|e) and could be achieve by setting the price
to be randomized over Dτ−1 (q 0 |e) and Dτ−1 (q 00 |e).

Figure 1: Ironed objective function
Finally, we prove the above claim to complete the proof of Lemma 3.4.
By the definition of ĝτ (q|e), for any randomized price p,
E[gτ (Dτ (p|e)|e)] ≤ E[ĝτ (Dτ (p|e)|e)].
p

p

Since ĝ is concave, applying Jensen’s inequality yields:




E[ĝτ (Dτ (p|e)|e)] ≤ ĝτ E[Dτ (p|e)] e = ĝτ (q̄|e)
p

p

Now it suffices to show that the upper bound ĝτ (q̄|e) is attainable.
If ĝτ (q̄|e) = gτ (q̄|e), then the right-hand-side could be achieved by letting pτ (e) be the deterministic price
Dτ−1 (q̄|e).
Otherwise, let I = (q 0, q 00) be the ironed interval (where ĝτ (q|e) > gτ (q|e), ∀q ∈ I but ĝτ (q 0 |e) = gτ (q 0 |e) and
ĝτ (q 00 |e) = gτ (q 00 |e)) containing q̄. Thus q̄ can be written as a convex combination of the end points q 0 and q 00:
q̄ = λq 0 + (1 − λ)q 00. Note that the function ĝτ is linear within the interval I. Therefore
λgτ (q 0 |e) + (1 − λ)gτ (q 00 |e) = λĝτ (q 0 |e) + (1 − λ)ĝτ (q 00 |e) = ĝτ (λq 0 + (1 − λ)q 00 |e) = ĝτ (q̄|e).
In other words, the upper bound ĝτ (q̄|e) could be achieved by setting the price to be q 0 with probability λ and q 00
with probability 1 − λ. In the meanwhile, the flow qτ (e) would retain the same.
Proof of Theorem 3.1. The theorem is implied by Lemma 3.2 and Lemma 3.4. In particular, the reward function is the
ironed objective function ĝ.
In the rest of the paper, we will focus on the following equivalent problem:
Õ
maximize
ĝτ (qτ (e)|e)
e,τ

subject to

(2.1) and (3.1).
6

(3.2)

4

Optimal Solution in Static Environment

In this setting, we restrict our attention to the case where the environment is static, hence the objective function does
not change over time, i.e., ∀τ ∈ [T], ĝτ (q|e) ≡ ĝ(q|e). We aim to find the optimal stationary policy that maximizes the
objective function, i.e., the decisions qτ depends only on the current state wτ .
In this section, we discretize the MDP problem and focus on stable policies. With the introduction of the ironed
objective function ĝτ , we show that for any discretization scheme, the optimal stationary policy of the induced
discretized MDP is dominated by a stable dispatching scheme. Then we formulate the stable dispatching scheme as a
convex problem, which means the optimal stationary policy can be found in polynomial time.
Definition 4.1. A stable dispatching scheme is a pair of state and policy (wτ , π), such that if policy π is applied, the
distribution of available drivers does not change over time, i.e., wτ+1 (v) = wτ (v).
In particular, under a stable dispatching scheme, the state transition rule (3.1) is equivalent to the following form:
Õ
Õ
q(e) =
q(e).
(4.1)
e ∈OUT(v)

e ∈IN(v)

Definition 4.2. Let M = (G, D, ĝ, S, A, W) be the original MDP problem. A discretized MDP DM with respect to M is
a tuple (G d, Dd, ĝd, Sd, Ad, Wd ), where G d = G, Dd = D, ĝd = ĝ, Wd = W, Sd is a finite subset of S, and Ad is a finite
subset of A that contains all feasible transition flows between every two states in Sd .
Theorem 4.3. Let DM and M be a discretized MDP and the corresponding original MDP. Let πd : Sd → Ad be an
optimal stationary policy of DM. Then there exists a stable dispatching scheme (w, π), such that the time-average
objective of π in M is no less than that of πd in DM.
Proof. Consider policy πd in DM. Starting from any state in Sd with policy πd , let {wτ }0∞ be the subsequent state
sequence. Since DM has finitely many states and policy πd is a stationary policy, there must be an integer n, such
that wn = wm for some m < n and from time step m on, the state sequence become a periodic sequence. Define
w̄ =

n−1
1 Õ
wk ,
n − m k=m

q̄ =

n−1
1 Õ
πd (wk )
n − m k=m

Denote by πd (wk |e) or qd (e) the flow at edge e of the decision πd (wk ). Sum the transition equations for all the time
steps m ≤ k < n, and we get:
n−1
Õ

wk+1 (v) −

k=m

n−1
Õ
k=m

wk (v) =

n−1 Õ
n−1
Õ
©
ª Õ© Õ
ª
πd (wk |e)® −
πd (wk |e)®
­
­
k=m «IN(v)
¬ k=m «OUT(v)
¬

© Õ
ª ©Õ
ª
w̄(v) = w̄(v) − ­
q̄(e)® + ­
q̄(e)®
«OUT(v)
¬ «IN(v)
¬
Also, policy πd is a valid policy, so ∀v ∈ V and ∀m ≤ k < n:
Õ
qk (e) ≤ wk (v)
OUT(v)

Summing over k, we have:
Õ

q̄(e) ≤ w̄(v)

OUT(v)

Now consider the original problem M. Let w = w̄ and π be any stationary policy such that:
• π(w) = q̄;
7

• starting from any state w 0 , w, policy π leads to state w within finitely many steps.
Note that the second condition can be easily satisfied since the graph G is strongly connected.
With the above definitions, we know that (w, π) is a stable dispatching scheme. Now we compare the objectives of
the two policies πd and π. The time-average objective function is not sensitive about the first finitely many immediate
objectives. And since the state sequences of both policies πd and π are periodic, Their time-average objectives can be
written as:
n−1
1 ÕÕ
ĝ(qd (e)|e)
n − m k=m e ∈E
Õ
OBJ(π) =
ĝ(q̄(e)|e)

OBJ(πd ) =

e ∈E

By Jensen’s inequality, we have:
n−1
Õ
1 ÕÕ
OBJ(πd ) =
ĝ(qd (e)|e) ≤
ĝ
n − m k=m e∈E
e∈E

"

! #
n
Õ
1 Õ
ĝ(q̄(e)|e) = OBJ(π)
qd (e) e =
n − m k=m
e ∈E

With Theorem 4.3, we know there exists a stable dispatching scheme that dominates the optimal stationary policy
of the our discretized MDP. Thus we now only focus on stable dispatching schemes. The problem of finding an
optimal stable dispatching scheme can be formulated as a convex program with linear constraints:
Õ
maximize
ĝ(q|e)
e∈E
(4.2)
subject to (2.1) and (4.1).
Because ĝ(q|e) is concave, the program is convex. Since all convex programs can be solved in polynomial time,
our algorithm for finding optimal stationary policy of maximizing the objective functions is efficient.

5

Characterization of optimality

In this section, we characterize the optimal solution via dual analysis. For the ease of presentation, we consider
Program 4.2 in the static environment with infinite horizon. Our characterization directly extends to the dynamic
environment.
The Lagrangian is defined to be
!
Õ
Õ
Õ © Õ
Õ
ª
L(q, λ, µ) = −
ĝ(q|e) + λ
q(e) − 1 +
µv ­
q(e) −
q(e)®
e ∈E
e∈E
v ∈V
IN(v)
«OUT(v)
¬
Õ
=−λ+
[−ĝ(q|e) + (λ + µs − µt )q(e)] ,
e ∈E

where s and t are the origin and destination of e, i.e., e = (s, t), and λ and µ are Lagrangian multipliers
Í with λ ≥ 0.
Note that we implicitly transform program 4.2 to the standard form that minimizes the objective − e∈E ĝ(q∗ |e).
The Lagrangian dual function is
Õ
h(λ, µ) = inf L(q, λ, µ) =
[−ĝ(q̃|e) + (λ + µs − µt )q̃(e)] ,
q

e ∈E

where q̃(e) is a function of λ and µ such that λ + µs − µt = ĝ 0(q̃|e), where ĝ 0(q̃|e) is the derivative of the objective
function with respect to flow q. The dual program corresponding to Program 4.2 is
maximize

h(λ, µ)

subject to

λ≥0

According to the KKT conditions, we have the following characterization for optimal solutions.
8

(5.1)

∗ ∗
Theorem 5.1. Let q∗ (e) be a feasible solution to the primal program 4.2 and (λ
to the dual
Í , µ ) be∗a feasible ∗solution
∗
∗
∗
program 5.1. Then both q (e) and (λ , µ ) are primal and dual optimal with − e∈E ĝ(q |e) = h(λ , µ∗ ), if and only if
!
Õ
λ∗
q∗ (e) − 1 = 0
(5.2)
e∈E

ĝ (q |e) = λ∗ + µ∗s − µ∗t , ∀v ∈ V
0

∗

(5.3)

Proof. According to the definition of h(λ, µ), we have h(λ∗, µ∗ ) = inf q L(q, λ∗, µ∗ ). Since ĝ(q|e) are concave functions,
Equation 5.3 is equivalent to the fact that q∗ (e) minimizes the function L(q, λ∗, µ∗ ).
h(λ∗, µ∗ ) = inf L(q, λ∗, µ∗ )
q

=L(q∗, λ∗, µ∗ )
!
=−

Õ

ĝ(q |e) + λ
∗

e ∈E

=−

Õ

∗

Õ

q (e) − 1 +
∗

Õ
v ∈V

e∈E
∗

Õ
© Õ ∗
ª
µ∗v ­
q (e) −
q∗ (e)®
IN(v)
«OUT(v)
¬

ĝ(q |e),

e∈E

where the last equation uses the Equation 5.2 and the fact that q∗ (e) is feasible.
Continuing with Theorem 5.1, we will analyze the dual variables from the economics angle and some interesting
insights into this problem for real applications.

5.1

Economic interpretation

The dual variables have useful economic interpretations (see (Boyd and Vandenberghe, 2004, Chapter 5.6)). λ∗ is the
system-wise marginal contribution of the drivers (i.e. the increase in the objective function when a small amount of
drivers are added to the system). Note that by the complementary slackness (Equation 5.2), if λ∗ > 0, the sum of the
total flow must be 1, meaning that all drivers are busy, and more requests can be accepted (hence increase revenue) if
more drivers are added to the system. Otherwise, there must be some idle drivers, and adding more drivers cannot
increase the revenue.
µ∗v is the marginal contribution of the drivers at node v. If we allow the outgoing flow from node v to be slightly
more than the incoming flow to node v, then µv is the revenue gain from adding more drivers at node v.

5.2

Insights for applications

The way we formulate and solve the problem, in fact, naturally leads to two interesting insights into this problem,
which are potentially useful for real applications.
1. Scalability In our model, the size of the convex program increases linearly in the number of edges, hence
quadratically in the number of regions. This could be one hidden feature that is potentially an obstacle to real
applications, where the number of regions in a city might be quite large.
A key observation to the issue is that any dispatching policy induced by a real system is a feasible solution of our
convex program and any improvement (maybe via gradient descent) from such policy in fact leads to a better solution
for this system. In other words, it might be hard to find the exact optimal or nearly optimal solutions, but it is easy to
improve from the current state. Therefore, in practice, the platform can keep running the optimization in background
and apply the most recent policy to gain more revenue (or achieve a higher value of some other objectives).
2. Alternative solution As suggested by the characterization and its economic interpretation, instead of solving the
convex programs directly, we also have an alternative way to find the optimal policy by solving the dual program.
The optimal policy can be easily recovered from dual optimal solutions. In particular, according to the economic
interpretation of dual variables, we need to estimate the marginal contributions of drivers.
More importantly, the number of dual variables (= the number of regions) is much smaller than the number of
primal variables (= the number of edges ≈ square of the former). So solving the dual program may be more efficient
when applied to real systems, and is also of independent interest of this paper.
9

6

Empirical Analysis

We design experiments to demonstrate the good performance of our algorithms for real applications. In this section,
we first describe the dataset and then introduce how to extract useful information for our model from the dataset.
Two benchmark policies, FIXED and SURGE, are compared with our pricing policy. The result analysis includes
demand-supply balance and instantaneous revenue in both static and dynamic environments.

6.1

Dataset

We perform our empirical analysis based on a public dataset from a major ride-sharing company. The dataset includes
the orders in a city for three consecutive weeks and the total number of orders is more than 8.5 million. An order is
created when a passenger send a ride request to the platform.
Each order consists of a unique order ID, a passenger ID, a driver ID, an origin, a destination, and an estimated
price, and the timestamp when the order is created (see Table 1 for example). The driver ID might be empty if no
driver was assigned to pick up the passenger. There are 66 major regions of the city and the origins and destinations
in the dataset are given as the region IDs. We say a request is related to a region if the region is either the origin or
the destination of the request. And the popularity of a region is defined as the number of related requests. Since some
of the regions in the dataset have very low popularity values, we only consider the most popular 21 or 5 regions in
the two settings (see Section 6.4 and Section 6.5 respectively for details). The related requests of the most popular 21
(or 5) regions cover about 90% (or 50%) of the total requests in the original dataset.
For ease of presentation, we relabel the region IDs in descending order of their popularities (so region #1 is the
most popular region). Figure 2 illustrates the frequencies of requests on different origin-destination pairs. From the
figure, one can see that the frequency matrix is almost symmetric and the destination of a request is most likely to be
in the same region as the origin.
order
hash

driver
hash

user
hash

origin
hash

dest
hash

price
37.5

timestamp
01-15 00:35:11

Table 1: An example of a row in the dataset, where “hash” stands for some hash strings of the IDs that we didn’t show
the exact value here.

Heatmap of Routes
Log Frequency

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

12.5

Origin IDs

10.0

7.5

5.0

2.5

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

0.0

Destination IDs

Figure 2: The logarithmic frequencies of request routes.

6.2

Data preparation

The time consumptions from nodes to nodes and demand curves for edges are known in our model. However, the
dataset doesn’t provide such information directly. We filter out "abnormal" requests and apply a linear regression to
10

Log Frequency

8

6

30

0

0

8

6

4

2

0

15

2

15

30

4

Time & Price Filtered
Log Frequency

Time
in Mins
45 60 75 90 105 120 135 150

Time
in Mins
45 60 75 90 105 120 135 150

Time & Price

0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80

0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80

Price in Local Currency

0

Price in Local Currency

(a) Time & price without filtering

(b) Time & price with filtering

Figure 3: The logarithmic frequencies of (time, price) pairs, with or without filtering the “abnormal” requests.

0

Density

Request value from region 6 to 2

Density

Request value from region 9 to 11

5

10

15

Value

20

25

0

5

10

15

20

Value

25

30

Figure 4: Fitting request values to lognormal distributions.
get the relationship of the travel time and the price. It makes possible to infer the travel time from the order price.
For the demand curves, we observe the values of each edge and fit them to lognormal distributions.
Distance and travel time The distance (or equivalently the travel time) from one region to another is required to
perform our simulation. We approximate the travel time by the time interval of two consecutive requests assigned to
the same driver. In Figure 3(a), we plot the frequencies of requests with certain (time, price) pairs. We cannot see
clear relationship between time and price, which are supposed to be roughly linearly related in this figure.3 We think
that this is due to the existence of two types of “abnormal” requests:
• Cancelled requests, usually with very short completion time but not necessarily low prices (appeared in the
right-bottom part of the plot);
• The last request of a working period, after which the driver might go home or have a rest. These requests usually
have very long completion time but not necessarily high enough prices (appeared in the left-top part of the
plot).
With the observations above, we filter out the requests with significantly longer or shorter travel time compared
with most of the requests with the same origin and destination. Figure 3(b) illustrates the frequencies of requests
after such filtering. As expected, the brightest region roughly surrounds the 30◦ line in the figure. By applying a
standard linear regression, the slope turns out to be approximately 0.5117 CNY per minute. One may also notice
some “right-shifting shadows” of the brightest region, which are caused by the surge-pricing policy with different
multipliers.
3 The price of a ride is the maximum of a two-dimension linear function of the traveled distance and spent time and a minimal price (which is 7
CNY as one can see the vertical bright line at price = 7 in Figure 3). Since the traveled distance is almost linearly related to the spent time, the
price, if larger than the minimal price, should also be almost linearly related to the traveling time. Readers may notice that from the figures, there
are many requests with price less than 7 (even as low as 0). This is because there are many coupons given to passengers to stimulate their demand
for riding and the prices given in the dataset are after applying the coupons.

11

Revenue per Minute

Revenue per Minute

1600
1400
1200
1000
800
600
400
200
0

0

20

40

60

80

# of Iterations

100

400

300

200

100

0

120

(a) Static environment

0

100

200

300

400

500

# of Iterations

600

700

800

(b) Dynamic environment

Figure 5: Convergence of revenue.
Estimation of demand curves To estimate the demand curves, we first gather all the requests along the same edge
(also within the same time period for dynamic environment, see Section 6.5) and take the prices associated with the
requests as the values of the passengers. Then, we fit the values of each edge (and each time period for dynamic
environment) to a lognormal distribution. The reason that we choose the lognormal distribution is two-fold: (i) the
data fits lognormal distributions quite well (see Figure 4 as examples); (ii) lognormal distributions are commonly used
in some related literatures Ostrovsky and Schwarz (2011); Lahaie and Pennock (2007); Roberts et al. (2016); Shen and
Tang (2017).
We set the cost of traveling to be zero, because we do not have enough information from the dataset to infer the
cost.

6.3

Benchmarks

We consider two benchmark policies:
• FIXED: fixed per-minute pricing, i.e., the price of a ride equals to the estimated traveling time from the origin
to the destination of this ride multiplied by a per-minute price α, where α is a constant across the platform.
• SURGE: based on FIXED policy, using surge pricing to clear the local market when supply is not enough.
In other words, the price of a ride equals to the estimated traveling time multiplied by αβ, where α is the
fixed per-minute price and β ≥ 1 is the surge multiplier. Note that β is dynamic and can be different for
requests initiated at different regions, while the requests initiated at the same regions will share the same surge
multipliers.
In the rest of this section, we evaluate and compare our dynamic pricing policy DYNAM with these two benchmarks
in both static and dynamic environments.

6.4

Static environment

We first present the empirical analysis for the static environment, which is simpler than the dynamic environment
that we will consider next, hence easier to begin with.
In the static environment, we use the average of the statistics of all 21 days as the inputs to our model. For
example, the demand function D(p|e) is estimated based on the frequencies and prices of the requests along edge
e averaged over time. Similarly, the total supply of drivers is estimated based on the total durations of completed
requests.
With the static environment, we can instantiate the convex program (4.2) and solve via standard gradient descent
algorithms. In our case, we simply use the MATLAB function fmincon to solve the convex program on a PC with
Intel i5-3470 CPU. We did not apply any additional techniques to speed-up the computation as the optimization
of running time is not the main focus of this paper. Figure 5(a) illustrates the convergence of the objective value
(revenue) with increasing number of iterations, where each iteration roughly takes 0.2 second.

12

Dynamic Environment

1550

Revenue per Minute

Revenue per Minute

Static Environment
DYNAM
FIXED
SURGE

1500
1450
1400
1350
1300
1250
1200
0

4

8

12

Hours

16

20

DYNAM
FIXED

1000
800
600
400
200
0

24

SURGE

0

4

(a) Static environment

8

12

16

Hours

20

24

(b) Dynamic environment

Figure 6: Instantaneous revenue in different environments.

300%
200%
100%
0%

500%
400%
300%
200%
100%

0

4

8

12

Hours

16

20

24

0%

500%
400%
300%
200%
100%

0

4

8

12

Hours

16

20

24

0%

600%

4

8

12

Hours

16

20

24

500%
400%
300%
200%

0%

DYNAM
FIXED
SURGE

700%

100%
0

Region #5

800%

DYNAM
FIXED
SURGE

700%

Supply/Demand

400%

600%

Region #4

800%

DYNAM
FIXED
SURGE

700%

Supply/Demand

500%

600%

Region #3

800%

DYNAM
FIXED
SURGE

700%

Supply/Demand

Supply/Demand

600%

Region #2

800%

DYNAM
FIXED
SURGE

700%

Supply/Demand

Region #1

800%

600%
500%
400%
300%
200%
100%

0

4

8

12

Hours

16

20

24

0%

0

4

8

12

Hours

16

20

24

Figure 7: Instantaneous supply ratios for different regions.
To compare the performance of policy DYNAM with the benchmark policies FIXED and SURGE, we also simulates
them under the same static environment. In particular, the length of each timestep is set to be 15 minutes and the
number of steps in simulation is 96 (so 24 hours in total). For both FIXED and SURGE, we use the per-minute price
fitted from data as the base price, α = 0.5117, and allow the surge ratio β to be in [1.0, 5.0]. To make the evaluations
comparable, we use the distribution of drivers under the stationary solution of our convex program as the initial
driver distributions for FIXED and SURGE. Figure 6(a) shows how the instantaneous revenues evolve as the time
goes by, where DYNAM on average outperforms FIXED and SURGE by roughly 24% and 17%, respectively.
Note that our policy DYNAM is stationary under the static environment, the instantaneous revenue is constant
(the red horizontal line). Interestingly, the instantaneous revenue curves of both FIXED and SURGE are decreasing
and the one of FIXED is decreasing much faster. The observation reflects that both FIXED and SURGE are not
doing well in dispatching the vehicles: FIXED simply never balances the supply and demand, while SURGE shows
better control in the balance of supply and demand because the policy seeks to balance the demand with local supply
when supply can not meet the demand. However, neither of them really balance the global supply and demand, so
the instantaneous revenue decrease as the supply and demand become more unbalanced.
In other words, the empirical analysis supports our insight about the importance of vehicle dispatching in
ride-sharing platforms.

6.5

Dynamic environment

In the dynamic environment, the parameters (i.e., the demand functions and the total number of requests) are estimated
based on the statistics of each hour but averaged over different days. For example, the demand functions Dh (p|e)
are defined for each edge e and each of the 24 hours, h ∈ {0, . . . , 23}. In particular, we only use the data from the
weekdays (14 days in total)4 among the most popular 5 regions for the estimation.
Again, we instantiate the convex program (3.2) for the dynamic environment and solve via the fmincon function
on the same PC that we used for the static case. Figure 5(b) shows the convergence of the objective value with
increasing number of iterations, where each iteration takes less than 1 minute.
4 The reason that we only use data from weekdays is that the dynamics of demands and supplies in weekdays do have similar patterns but quite
different from the patterns of weekends.

13

We setup FIXED and SURGE in exactly the same way as we did for the static environment, except that the initial
driver distribution is from the solution of the convex program for dynamic environment.
Figure 6(b) shows the instantaneous revenue along the simulation. In particular, the relationship DYNAM 
SURGE  FIXED holds almost surely. Moreover, the advantages of DYNAM over the other two policies are more
significant at the high-demand “peak times”. For example, at 8 a.m., DYNAM (∼800) outperforms SURGE (∼600) and
FIXED (∼500) by roughly 33% and 60%, respectively.
Demand-supply balance Balancing the demand and supply is not the goal of our dispatching policy. However, a
policy without such balancing abilities are unlikely to perform well. In Figure 7, we plot the supply ratios (defined as
the local instantaneous supply divided by the local instantaneous demand) for all the 5 regions during the 24 hours of
the simulation.
From the figures, we can easily check that comparing with the other two lines, the red line (the supply ratio of
DYNAM) tightly surrounds the “balance” line of 100%, which means that the number of available drivers at any time
and at each region is close to the number of requests sent from that region at that time. The lines of other two policies
sometimes could be very far from the “balance” line, that is, the drivers under policy FIXED and SURGE are not in
the location where many passengers need the service.
As a result, our policy DYNAM shows much stronger power in vehicle dispatching and balancing demand and
supply in dynamic ride-sharing systems. Such advanced techniques in dispatching can in turn help the platform to
gain higher revenue through serving more passengers.

References
Javier Alonso-Mora, Samitha Samaranayake, Alex Wallar, Emilio Frazzoli, and Daniela Rus. 2017. On-demand
high-capacity ride-sharing via dynamic trip-vehicle assignment. PNAS (2017), 201611675.
Santiago Balseiro, Max Lin, Vahab Mirrokni, Renato Paes Leme, and Song Zuo. 2017. Dynamic revenue sharing. In
NIPS 2017.
Siddhartha Banerjee, Daniel Freund, and Thodoris Lykouris. 2017. Pricing and Optimization in Shared Vehicle Systems:
An Approximation Framework. In EC 2017.
Siddhartha Banerjee, Carlos Riquelme, and Ramesh Johari. 2015. Pricing in Ride-share Platforms: A QueueingTheoretic Approach. (2015).
Kostas Bimpikis, Ozan Candogan, and Saban Daniela. 2016. Spatial Pricing in Ride-Sharing Networks. (2016).
Stephen Boyd and Lieven Vandenberghe. 2004. Convex optimization. Cambridge university press.
Gerard P Cachon, Kaitlin M Daniels, and Ruben Lobel. 2016. The role of surge pricing on a service platform with
self-scheduling capacity. (2016).
Juan Camilo Castillo, Dan Knoepfle, and Glen Weyl. 2017. Surge pricing solves the wild goose chase. In EC 2017. ACM,
241–242.
Nelson D Chan and Susan A Shaheen. 2012. Ridesharing in north america: Past, present, and future. Transport Reviews
32, 1 (2012), 93–112.
M Keith Chen and Michael Sheldon. 2015. Dynamic pricing in a labor market: Surge pricing and flexible work on the
Uber platform. Technical Report. Mimeo, UCLA.
Judd Cramer and Alan B Krueger. 2016. Disruptive change in the taxi business: The case of Uber. The American
Economic Review 106, 5 (2016), 177–182.
Vincent P Crawford and Juanjuan Meng. 2011. New york city cab drivers’ labor supply revisited: Reference-dependent
preferences with rationalexpectations targets for hours and income. AER 101, 5 (2011), 1912–1932.
Zhixuan Fang, Longbo Huang, and Adam Wierman. 2017. Prices and subsidies in the sharing economy. In Proceedings
of the 26th International Conference on World Wide Web. WWW 2017, 53–62.

14

Ian L Gale and Thomas J Holmes. 1993. Advance-purchase discounts and monopoly allocation of capacity. The
American Economic Review (1993), 135–146.
Michel Gendreau, Alain Hertz, and Gilbert Laporte. 1994. A tabu search heuristic for the vehicle routing problem.
Management science 40, 10 (1994), 1276–1290.
Gianpaolo Ghiani, Francesca Guerriero, Gilbert Laporte, and Roberto Musmanno. 2003. Real-time vehicle routing:
Solution concepts, algorithms and parallel computing strategies. European Journal of Operational Research 151, 1
(2003).
Ramon Iglesias, Federico Rossi, Rick Zhang, and Marco Pavone. 2016. A BCMP Network Approach to Modeling and
Controlling Autonomous Mobility-on-Demand Systems. arXiv preprint arXiv:1607.04357 (2016).
Peter F Kostiuk. 1990. Compensating differentials for shift work. Journal of political Economy 98, 5, Part 1 (1990),
1054–1075.
Sébastien Lahaie and David M Pennock. 2007. Revenue analysis of a family of ranking rules for keyword auctions. In
EC 2007. ACM, 50–56.
Gilbert Laporte. 1992. The vehicle routing problem: An overview of exact and approximate algorithms. European
journal of operational research 59, 3 (1992).
Shuo Ma, Yu Zheng, and Ouri Wolfson. 2013. T-share: A large-scale dynamic taxi ridesharing service. In ICDE. IEEE,
410–421.
R Preston McAfee and Vera Te Velde. 2006. Dynamic pricing in the airline industry. forthcoming in Handbook on
Economics and Information Systems, Ed: TJ Hendershott, Elsevier (2006).
Luis Moreira-Matias, Joao Gama, Michel Ferreira, Joao Mendes-Moreira, and Luis Damas. 2013. Predicting taxi–
passenger demand using streaming data. IEEE Transactions on Intelligent Transportation Systems 14, 3 (2013),
1393–1402.
Gerald S Oettinger. 1999. An empirical analysis of the daily labor supply of stadium venors. Journal of political
Economy 107, 2 (1999), 360–392.
Michael Ostrovsky and Michael Schwarz. 2011. Reserve prices in internet advertising auctions: A field experiment. In
EC 2011Practical. ACM, 59–60.
Ben Roberts, Dinan Gunawardena, Ian A Kash, and Peter Key. 2016. Ranking and tradeoffs in sponsored search
auctions. ACM Transactions on Economics and Computation 4, 3 (2016), 17.
Weiran Shen and Pingzhong Tang. 2017. Practical versus Optimal Mechanisms. In AAMAS. 78–86.
Joanna Stavins. 2001. Price discrimination in the airline market: The effect of market concentration. Review of
Economics and Statistics 83, 1 (2001), 200–202.
Christopher S Tang, Jiaru Bai, Kut C So, Xiqun Michael Chen, and Hai Wang. 2016. Coordinating supply and demand
on an on-demand platform: Price, wage, and payout ratio. (2016).
Yongxin Tong, Yuqiang Chen, Zimu Zhou, Lei Chen, Jie Wang, Qiang Yang, Jieping Ye, and Weifeng Lv. 2017. The
simpler the better: a unified approach to predicting original taxi demands based on large-scale online platforms. In
KDD 2017. ACM, 1653–1662.
Dengji Zhao, Dongmo Zhang, Enrico H Gerding, Yuko Sakurai, and Makoto Yokoo. 2014. Incentives in ridesharing
with deficit control. In AAMAS 2014.

15

