Publication Type
Journal Article
Version
publishedVersion
Publication Date
8-2017
Abstract
The popularity of Online To Offline (O2O) service platforms has spurred the need for online task assignment in real-time spatial data, where streams of spatially distributed tasks and workers are matched in real time such that the total number of assigned pairs is maximized. Existing online task assignment models assume that each worker is either assigned a task immediately or waits for a subsequent task at a fixed location once she/he appears on the platform. Yet in practice a worker may actively move around rather than passively wait in place if no task is assigned. In this paper, we define a new problem F lexible T wo-sided O nline task A ssignment (FTOA). FTOA aims to guide idle workers based on the prediction of tasks and workers so as to increase the total number of assigned worker-task pairs. To address the FTOA problem, we face two challenges: (i) How to generate guidance for idle workers based on the prediction of the spatiotemporal distribution of tasks and workers? (ii) How to leverage the guidance of workers' movements to optimize the online task assignment? To this end, we propose a novel two-step framework, which integrates offline prediction and online task assignment. Specifically, we estimate the distributions of tasks and workers per time slot and per unit area, and design an online task assignment algorithm, P rediction-oriented O nline task A ssignment in R eal-time spatial data (POLAR-OP). It yields a 0.47-competitive ratio, which is nearly twice better than that of the state-of-the-art. POLAR-OP also reduces the time complexity to process each newly-arrived task/worker to O(1). We validate the effectiveness and efficiency of our methods via extensive experiments on both synthetic datasets and real-world datasets from a large-scale taxi-calling platform.
Discipline
Software Engineering
Research Areas
Software and Cyber-Physical Systems
Publication
Proceedings of the VLDB Endowment
Volume
10
Issue
11
First Page
1334
Last Page
1345
ISSN
2150-8097
Identifier
10.14778/3137628.3137643
Publisher
VLDB Endowment
Citation
TONG, Yongxin; WANG, Libin; ZHOU, Zimu; DING, Bolin; CHEN, Lei; YE, Jieping; and XU, Ke.
Flexible online task assignment in real-time spatial data. (2017). Proceedings of the VLDB Endowment. 10, (11), 1334-1345.
Available at: https://ink.library.smu.edu.sg/sis_research/4509
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.14778/3137628.3137643