Optimal Pricing for Improving Efficiency of Taxi Systems

1 Introduction

As an efficient and convenient way for short-distance travel, taxi has been an indispensable mode of transport in most large cities. It is easily accessible and comfortable compared with other types of public transport. Therefore, it is essential for decision-makers to regulate the taxi market to balance taxi supply and customer demand, especially during peak hours. However, this has been a challenging issue due to the decentralized nature of the taxi systems and taxi drivers' profitdriven behavior.

A long-standing problem in the taxi market in Beijing is the insufficient taxi supply during peak hours. During these periods most taxi drivers intentionally avoid working regardless of the huge demand (Fig. 1(a)). As a result, a large number of customers have to spend a lot of time (sometimes more than 2 hours) waiting for a taxi (Fig. 1(b)). Some even may have to switch to unlicensed taxis, which typically charge a higher rate and pose threats to road safety. The improper pricing of the current taxi fare structure, as revealed by recent interviews to taxi drivers is the main cause of this dilemma. The taxi fare in Beijing is calculated primarily by trip distance, and it stays stable throughout the day. Typically, travel speed is low during peak hours due to traffic congestion. As a result, a taxi driver may choose not to work since the income may be even lower than the operation cost (gas cost and etc.).

There has been some research works on analyzing taxi market equilibrium in the literature, but market efficiency is ignored by them. Yang et al. [2005a] studied the taxi market in the presence of traffic congestion with the objective of identifying market equilibrium. The study did not consider taxi drivers' decision making process (i.e., work or not). Other than that, the number of working taxis was set to a constant value instead of a variable which is determined by taxi drivers' operation strategies. In another study, Yang et al. [2005b] analyzed the taxi market with consideration of market variance over multiple periods. This study provided a framework for modeling the taxi market under a multi-period scenario. However, as key factors that affect taxi drivers' decision, variance of traffic condition and interdependence of each period are not revealed in this study. Recently, there are some works on traffic control and intersection management using AI techniques [Au et al., 2011; Bazzan, 2009; Dresner and Stone, 2008; Xie et al., 2012], but these approaches cannot be used to improve taxi market efficiency. In this paper, we propose to adjust the current taxi fare to give taxi drivers extra incentives for working in peak hours, which has been adopted in several countries like Singapore. However, to the best of our knowledge, there has been no research on how to generate the optimal fare structure.

To compute the optimal fare, we first analyze how taxi drivers react to changing market conditions and how these reactions affect market conditions in return. Different from previous studies, we consider the variations of market conditions over multiple time periods since taxi drivers' strategies in one period are highly dependent on strategies in other periods due to scheduling constraints on total working time and maximum continuous working time. Then we calculate the taxi drivers' best-mixed strategy to study their behavior in response to market condition variations. However, a driver's strategy space increases exponentially with the number of working periods. To resolve this scalability issue, an atom schedule method is developed to decompose a schedule into several atom schedules. As a result, the problem magnitude is significantly reduced due to the smaller number of atom schedules. Based on the analysis of drivers' behavior, we search the optimal fare that maximizes the overall efficiency of the taxi system. We computed optimal fare structure for Beijings taxi market using real data, and experimental results show that market efficiency was significantly improved.

2 Optimal Pricing for A Single Period

In order to study the variance of taxi market over a whole day, we divide a day into several short periods with the equal duration τ, and assume that during each period, taxi supply, customer demand, the number of on-road vehicles, and vehicle travel speed are uniform. This section focuses on analyzing optimal pricing for a single period, which forms the basis for computing the optimal pricing scheme over multiple periods.

2.1 Traffic Conditions and Fare Structure

In the following sections, unless otherwise specified, variables and parameters with a superscript i are related to period i. We denote average travel speed in period i as V i , and assume V i is a linear function of traffic load N i (number of vehicles on the network) as most work in the literature did (e.g., [Smith and Cruz, 2012]):

where constant vf is the free-flow speed obtained at N i = 0 when there is no vehicle on road. Constant Nmax is the maximum capacity of the road network. When N i = Nmax, V i = vf/Nmax is close to zero, and the traffic may travel in a "stop-and-go" manner, rather than complete gridlock.

We separate taxis from other normal vehicles, and assume that the number N inor of normal vehicles is a constant. Let the number of working taxis be N iw . We rewrite Eq. (1) as

According to current taxi fare structure of Beijing and other major cities in China, a taxi fare consists of: a flag-down charge, which covers an amount of initial distance, and a distance-dependent charge on top of the flag-down charge. We define the taxi fare for period i as

where f i is the per unit distance price, which is to be adjusted to improve taxi market efficiency. 1 d is the travel distance. f0 and d0 are initial charge and the distance covered by initial charge respectively, which are the same for all periods.

2.2 Customer Demand

We assume that customer demand in a specific period depends on monetary and time cost for taxi service, i.e., taxi fare, travel time, and waiting time, as in many existing works such as [Yang et al., 2002; 2005b]. Here customer demand represents the number of customers transported by the taxi system. Specially, customer demand in period i is defined as

where Dimax is a constant representing the maximal potential customer demand. F i , Li and W i are trip fare, travel time, and customer waiting time respectively. m is the average number of passengers in a trip. φ1 > 0 and φ2 > 0 are parameters used for converting Li and W i into monetary costs respectively. β > 0 is a demand sensitivity parameter.

We define Li as Li = ¯ d/V i , and F i as F i = F i (f i , ¯ d), where ¯ d denotes average trip distance. We assume that ¯ d is a constant, and denote F i as F i (f i ) for short. Waiting time W i is negatively related to the number of vacant taxis available:

where 1 - Li τ · Di mN iw represents a taxi's vacancy rate.

2.3 Taxi Drivers' Strategy

To simplify the analysis, we assume that all taxi drivers are identical and they adopt the same operation strategy, i.e., in period i they all choose to work with probability pi , and not to work with probability 1 - pi . Given the total number of licensed taxis Nt, N iw = Nt · pi taxis choose to work. Substitute this into Eq. (2), V i can be written as a function of pi , V i = V i (pi ) for short.

Taxi drivers are self-interested and always adjust their working probability pi to maximize their individual revenue. We define a taxi driver's utility as

where Di mN iw · F i -cg · τ represents the revenue of working in period i, as Di mN iw is the number of trips a taxi serves, and cg is the cost on gasoline consumption per unit time.

1 We choose to improve the current fare structure, instead of redesigning a new fare structure, or adopting other existing structures. This is because 1) other fare structures, such as the time-dependent structure which is widely used in some European countries, may not be applicable to Beijing due to differences in culture, economy, and most importantly the level of traffic congestions in comparison to other cities; 2) our idea of giving taxi drivers' extra incentives can be well achieved with the current fare structure. In addition, our model can also be easily extended to other fare structures if necessary.

From Eqs. (4) and (5), Di = Di (W i (Di , pi ), pi , f i ). Given pi and f i , Di is in fact a function of itself. We define the following equation

Yang et al. [2005b] proved that there is one and only one solution to this equation. From Eq. (5) and the fact that W i > 0, we have 0 < Di < mN iw V i τ/ ¯ di . Thus Φ(Di ) is a continuous function of Di ∈ (0,mN iw V i τ/ ¯ di ), and

Furthermore, it can be easily verified that

Thus there is one and only one point where Φ(Di ) = 0, and correspondingly one and only one solution to this equation.

By substituting this solution into Eqs. (5) and (6), we could calculate the values of W i and U i . Therefore, Di , W i and U i are all implicitly and uniquely determined by pi and f i . We write U i as a function U i = U i (pi , f i ). Given f i , taxi drivers would maximize their utility by choosing an optimal working probability pi∗ , such that

This paper assumes that each taxi driver chooses his optimal working probability to maximize his revenue. Taxi drivers' working probability affects traffic condition, waiting time, and customer demand. Since we do not distinguish different taxi drivers, the optimal working probability for a given fare structure is in fact an equilibrium strategy for all drivers.

2.4 Computing the Optimal Price

Our objective is to maximize taxi system efficiency, which is measured by customer demand Di under market equilibrium. Intuitively, given our model, higher customer demand indicates higher driver working probability, higher driver revenue, and higher social welfare. Moreover, our framework can also be easily extended to optimize other objective functions. We construct an optimization program for period i as follows:

The above program is a bilevel program with two levels involved: an upper level defined in Eq. (9), and a lower level defined in the first constraint. To look into the lower level program, we consider a period from 17:00 to 18:00 using real data (Section 4.1). From the plot of U i with different pi , we find that for f i = ¥2.00 to ¥5.00, when pi is very close to 0, U i first drops for a short section (Fig. 2(b)). This is because the the number of taxis increases by more than the increasement of customer demands. However, this situation

Algorithm 1: Compute optimal fare for period i

1 Optf←Null, MaxD←-∞; 2 F ← {fmin, fmin +Δ, fmin +2Δ, ..., fmax}; 3 for each x ∈ F do 4 f ← x; 5 Solving program presented in Eqs. (11) and (12) ; 6 d ←Optimal Di obtained in last setp; 7 if d > MaxD then MaxD ← D, Optf ← x; 8 end 9 return Optf;

happens with an extremely small percentage (from Fig. 2(b) less than 0.4%) of working taxis, which is unlikely to happen in reality. From Fig. 2(a), we see that U i is almost a concave function of pi , which indicates that there is always only one optimal solution to the lower level problem.

Moreover, it is unnecessary to consider extremely large or small values for f i , since drivers cannot make money with very low price, and the demand would be extremely small with a very high price. It is also unnecessary to consider prices with too many digits, such as ¥2.345. Thus we focus on some candidate prices within a reasonable range [fmin, fmax] (e.g., ¥1.00, ¥1.20, ¥1.40, ..., ¥5.00). Alg. 1 searches the optimal price from several candidate prices within [fmin, fmax] with the difference Δ. Line 5 solves the lower level optimization program redefined as:

Note that since U i as a function of pi and f i is not defined explicitly, we take Di and W i as independent variables, and consider their dependence in the first two constraints.

3 Optimal Pricing for Multiple Periods

In this section, we extend the modeling framework for period i to a whole day, which is divided into n periods. 2 We extend each period-dependent variable to a vector for multiple periods, e.g., we denote average travel speed as V =

2 This paper assumes that different days have identical traffic condition. However, our analysis can be easily extended to handle traffic condition differences between deferent days.

(V 1 , ..., V n ). Similarly, we denote customer demand, customer waiting time and each taxi driver's utility as D, W and U respectively. We denote the percentage of working taxis and per unit distance price as p and f respectively.

3.1 Taxi Driver's Optimal Mixed Strategy

For multiple periods, a taxi driver's pure strategy corresponds to an operation schedule over all periods. For example, for n = 3, a pure strategy could be: work in the first and the third periods, and rest in the second period. We denote such a pure strategy by a vector s = (s1, ..., sn), such that si = 1 if the driver chooses to work in period i, and si = 0 otherwise. Moreover, each taxi driver faces additional realistic scheduling constraints that must be taken into account:

• C1: ∑ni=1 si ≤ nw. C1 requires that each taxi driver should not work for more than nw periods a day.
• C2: maxi,j:∀i≤k≤j,sk=1(j - i) ≤ nc. C2 requires that each taxi driver should not work continuously for more than nc periods.

Let the set of feasible pure strategies be S. A mixed strategy can be represented as a vector x, whose element xs is the probability assigned to schedule s. The mixed strategy space is X = {x : 0 ≤ xs ≤ 1, ∑s∈S xs=1}. A mixed strategy determines the percentages p of working taxis in each period:

Therefore, p is a function of x. According to analysis in Section 2.3, once p and f is specified, travel speed, customer demand, waiting time and taxi drivers' utility for each period are all determined. We define taxi drivers' overall utility Ump as Ump = ∑ni=1 U i , which is determined by p and f. We can thus write Ump = Ump(p, f) = Ump(x, f), since p is determined by x. Thus a driver's optimal strategy is

Similar to Alg. 1, we solve this optimization problem, and then search for the optimal prices for different periods. However, one issue for this approach is that the pure strategy space S grows exponentially large with the number n of periods. E.g., when n=18, nw=10, and nc =4, |S| will be 176178. There will be as many variables in the above optimization problem, which makes the approach inapplicable to more fine grained discretization of periods.

3.2 Compact Representation of Mixed Strategies

We use a compact representation of a taxi driver's mixed strategy to address the scalability issue. Such technique has been used to solve large scale security games (e.g.,[Kiekintveld et al., 2009], [An et al., 2011], [An et al., 2012], [Yin et al., 2012]). The idea is to represent each schedule with a set of Atom Schedules (AS), which has a much smaller size than |S|. We seek an optimal allocation of these ASs which maximizes Ump, rather than an optimal mixed strategy as we do in Eq. (14). Using this optimal allocation of AS, we then construct a mixed strategy which maximizes Ump, such that a solution to Eq. (14) is obtained.

Denote an AS as a tuple o〈j, k〉. Following o〈j, k〉, a taxi driver works continuously from period j to k. Let O = {o〈j,k〉 : 1 ≤ j,k ≤ n, 0 ≤ k-j < nc}. Thus any schedule satisfying both C1 and C2 can be constructed by linking several ASs in O with at least one resting periods between each pair of neighboring ASs, and there are less than nc · n ASs in O, which is far less than |S|. We assign a weight wo to each o ∈ O to represent the percentage of drivers whose schedule contains o. Denote the weights of all o ∈ O as a vector w. w determines an allocation of ASs. Therefore, the percentage p of working taxis could be computed by pi = ∑o∈O wo · δ(o, i), where δ(o, i) = 1 if period i is covered by o, and δ(o, i) = 0, otherwise.

Therefore, given f, w determines p, and then Ump. We formulate an optimization program as shown in Eqs. (15) to (18), which takes w as variable and maximizes Ump for given f. Eqs. (16) to (18) restrict w to a feasible domain, which ensures that a mixed strategy satisfying C1 and C2 can be constructed in the next step.

∑

o∈O

i=1

Here in Eq. (17), qi = ∑o∈O wo · δ′ (o, i), where δ′ (o, i) = 1 if o ends at period i1, and δ′ (o, i)=0, otherwise. In other words, qi represents the percentage of drivers switching from work to rest at period i-1, whom should not work in period i. Eq. (18) requires the overall coverage to be no larger than nw.

As is justified by Proposition 1, Alg. 2 construct a mixed strategy satisfying C2, but not necessarily C1. The time complexity of Alg. 2 is O(|O|2 ).

Proposition 1. Alg. 2 returns a mixed strategy (a distribution over a set A of schedules) which satisfies C2.

Proof. Firstly, each schedule in A satisfies C2, because they are constructed by linking ASs leaving at least one resting period between each neighboring ASs (Line 6).

Next, we show that probabilities of all schedules in A sum to 1, which is required by the definition of a mixed strategy. Let the k-th added schedule be sk, and its probability be xsk . Since Lines 16 to 19 adds a special schedule with no periods covered, the sum of probabilities will always be no less than 1. Thus, we only need to show that ∑|A| l=1 xsl ≤ 1, where |A| is the number of schedules in A. We prove this result by the following contradiction.

For k=1, we have ∑kl=1 xsl =xs1 ≤ 1. For some k > 1, suppose that ∑kl=1 xsl ≤ 1, but ∑k+1 l=1 xsl >1.

Lines 5 to 7 search for the earliest appendable AS for the schedule being constructed. Let o〈i, j〉 be the first AS of sk+1. This portion of o〈i, j〉, which is not used in the construction of s1, ..., sk, indicates that in each one of s1, ..., sk, at least one of period i and period i - 1 is already covered. This is because assume that both of them are not covered in a

wo · δ(o, i) ≤ nw.

(18)

schedule s ∈ {s1, ..., sk}, then o〈i, j〉 should be the earliest appendable AS for s after period i - 1, and should be appended to s while s is being constructed; thus period i should be covered, which contradicts the assumption that it is not covered.

So, there exists an AS o∗ 〈i∗ , j ∗ 〉 in each one of s1, ..., sk, which either covers period i or ends at period i - 1. We have δ(o∗ , i) + δ′ (o∗ , i) = 1 by the definition of δ and δ′ in Section 3.2. Let O∗ = {o∗ 〈i∗ , j ∗ 〉 : o∗ ∈ O, δ(o∗ , i) + δ′ (o∗ , i) = 1}. For period i, we have

Furthermore, wo should be no less than the sum of probabilities of schedules in which o appears. Since there exists an AS o ∈ O∗ in each one of s1, ..., sk+1, we have

which contradicts Eq. (17).

Therefore, we conclude that ∑kl=1 xsl ≤ 1 holds for any k ≥ 1. Specially, we have ∑|A| l=1 xsl ≤ 1. We conclude that Alg. 2 returns a mixed strategy satisfying C2.

Alg.3 further adjusts the mixed strategy obtained by Alg. 2 to one that satisfies both C1 and C2. The core of Alg. 3 is a swapping method presented in Lines 5 to 7. Denote the number of periods covered by s as c(s). We find that if there is a schedule s in A which violates C1, i.e., c(s) >nw, we can always find another schedule s′ where c(s′ ) < nw, because the overall coverage is no more than nw by Eq. (18).

We use a split to divide a schedule into two subschedules. Denote a subschedule of schedule s as sj,k, which begins at period j and ends at period k. A split can be placed between two adjacent periods. Let the split right after period i be split i. By applying split i to s and s′ such that c(s) > nw and c(s′ ) < nw, we divide them into subschedules s1,i, si+1,n and s′1,i , s′i+1,n respectively. Then we execute a swapping procedure which links s1,i to s′i+1,n , and s′1,i to si+1,n to create two new schedules denoted as s1,i+s′i+1,n and s1,i+ s′i+1,n . Proposition 2 shows that we can always find a safe split i, such that c(s1,i+s′i+1,n ) = nw. Here a split is safe if a swapping on it does not cause violation of C2.

Figure 3: Possible patterns for c(s1,i + s′i+1,n ) = nw + 1.

Proposition 2. For schedules s and s′ , where c(s) > nw and c(s′ ) < nw, a safe split i with c(s1,i+s′i+1,n ) = nw can always be found.

Proof. We search for such a split with the loop shown in Lines 5 and 7 of Alg. 3, and prove that this loop always ends with a safe split i, such that c(s1,i + s′i+1,n ) = nw. We first show that this loop will never encounter a split such that c(s1,i + s′i+1,n ) ≥ nw + 1:

The for-loop in Lines 5 to 7 checks if the split in the current iteration is safe and if it covers nw periods. Assume that the for-loop encounters a split i, such that c(s1,i+s′i+1,n ) = nw + 1 for the first time. We find that c(s1,i-1 + s′i,n ) = nw because c(s1,i + s′i+1,n ) - c(s1,i-1 + s′i,n ) = si - s′i ∈ {-1, 0, 1}, and c(s1,i-1 + s′i,n ) can not be nw + 1 or nw + 2 since we assume that split i is the first split such that c(s1,i + s′i+1,n ) = nw+1. Therefore, we have c(s1,i-1+s′i,n ) = nw, and si = 1, s′i = 0. Consider the two periods right before split i, Fig. 3 depicts all possible covering patterns. However, all these patterns will in fact not appear:

• Clearly, for patterns shown in Figs. 3(a) and 3(b), split i - 1 is safe, together with the fact that c(s1,i-1 + s′i,n ) = nw, the loop should end before it encounters split i. Therefore, these two patterns will not appear.

• For pattern shown in Fig. 3(c), we find that c(s1,i-2 + s′1,i-2 ) = nw+1, which contradicts the assumption that split i is the first such split. Therefore, this pattern will not appear.
• For pattern shown in Fig. 3(d), we find split i - 1 is also safe. Because if it is not safe, then the AS in s′ ending at period i - 1 must start earlier than the AS in s which covers period i. Let j be the index of the starting period of the AS in s which covers period i, we have c(s1,j-2 + s′j-1,n ) = nw + 1 as shown in Fig. 4, which contradicts the assumption that split i is the first split such that c(s1,i + s′i+1,n ) ≥ nw + 1. Therefore, this pattern will not appear.

Therefore, the for-loop will never encounter a split i, such that c(s1,i + s′i+1,n ) = nw + 1. Moreover, since c(s1,i + s′i+1,n ) grows by at most 1 in each iteration of increasing i by 1, it can not jump from a value smaller than nw + 1 to another one larger than nw + 1. Thus the loop will in fact never encounter a split i, such that c(s1,i+s′i+1,n ) ≥ nw+1. Since we already have that when i = n, c(s1,i + s′i+1,n ) = c(s1,n + s′n+1,n ) = c(s) ≥ nw + 1. 3 We conclude that the loop will always end before i reaches n, thus the only reason for its ending is that it breaks with a safe split i such that c(s1,i + s′i+1,n ) = nw (Line 6).

Thus we transform s and s′ into two new schedules with coverages of nw and c(s)+c(s′ ) -nw respectively. For the latter one, we have c(s)+c(s′ )-nw < c(s), which is, if not smaller or equal to nw, at least one period closer to nw than c(s). Note that we only swap s and s′ by a feasible portion. For example, if the probabilities of s and s′ are 0.5 and 0.3, we can only take a portion of 0.3 from s to swap with s′ . The maximum swappable portion of s and s′ is the minimum of their probabilities (Line 9). The left portion will be handled by swapping with another s′ as Alg. 3 proceeds.

We show that Alg. 3 will eventually end after swapping for at most 2n times. In Line 1, we divide A into subsets Ak. After each swapping, at least one of s and s′ will be removed (Lines 12 and 13), and at least one of |Ac(s)| and |Ac(s′ )| will be reduced by 1. The newly added schedules (Line 10) are always added to a subset Ak, such that c(s′ ) < k < c(s), which will never increase |Ac(s)| or |Ac(s′ )|. Since |Ak| ≤

3 As is defined in Section 3.2, subschedule sj,k begins at period j and ends at period k. In other words, sj,k is a subschedule between split j-1 and split k, thus s′n+1,n represents a subschedule between split n and split n, i.e., a null schedule.

Algorithm 3: Adjust a mixed strategy to satisfy C1, C2

1 Ak←{s:s∈A, c(s)=k}, k=1, ..., n; 2 while ∪nk=nw+1Ak ̸= ∅ do 3 Let s be the schedule with highest c(s) in ∪nk=nw+1Ak ; 4 Let s′ be the schedule with lowest c(s′ ) in ∪nw k=1Ak ; 5 for i = 1 to n do 6 if c(s1,i+s′i+1,n)=nw and split i is safe then Break; 7 end 8 t←s1,i+s′i+1,n, t′ ←s′1,i+si+1,n ; 9 x←min{xs, xs′} ; 10 Add 4 t to Anw ; Add t′ to Ac(t′); 11 xs←xs -x, xs′ ←xs′ -x; 12 if xs =0 then remove s from Ac(s); 13 if xs′ =0 then remove s′ fromAc(s′); 14 end 15 return ∪nw k=1Ak with probability xs for each s∈∪nw k=1Ak ;

(nk ), after swapping for at most ∑nk=0 (nk ) = 2n times, all the subsets except Anw will be empty, and Alg. 3 will thus end.

In addition, swapping does not change the value of pi , such that Eq. (18) can always be satisfied. For Eq. (17), since in each schedule, there can be at most one AS which covers period i, or ends at period i-1, we have pi +qi ≤ ∑s∈A xs ≤ 1, which means Eq. (17) will always be satisfied.

3.3 Optimal Price for Multiple Periods

We extend the objective function for a single period to one for multiple periods by summing up the objective functions of all periods. Alg. 4 searches from a set of candidate prices for each period. For each price scheme, Alg. 4 solves the program presented in Eqs. (15) to (18) to obtain each taxi driver's optimal strategy. Here we transform this program to another form as shown in Eqs. (19) to (20) by taking D and W as independent variables, so as to address the implicitly defined relationship between them.

Rather than optimizing f as an n-dimensional vector, we reduce it to two segments: one for normal periods, and the other for peak periods. The reason that we propose such a simplified fare structure for multiple periods is that firstly, research (e.g., [Bilton, 2012]) has shown that a too complex fare structure may make customers unpleasant, as the total fare will be hard to predict; secondly, with such a simplified fare

4 If there already exists a schedule with the same coverage pattern as the newly added one, just update the probability of the existing one with the sum of their probabilities.

1 Optf←Null, MaxD←-∞ ; 2 f←{2.00, ..., 2.00}, F← {fmin, fmin +Δ, ..., fmax}; 3 for each f ∈ F do 4 Replace prices for peak periods in f with f; 5 Solve optimization program defined in Eq. (19) and (20); 6 if ∑ni=1Di >MaxD then MaxD← ∑ni=1Di , Optf ←x; 7 end 8 return Optf;

structure, the computational complexity could be largely reduced. We use the single-period model to calculate customer demand with variance of per unit distance fare f for each period. We identify periods where customer demand decreases at prices larger than ¥2.00 as normal periods, and the rests as peak periods. This is because, intuitively, customers are more sensitive to the fare price at normal periods when taxi supply is sufficient, such that extra incentive for these periods could hardly attract more taxi drivers to work. Next, Alg. 4 fixes the fare price for normal periods to ¥2.00, and searches the optimal fare price for peak periods within the candidates. We can also relax the price for normal periods, and search on a two-dimensional space to optimize prices for both peak and normal periods, for which we just need more iterations.

4 Experimental Evaluation

Experiments based on real data are provided to evaluate our approach. We use software KNITRO (version 8.0.0) to solve all the non-linear programs, e.g., Eqs. (11) and (12).

4.1 Data Sets

According to Annual Report on Beijing's Transportation 2010, the total number of Beijing's licensed taxis T = 6.66×104 , average trip distance ¯ d = 7.2 km. Suppose Dmax for each period is proportional to the total demand for bus, subway and taxi services, and Nnor for each period is proportional to the demand of private cars. We set values of Dmax and Nnor as depicted in Table 1. We take 1 hour as a period, i.e., τ = 1 hour, and consider 18 periods from 5:00 to 23:00, since customer demand in other time is negligible. We set maximum working time nw = 9 hours, and maximum continuous working time nc = 4 hours .

For the function of travel speed and number of working taxis defined in Eq. (2), we set vf = 50 km/h, Nmax = 100 × 104 , thus we have V i (pi ) = -5.00×10-5 (N inor + 6.66 × 104pi ) + 50.00. We set gas price cg = ¥20/hour from interviews to taxi drivers. We set β = 0.06, ω = 400 with reference to researches from Yang et al. (e.g., [2005b]), and set m = 1.5 according to media reports. We set φ1 = ¥20/hour and φ2 = ¥40/hour given that: 1) φ1 and φ2 should be similar since they are both values for time; 2) φ2 should be larger than φ1 since, empirically, waiting time is more critical on customer's experience to taxi service.

4.2 Experiment Results for a Single Period

We use the single-period model to pick out peak periods. Customer demands at prices varying from ¥1.00 to ¥8.00 with a difference of ¥0.50 are calculated for each period. Experiment results for the 7th period (11:00 - 12:00), and the 13th period (17:00 - 18:00) are presented in Fig. 5. As is shown in Fig. 5(a), customer demand decreases with the price in the 7th period, while in the 13th period it increases. Thus we identify the former period as a normal period, and the latter one as a peak period. For all the 18 periods, the 3rd and the 4th periods (7:00 - 9:00), and the 13th and the 14th periods (17:00 - 19:00) are identified as peak periods.

Fig. 5(b) depicts the percentage of working taxis with variance of fare price at the two typical periods. We see that percentage of working taxi drivers exhibits similar trend as customer demand. In the peak period, percentage of working taxis and customer demand drop to 0 when the price is too low, i.e., no drivers choose to work because of potential negative revenue generation.

4.3 Experiment Results for Multiple Periods

The optimal price for peak periods obtained using the multiperiod model is ¥3.00. Under this price, customer demands of peak periods are improved compared with the current situation (Fig. 6(a)), while at the same time customer demand of the whole day increases from 187.78 × 104 to 200.50 × 104 . Fig 6(b) shows two significant valleys of the number of working taxis in the peak periods in the current market, which accords with the reality. Under the optimal price, these two valleys both move upward, which indicates the effectiveness of the extra incentive. Percentages of taxis in the normal periods exhibit the similar patterns, because fixed prices for these periods result in the same market conditions of each period. However, there are some slight changes over these periods caused by the interdependence of taxi drivers' strategies among different periods. Fig. 6(c) depicts variance of a taxi driver's expected revenues. Fig. 6(d) depicts total working time of taxi drivers under different prices. The drivers are more willing to work with higher prices, however, the total working time is bounded after the price is higher than ¥3.00, where the maximum working time is reached.

5 Conclusions

The key contributions of this paper include: (1) a realistic taxi market model considering taxi drivers' behavior under market variance over multiple periods; (2) an atom schedule method with novel algorithms to address computational challenges due to the large size of pure strategies; and (3) experiments based on real data which show that the new pricing scheme achieved significant efficiency improvement. We believe this study will stimulate the interest in applying innovative AI techniques to improve taxi system efficiency and other sustainability issues in megacities.

6 Acknowledgement

This work was supported by the National Program on Key Basic Research Project (973 Program) (No. 2013CB329502), National Natural Science Foundation of China (No. 61035003, 61202212, 61072085, 60933004), National High-tech R&D Program of China (863 Program) (No. 2012AA011003), National Science and Technology Support Program (2012BA107B02), China Information Technology Security Evaluation Center (CNITSEC-KY-2012-006/1). The work of the forth author was supported in part by the National Natural Science Foundation of China Grant (No. 61170062, 61222202).