Publication Type
Journal Article
Version
acceptedVersion
Publication Date
8-2018
Abstract
Online spatio-temporal matching of servers/services to customers is a problem that arises at a large scale in many domains associated with shared transportation (e.g., taxis, ride sharing, super shuttles, etc.) and delivery services (e.g., food, equipment, clothing, home fuel, etc.). A key characteristic of these problems is that the matching of servers/services to customers in one stage has a direct impact on the matching in the next stage. For instance, it is efficient for taxis to pick up customers closer to the drop off point of the customer from the first stage 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 multi-stage stochastic optimization formulation to consider potential future demand scenarios (obtained from past data). We then provide an enhancement to solve large scale problems more effectively and efficiently online. We also provide the worst-case theoretical bounds on the performance of different approaches. Finally, we demonstrate the significant improvement provided by our techniques over myopic approaches and two other multi-stage approaches from literature (Approximate Dynamic Programming and Hybrid Multi-Stage Stochastic optimization formulation) on three real world taxi data sets.
Keywords
Large-scale problem, On-line matching, Online linear programming, Stochastic optimization, MDPs
Discipline
Artificial Intelligence and Robotics | Numerical Analysis and Scientific Computing | Theory and Algorithms
Research Areas
Intelligent Systems and Optimization
Publication
Artificial Intelligence
Volume
261
First Page
71
Last Page
112
ISSN
0004-3702
Identifier
10.1016/j.artint.2018.04.005
Publisher
Elsevier
Citation
LOWALEKAR, Meghna; VARAKANTHAM, Pradeep; and JAILLET, Patrick.
Online spatio-temporal matching in stochastic and dynamic domains. (2018). Artificial Intelligence. 261, 71-112.
Available at: https://ink.library.smu.edu.sg/sis_research/4329
Copyright Owner and License
Authors
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://doi.org/10.1016/j.artint.2018.04.005
Included in
Artificial Intelligence and Robotics Commons, Numerical Analysis and Scientific Computing Commons, Theory and Algorithms Commons