Please use this identifier to cite or link to this item:
Title: Self-Organization and Multi-Agent Reinforcement Learning for Taxi Dispatch
Authors: Alshamsi Omran, Aamena Ali Ahmed
Keywords: taxi dispatch problem
multiagent self organization
reinforcement learning method
Issue Date: Feb-2009
Publisher: The British University in Dubai (BUiD)
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.
Appears in Collections:Dissertations for Informatics (Knowledge and Data Management)

Files in This Item:
File Description SizeFormat 
20050095.pdfFull Text855.13 kBAdobe PDFThumbnail

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.