Publications -> Conference Papers

Optimizing Efficiency of Taxi Systems: Scaling-up and Handling Arbitrary Constraints


Authors: J. Gan, B. An, and C. Miao
Title: Optimizing Efficiency of Taxi Systems: Scaling-up and Handling Arbitrary Constraints
Abstract: Taxi service is an indispensable part of public transport in modern cities. However, due to its decentralized operation mode, taxi services in many cities are inefficient. Besides, the decentralized nature also poses significant challenges to analyzing and regulating taxi services. State of the art computational methods for optimizing taxi market efficiency suffer from two important limitations: 1) they cannot be scaled up efficiently; and 2) they cannot address complex real-world market situations where additional scheduling constraints need to be handled. In this paper, we propose two novel algorithms — FLORA and FLORA-A — to address the inadequacies. Using convex polytope representation techniques, FLORA provides a fully compact representation for taxi drivers’ strategy space and scales up more efficiently than existing algorithms. FLORA-A avoids enumerating the entire exponentially large pure strategy space by gradually expanding the strategy space. It is the first known method capable of handling arbitrary scheduling constraints for optimizing taxi system efficiency. Experimental results show orders of magnitude improvement in speed FLORA provides, and the necessity of using FLORA-A as suggested by changes in the taxi drivers’ operation strategy under different market conditions.
Keywords: Taxi system; Game theory; Optimization
Conference Name: 14th International Conference on Autonomous Agents and Multi-agent Systems (AAMAS'15)
Location: Istanbul, Turkey
Publisher: IFAAMAS
Year: 2015
Accepted PDF File: Optimizing_Efficiency_of_Taxi_Systems_Scaling-up_and_Handling_Arbitrary_Constraints_accepted.pdf
Permanent Link: http://www.ifaamas.org/Proceedings/aamas2015/aamas/p523.pdf
Reference: J. Gan, B. An, and C. Miao, “Optimizing efficiency of taxi systems: Scaling-up and handling arbitrary constraints,” in Proceedings of the 14th International Conference on Autonomous Agents and Multi-agent Systems (AAMAS’15). IFAAMAS, May 2015, pp. 523–531.
bibtex: 
@inproceedings{LILY-c34, 
   author	= {Gan, Jiarui and An, Bo and Miao, Chunyan},
   title	= {Optimizing Efficiency of Taxi Systems: Scaling-up and Handling Arbitrary Constraints},  
   booktitle	= {Proceedings of the 14th International Conference on Autonomous Agents and Multi-agent Systems (AAMAS'15)}, 
   year		= {2015}, 
   month	= {May}, 
   pages	= {523-531}, 
   location	= {Istanbul, Turkey},
   publisher	= {IFAAMAS},
}