论文阅读笔记：Flexible Online Task Assignment in Real-Time Spatial Data
论文阅读笔记：Flexible Online Task Assignment in Real-Time Spatial Data(VLDB)
Abstract
定义了网约车的实时任务分配问题，希望能够基于预测来对空闲车辆进行安排，提出了POLAR-OP框架，该框架主要分为两个部分，第一个部分是利用预测模型对未来一段时间内的每个地区的车辆数和客人数进行预测，这里使用了网格对地理位置进行划分，使用时间段对时间进行划分。第二个部分是基于第一部分预测的数据进行在线的任务分配，该部分主要分为离线的匹配以及实际的线上分配算法，论文重点讲述了第二部分如何实现。
1. 在线算法评估方式判定
下面的公式是对未来时空的worker数/任务数的分布。
用 Dw,Dr表示，其中aij表示在时间I 地区j预测的worker数量。
Competitive Ratio（CR）：
表示一个在线算法的输出结果与在假设已知未来所有tasks和workers位置下最优化结果之间的差异。
（the differences between the outputs of an online algorithm and the optimal results under the assumption of knowing all the future locations of tasks and workers.）
2. 离线引导匹配生成方法算法
先对预测车辆数/任务数进行车辆先进行分配，当实时分配时，平台会根据这个offline guide 进行分配决策。
这一部分主要是使用了二分图的最大匹配算法，二分图中的节点由worker 和task 组成，其中在同一网格范围和时间段的节点表示同一类型。
3. 线上分配
Object->实际的对象
Node->预测的对象
3.1 POLAR算法：
主要思想：
当实际上一个新的对象到达时，会将其 在offline guide上占有另一个同类型的点然后进行匹配，如果同类型的所有点都被占有了，则忽略，如果与其匹配的点已经被占有，则将o分配给对应的，完成这个匹配。
否则，如果o是一个worker 则分配其去r的空间，如果o是task，就让其等待。
3.2 优化POLAR算法
主要是改善原算法中，直接忽略没有预测到的对象的情况。
Associate ：表示Gf中的节点可以被多个对象重复利用