T-Balance: A Unified Mechanism for Taxi Scheduling in a City-scale

Ride-sharing Service

Jiyao Li and Vicki H. Allan

Department of Computer Science, Utah State University, Logan, Utah, U.S.A.

Keywords:

Ridesharing Service, Task Assignment, Vehicle Repositioning, Q-learning.

Abstract:

In this paper, we propose a unified mechanism known as T-Balance for scheduling taxis across a city. Balanc-

ing the supplies and demands in a city scale is a challenging problem in the field of the ride-sharing service.

change environments. The experimental results verify that the unified mechanism is effective and flexible.

1 INTRODUCTION

Thanks to the rapid development of wireless networks

and the prevalence of portable smart devices, ride-

sharing services have become an important part of

our daily life. Ride-sharing services pool passengers

with similar itineraries and time schedules together in

a single taxi. Such services may provide positive im-

pacts on society and the environment by reducing traf-

fic congestion, emission of carbon dioxide, and taxi

lion drivers worldwide working for Uber. A recent

market report (Curley, 2019) also showed that global

ride-sharing service is valued at $61.3 billion and ex-

pected to reach $218 billion by 2025. To increase fu-

ture market shares, ride-sharing service corporations

are willing to spend large sums of money optimizing

service operations such as reducing travel cost, serv-

ing more riders with fewer taxis, and improving pas-

sengers’ satisfaction.

If the distribution of taxis across the city could be

tween requesting a ride and being picked up). There-

lenging when there are a large amount of riders and

taxis. Evaluating demand patterns in a city scale at a

specific period is difficult, since the number of rider

requests might fluctuate dramatically in as little as an

hour. Also, some riders’ destinations are in demand-

sparse areas such that delivery will lead taxis away

from demand-dense areas, leaving many passengers

in busy areas unserved even though corporations em-

ploy a large number of taxis. In addtion, each rider

has a patience period, that is, they will cancel the re-

research on forecasting taxi demand patterns across

a city. However, their works focused on predicting

taxi demand patterns at a given timestamp rather than

evaluating long-term demand (Zhang et al., 2017a)

(Xu et al., 2018) (Liu et al., 2019); (ii) Many current

works proposed various solutions of ride-matching in

order to meet the balance between supply and de-

mand, but they only consider balancing taxi distri-

458

bution in local areas rather than citywide (Banerjee

et al., 2018) (Wang et al., 2018) (Xu et al., 2018)

(Zhang et al., 2017b) (Li and Allan, 2019); (iii)

Most research papers designed different repositioning

strategies to guide vacant taxis to busy areas where

drivers would have greater opportunities for picking

up passengers, but such solutions often omitted bal-

ancing supply and demand in local areas, although

taxis could be scheduled in a wider area (Wen et al.,

2017) (Lin et al., 2018) (Qu et al., 2014) (Jha et al.,

ride-sharing service, we propose a unified mechanism

known as T-Balance. The main contributions of the

current work are described as following:

riders to be served such that taxis can be sched-

uled to needed places in the process of ride-

matching.

calculate a new popularity score to estimate long-

term demand density for each zone of the city.

ment (QIM) mechanism to reposition vacant taxis

citywide, increasing the taxi service’s ability to

meet demand in the busiest areas of a city.

The remainder of the paper is organized as fol-

lows: we discuss recent related works of ride-sharing

services in section 2; in section 3, the business model

of ride-sharing service is introduced; in section 4,

we propose a novel unified mechanism known as T-

Balance for a city-scale ride-sharing service; in sec-

tion 5, we compare our method to other approaches

We organize the previous works in terms of demand

sharing platforms be smarter in scheduling taxis

across a city. (Zhang et al., 2017a) proposed a

deep learning-based approach known as Deep Spatio-

Temporal Residual Networks (ST-ResNet) to pre-

dict the demand of a city. (Xu et al., 2018) de-

signed a sequence learning model based on Recur-

rent Neural Networks (RNN) to predict rider requests

in different areas of a city. (Yao et al., 2018) con-

structed a novel Deep Multi-View Spatial-Temporal

Network (DMVST-Net) framework to model both

on predicting future demand at a given timestamp, but

do not consider providing the ride-sharing platform

with a long-term model.

ride-sharing platform. (Banerjee et al., 2018) pro-

posed a Scaled MaxWeight (SMW) approach to

schedule vehicles for demands in local areas. This

method utilizes a closed queueing network and dis-

patches taxis from the queue with the most supplies.

SMW has proven effective, but the authors do not

offer a concrete solution for how to estimate de-

mand weight. (Wang et al., 2018) optimizes the ride-

matching policy by deep reinforcement learning. A

Deep Q-network (DQN) with an action search was

solve the order dispatch problem. The offline learning

step summarizes demand and supply patterns through

historical data, then driver-order pairs are created by

a combinatorial optimizing algorithm. (Zhang et al.,

2017b) proposed Stochastic Gradient Descent (SGD)

forecasting the combined probability of each rider and

driver pairs and the Hill Climbing algorithm was used

to maximize the global success rate. The drawback

of both methods is that passengers may be forced

to wait longer for service, although the serving rate

keep balance between supply and demand. The fleet

size can be reduced by 14% with slightly increased

extra taxi travel distance, but this method might lead

to excess taxis in busy areas. (Lin et al., 2018) mod-

eled the movement of vacant taxis as a multi-agent

problem and proposed an approach known as contex-

tual multi-agent actor-critic, which is a novel version

of Multiagent Reinforcement Learning (MARL). (Qu

et al., 2014) aimed to maximize the net profit of taxis.

The authors created a graph representing road net-

they argued that drivers’ net profit could be maxi-

mized.

In addition, various price mechanisms have been

straint function was proposed by (Ma et al., 2014) to

motivate passengers to participate in a ride-sharing

service. (Kleiner et al., 2011) aimed to minimize

serving rate and the Sealed-Bid Second-Price Auction

(SBSPA) was proposed to distribute taxi resources

among passengers. (Asghari et al., 2016) allocate

requesting customers through Sealed-Bid First-Price

Auction (SBFPA) mechanism such that the profit of

drivers could be maximized. A VCG (Wooldridge,

a city.

matching) and direct the vacant taxis to needed places

(Idle Movement)

460

In this work, we propose the Lottery Selection (LS)

to select appropriate rider requests for drivers in the

process of ride-matching, such that taxis would have

more chances to be dispatched to the busier zones that

need more supplies than others. The idea of the Lot-

tery Selection is described as following: each rider is

given a certain amount of lottery tickets L

according

to the popularity score P of their destination, and a lot-

tery number LOT T ERY NUM is drawn then the ap-

propriate rider to be served is the rider who owns the

Definition 2: Balanced Factor. Given specific times-

tamp t and zone z, the balanced factor B is the propor-

tion between the number of available taxis A(t, z) and

the smoothed popularity score smooth(P(t, z)). It can

be defined by the Eq.(2):

B(t, z) =

A(t, z)

1 + smooth(P(t, z))

(2)

In (Li and Allan, 2020), the popularity score of

zones.

P(t, i) (3)

Based on the Lottery Selection and Balanced Fac-

tor, a new ride-matching algorithm named Scoring

Ride-matching with Lottery Selection (SRLS) is pro-

posed. The main idea is to dispatch taxis from

the least busy zone (highest Balanced Factor) in the

neighborhood to serve rider requests, while taxis from

the busier zones (lower Balanced Factor) are reserved

for future use. The algorithm can be described as fol-

lows: the appropriate rider r is selected by Lottery

Selection (LS) and the zone where the rider r is lo-

Algorithm 2: Scoring Ride-matching with Lottery

Selection (SRLS).

Input : Rider list l

at zone z at timestamp t

Output: The selected taxi v

at timestamp t.

The Scoring Ride-Matching with Lottery Selection

rider requests cannot be served on time and drivers’

traveling cost would be increased. In previous work, a

Greedy Idle Movement (GIM) was proposed to tackle

the issue. However, this approach cannot adapt to the

dynamic environment. For this reason, a flexible Idle

Movement Strategy based on Q-learning (Watkins

and Dayan, 1992) named Q-Learning Idle Movement

(QIM) is proposed. Each vacant taxis can learn the

movement strategy by itself according to the current

environment.

Considering each taxi as an autonomous agent, we

want to let vacant taxis decide where to go. A Q-

learning approach is applied to train taxi agents such

that they are able to make a reasonable decision in idle

mode. The movement of a vacant taxi is model as a

Markov Decision Process (MDP) (Puterman, 2014).

The components of the MDP are defined as follows:

State: The state s of a taxi is defined as a three tu-

Action: A taxi driver may implement two types of

actions. One action is staying at the current zone z; the

other is moving to an adjacent zone with the lowest

updated Balanced Factor argmin

B

stays at the current zone without receiving rider re-

quests, they will receive a penalty −R

moves to its adjacent zone without receiving rider re-

quests, they will receive a penalty −2R

siders travel cost.

At each simulated cycle, the Q-learning is applied

s

rate.

When a taxi is in idle mode, it will select an action

according to argmax

q(s, a). If a = 0, it would not

move and stop at the current place, otherwise, it will

˙

R

˙

= s

5 EXPERIMENT

The experiment is performed using the taxi data

0.5 if it just drives around within its current area, and

the money spent per unit of travel cost is $2.5. The

patience period is 20 minutes (in other words, after

20 minutes waiting in our simulation, customers will

change to another service). To verify the effectiveness

of the T-Balance, 43,764 rider requests during busy

hours (from 11:00 to 23:59) of a weekday is used.

SMW in (Banerjee et al., 2018) and the Hybrid So-

lution in (Li and Allan, 2020) are implemented as a

baseline. We suppose that all the three methods are

462

T-Balance is better than the two other methods. The

main reason is that the Lottery Selection (LS) helps

the service rate due to dispatching taxis to busy zones

for future use in ride-matching process, and the Q-

learning Idle Movement (QIM) improves both metrics

by guiding vacant taxis to the most needed places to

serve demands.

6 CONCLUSION

plies and demands in each local neighborhood and hot

places. Third, the Q-Learning Idle Movement (QIM)

directs vacant taxis to the most needed places adapt-

ing to the change of the dynamic environment. Four,

comparing our current work to state-of-the-art meth-

ods, the results verify the effectiveness and flexibility

of the T-balance.

REFERENCES

(2018). Chicago data portal: Taxi Trips. City of Chicago.

Banerjee, S., Kanoria, Y., and Qian, P. (2018). State depen-

Chen, M. K. (2016). Dynamic pricing in a labor market:

Curley, R. (2019). Global ride sharing industry valued at

Kleiner, A., Nebel, B., and Ziparo, V. A. (2011). A mech-

Li, J. and Allan, V. H. (2019). A ride-matching strategy

Li, J. and Allan, V. H. (2020). Balancing taxi distribution

464

Lin, K., Zhao, R., Xu, Z., and Zhou, J. (2018). Efficient

Liu, L., Qiu, Z., Li, G., Wang, Q., Ouyang, W., and Lin,

L. (2019). Contextualized spatial–temporal network

for taxi origin-destination demand prediction. IEEE

Transactions on Intelligent Transportation Systems,

20(10):3875–3887.

Lu, A., Frazier, P., and Kislev, O. (2018). Surge pric-

ing moves uber’s driver partners. Available at SSRN

3180246.

Ma, S., Zheng, Y., and Wolfson, O. (2014). Real-time city-

scale taxi ridesharing. IEEE Transactions on Knowl-

edge and Data Engineering, 27(7):1782–1795.

conference on Knowledge discovery and data mining,

pages 45–54.

Stasha, S. (2021). Ride-Sharing Industry Statistics to get

you going in 2021. https://policyadvice.net/insurance/

insights/ride-sharing-industry-statistics/.

Wang, Z., Qin, Z., Tang, X., Ye, J., and Zhu, H. (2018).

Deep reinforcement learning with knowledge transfer

for online rides order dispatching. In 2018 IEEE Inter-

national Conference on Data Mining (ICDM), pages

617–626. IEEE.

Watkins, C. J. and Dayan, P. (1992). Q-learning. Machine

Xu, J., Rahmatizadeh, R., B

¨

ol

¨

oni, L., and Turgut, D. (2018).

Real-time prediction of taxi demand using recurrent

neural networks. IEEE Transactions on Intelligent

Transportation Systems, 19(8):2572–2581.

Xu, Z., Li, Z., Guan, Q., Zhang, D., Li, Q., Nan, J., Liu,

C., Bian, W., and Ye, J. (2018). Large-scale order dis-

patch in on-demand ride-hailing platforms: A learning

and planning approach. In Proceedings of the 24th

ACM SIGKDD International Conference on Knowl-

Zhang, J., Zheng, Y., and Qi, D. (2017a). Deep spatio-

prediction. In Proceedings of the AAAI Conference on

Artificial Intelligence, volume 31.

Zhang, L., Hu, T., Min, Y., Wu, G., Zhang, J., Feng,

Zheng, L., Cheng, P., and Chen, L. (2019). Auction-based