Self-Organization and Multi-Agent Reinforcement Learning for Taxi Dispatch

Abstract

The taxi dispatch problem involves assigning taxis to callers waiting at different locations. An adjacency-based dispatch system currently in use by a major taxi company divides the city(in which the system operates) into regional dispatch areas. Each area has fixed designated adjacent areas hand-coded by human experts. When a local area does not have vacant cabs,the system chooses an adjacent area to search. However, such fixed, hand-coded adjacency of areas is not always a good indicator because it does not take into consideration frequent changes in tra ffic patterns and road structure. This causes dispatch o fficials to override the system by manually enforcing movement on taxis. In this thesis, I apply two different methods separately to solve the problem: (1) a multiagent self organization technique to dynamically modify the adjacency of dispatch areas (2) a multiagent reinforcement learning method to optimize the dispatch policy for each area. I compare performance of each method with actual data from,and a simulation of, an operational dispatch system. The multiagent self organization technique decreases the total waiting time by up to 25% in comparison with the real system and increases taxi utilization by 20% in comparison with results of the simulation without self-organization. Interestingly, I also discover that human intervention (by either the taxi-dispatch offi cials or the taxi drivers) to manually overcome the limitations of the existing dispatch system can be counterproductive when used with a self-organizing system. Furthermore, the proposed multiagent reinforcement learning method decreases the total waiting time by up to 33.5% in comparison with the real system.