  Empty taxi cruising represents a wastage of resources in the context of urban
taxi services. In this work, we seek to minimize such wastage. An analysis of a
large trace of taxi operations reveals that the services' inefficiency is
caused by drivers' greedy cruising behavior. We model the existing system as a
continuous time Markov chain. To address the problem, we propose that each taxi
be equipped with an intelligent agent that will guide the driver when cruising
for passengers. Then, drawing from AI literature on multiagent planning, we
explore two possible ways to compute such guidance. The first formulation
assumes fully cooperative drivers. This allows us, in principle, to compute
systemwide optimal cruising policy. This is modeled as a Markov decision
process. The second formulation assumes rational drivers, seeking to maximize
their own profit. This is modeled as a stochastic congestion game, a
specialization of stochastic games. Nash equilibrium policy is proposed as the
solution to the game, where no driver has the incentive to singly deviate from
it. Empirical result shows that both formulations improve the efficiency of the
service significantly.
