Locating lucrative passengers for taxicab drivers

In an urban setting, such as the city of Beijing, after a taxi driver drops the previous passenger, he/she needs to decide where to drive to find the next --- preferably lucrative --- passenger. Different drivers follow different strategies that are mostly based on personal experiences. In this work, we analyze large amounts of GPS location data of taxicabs to compute a high-level profit-maximizing strategy for taxi drivers. Formally, we model the problem of finding a passenger as a Markov Decision Process (MDP) whose parameters are estimated from the GPS data. For this MDP, we compute an optimal policy using dynamic programming. We show that the proposed strategy captures meaningful rules for finding a passenger and we demonstrate that taxi drivers whose behaviors agree with our proposal generate more profit than average drivers.