ReVLDB 2017 DI Murich-Germany Flexible Online Task Assignment in Real-Time Spatial Data Yongxin Tong1, Libin Wang, Zimu Zhou2, Bolin Ding, Lei Chen, Jieping Ye5, Ke Xu 1 Beihang University 2 ETH Zurich 3 Microsoft research 4 The hong Kong University of Science and Technology 5 DiDi Research Microsoft 航空航 ETHzurich Researchi 香港科技大 THE HONG KONG UNIVERSITY OF CIENCE AND TECHNOLOGY O DiDi
Flexible Online Task Assignment in Real-Time Spatial Data Yongxin Tong 1 , Libin Wang1 , Zimu Zhou2 , Bolin Ding3 , Lei Chen4 , Jieping Ye5 , Ke Xu1 1 Beihang University 2 ETH Zurich 3 Microsoft Research 4 The Hong Kong University of Science and Technology 5 DiDi Research
Outline o Background and motivation ●Prob| em Statement o Our solutions 上 xperiments ●Conc| usion
Outline ⚫ Background and Motivation ⚫ Problem Statement ⚫ Our Solutions ⚫ Experiments ⚫ Conclusion 2
Outline o Background and Motivation ●Prob| em Statement o Our solutions 上 xperiments ●Conc| usion
Outline ⚫ Background and Motivation ⚫ Problem Statement ⚫ Our Solutions ⚫ Experiments ⚫ Conclusion 3
Real-Time Spatial Data Mobile Internet applications make real-time spatial data ubiquitous Intelligent transportation platforms [ DIDi ∪BER More than a journey Food delivery platforms grubHub yelp Spatial crowdsourcing platforms Gigal BOSTON taskrabbit 22 Life is busy. We can help
⚫ Mobile Internet applications make real-time spatial data ubiquitous ⚫ Intelligent transportation platforms ⚫ Food delivery platforms ⚫ Spatial crowdsourcing platforms Real-Time Spatial Data 4
Why Real-Time task assignment Task assignment is an important issue in many real-time Online-to-Offline(o20)platforms Type Application Issue Intelligent Assign proper drivers transportation (workers)to pick up U BER platforms passengers( tasks) Food delivery Assign proper deliverers platforms grubB (workers) to send food to happy eating users( tasks) Spatial crowdsourcing Gigwalke Assign micro tasks to platforms proper workers
⚫ Task assignment is an important issue in many real-time Online-to-Offline (O2O) platforms Why Real-Time Task Assignment Type Application Issue Intelligent transportation platforms Assign proper drivers (workers) to pick up passengers (tasks) Food delivery platforms Assign proper deliverers (workers) to send food to users (tasks) Spatial crowdsourcing platforms Assign micro tasks to proper workers 5
Existing Research Early research directly models the task assignment problem through the classical offline bipartite matching"problem, which tries to maximize the total number of the assignment Worker Task (1,8) w r2(3,6) r1(2,5 f4(65) 4 7(5,3.5) Ws(8,2) Edge: a worker can 6(4,1)W4(6,1) arrive at the location 012345678X of a task before the deadline of the task Kazemi et aL. Geocrowd: enabling query answering with spatial crowdsourcing In GIS 2012. H. To et al. A server-assigned spatial crowdsourcing framework In TASA 2015
⚫ Early research directly models the task assignment problem through the classical “offline bipartite matching” problem, which tries to maximize the total number of the assignment Existing Research L. Kazemi et al. Geocrowd: enabling query answering with spatial crowdsourcing. In GIS 2012. H. To et al. A server-assigned spatial crowdsourcing framework. In TASA 2015. Worker Task Edge: a worker can arrive at the location of a task before the deadline of the task. 6
Existing Research Early research directly models the task assignment problem through the classical offline bipartite matching " problem, which tries to maximize the total number of the assignment Task w2(1.8)w3(37) Worker r366,7) Cannot handle real-time scenarios where workers and tasks will dynamically appear Ws(8,2) Edge: a worker can 6(4,1)W4(6,1) arrive at the location 012345678X of a task before the deadline of the task Kazemi et aL. Geocrowd: enabling query answering with spatial crowdsourcing In GIS 2012. H. To et al. A server-assigned spatial crowdsourcing framework In TASA 2015
⚫ Early research directly models the task assignment problem through the classical “offline bipartite matching” problem, which tries to maximize the total number of the assignment Existing Research L. Kazemi et al. Geocrowd: enabling query answering with spatial crowdsourcing. In GIS 2012. H. To et al. A server-assigned spatial crowdsourcing framework. In TASA 2015. Worker Task Edge: a worker can arrive at the location of a task before the deadline of the task. Cannot handle real-time scenarios where workers and tasks will dynamically appear ! 7
Existing Research Recent research uses "online bipartite matching'"' to model the real-time task assignment problem When a task/worker appears, the task assignment is performed immediately and irrevocably A rigorous assumption: once a worker appears on the platform, the worker can only wait in place tlil a task is assigned to him/her Y Tong et al. Online Mobile Micro-Task Allocation in Spatial Crowdsourcing. In ICDE2016
⚫ Recent research uses “online bipartite matching” to model the real-time task assignment problem ⚫ When a task/worker appears, the task assignment is performed immediately and irrevocably Existing Research Y. Tong et al. Online Mobile Micro-Task Allocation in Spatial Crowdsourcing. In ICDE2016. A rigorous assumption: once a worker appears on the platform, the worker can only wait in place tlil a task is assigned to him/her 8
9 Existing Research: An Example 9:009:009:019:019:029:039:039:039:049:059:069:079:08 w1 T 12 W3 w4 15 w7 75 5 Wi(1, 6) Each taxi can move one unit distance per minute 012345678X Dr= 2min and dw=10min
1 2 3 4 5 1 2 3 4 5 0 X Y 6 7 8 6 7 8 Existing Research: An Example 𝒘𝟏(𝟏,𝟔) 𝒘𝟏 𝑫𝒓 = 𝟐min and 𝑫𝒘 = 𝟏𝟎min Each taxi can move one unit distance per minute 9
Existing Research: An Example 9:009:0019:019:019:029:039:039:039:049:059:069:079:08 w1 T1 12 W3 w4 15 w7 75 Deadline constraint: If a taxi is in the n16 dotted circle, it can arrive at the position r1(25) of the passenger before her/his deadline 012345678X Dr= 2min and dw=10min
1 2 3 4 5 1 2 3 4 5 0 X Y 6 7 8 6 7 8 Existing Research: An Example 𝒘𝟏(𝟏,𝟔) 𝒘𝟏 𝒓𝟏(𝟐, 𝟓) 𝒓𝟏 Deadline constraint: If a taxi is in the dotted circle, it can arrive at the position of the passenger before her/his deadline 𝑫𝒓 = 𝟐min and 𝑫𝒘 = 𝟏𝟎min 10
