Dynamic coordination of the New York City taxi to optimize the revenue of the taxi service

Taxis are an essential component of the transportation system in most urban centers. The ability to optimize the efficiency of routing represents an opportunity to increase revenue for taxi drivers. Vacant taxis on the road waste fuel, represent uncompensated time for the taxi driver and create unnecessary carbon emissions while also generating additional traffic in the city. In this paper, we utilize Markov Decision Processes to optimize the revenue of taxi drivers through better routing. We present a case study utilizing real-world New York City Taxi data with several experimental evaluations of our model. We achieve approximately 10% improvement in efficiency using data from the month of January, representing the best scenario for an arbitrary taxi driver in that particular period of time. These results also provide a better understanding of how optimization strategies may differ during different times of the day. In the second half of the paper, we present a dynamic fleet management model that can handle random load arrivals with multiple vehicles in Manhattan in a period of 30 minutes. The fleet management problem decomposes into a sequence of time-indexed min-cost network flow subproblems that naturally yield integer solutions. These two methods may have important implications in the field of self-driving vehicles.