Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

2-2016

Abstract

Spatio-temporal matching of services to customers online is a problem that arises on a large scale in many domains associated with shared transportation (ex: taxis, ride sharing, super shuttles, etc.) and delivery services (ex: food, equipment, clothing, home fuel, etc.). A key characteristic of these problems is that matching of services to customers in one round has a direct impact on the matching of services to customers in the next round. For instance, in the case of taxis, in the second round taxis can only pick up customers closer to the drop off point of the customer from the first round of matching. Traditionally, greedy myopic approaches have been adopted to address such large scale online matching problems. While they provide solutions in a scalable manner, due to their myopic nature the quality of matching obtained can be improved significantly (demonstrated in our experimental results). In this paper, we present a two stage stochastic optimization formulation to consider expected future demand. We then provide multiple enhancements to solve large scale problems more effectively and efficiently. Finally, we demonstrate the significant improvement provided by our techniques over myopic approaches on two real world taxi data sets.

Keywords

Artificial intelligence, Optimization, Sales, Taxicabs, Large-scale problem, On-line matching

Discipline

Artificial Intelligence and Robotics | Technology and Innovation | Transportation

Research Areas

Intelligent Systems and Optimization

Publication

Proceedings of the 30th AAAI Conference on Artificial Intelligence 2016: Phoenix, Arizona, February 12-17

First Page

3271

Last Page

3277

ISBN

9781577357667

Publisher

AAAI Press

City or Country

Palo Alto, CA

Additional URL

https://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/view/12385

Download

Share

COinS