Online Spatio-Temporal Matching in Stochastic and Dynamic Domains

Spatio-temporal matching of services to customers online is a problem that arises on a large scale in many domains asso-ciated with shared transportation (ex: taxis, ride sharing, su-per shuttles, etc.) and delivery services (ex: food, equipment, clothing, home fuel, etc.). A key characteristic of these prob-lems 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 sec-ond 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 my-opic 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 for-mulation to consider expected future demand. We then pro-vide multiple enhancements to solve large scale problems more effectively and efficiently. Finally, we demonstrate the significant improvement provided by our techniques over my-opic approaches on two real world taxi data sets.