空间众包下面向任务需求的在线三类分配策略

陈天一，高丽萍

（上海理工大学 光电信息与计算机工程学院，上海 200093）

近年来，空间众包下任务分配问题［1-2］受到越来越多研究者关注，即在满足约束条件的前提下为任务分配合适的工作者。随着互联网的快速发展和移动智能设备的普及，空间众包应用日渐成熟，给人们的生活带来了极大便利。例如，美团外卖、饿了么等平台能够提供美食、药品等多种商品类型，用户可以根据自身意愿选择对应的配送门店购买所需物品。然而，大多数用户在购买商品时，为节约送达时间往往会倾向于选择距离较近的配送点，因此会存在指定地点附近工作者较少的情况，导致平台不得不从更远的地方派遣工作者执行该任务，反而延长了交付时间。

目前，大多数研究［3-10］主要考虑了任务和工作者两类对象，其目标是在满足任务和工作者约束的前提下通过一对一或一对多的匹配模式分配任务。Cheng 等［11］提出通过协调不同平台之间的工作者资源实现动态任务分配以最大化平台总收入。Liu 等［12］设计通过历史数据学习接近最佳阈值的Greedy-OT 算法以最大化分配数量。Chen等［13］研究如何降低分配中最长等待时间以提高用户满意度，并假设任务会一直等待工作者到来，考虑任务具有截止期限。Qian 等［14］提出一种多臂赌博机与批处理相结合的自适应算法，以最小化任务的平均等待时间。Miao等［15］考虑存在不可靠工作者，进而提出一种评估任务质量的概率模型和描述工作者行为的搭便车模型。但是，这些研究都没有考虑配送地点选取对任务分配的影响。

Song 等［16］首次提出了基于三类对象的在线匹配问题，证明此问题的离线版本是NP-hard，并设计一种自适应随机阈值算法以最大化分配总效用。Li 等［17］提出一种3 类稳定匹配问题，以最大限度地增加稳定匹配的数量。Pan等［18］指出文献［16］忽略了任务和工作者之间的距离成本和公平性，通过自动协商的分配方式提高平均匹配质量和总效用。Zheng 等［19］考虑任务不同需求类型，研究如何根据任务需求分配合适的配送地点和工作者，并为工作者规划合适的配送路线使总效用最大化。已有研究［20-23］提出根据任务或工作者的历史数据预测未来分布或质量进行任务分配以满足不同的优化目标。但上述研究都忽略了用户需求和移动成本对任务分配的影响。

本文考虑到任务需求多样性和配送地点选择主观性，以最小化分配成本为目标，根据任务需求为请求者寻找合适的配送点与工作者，提出一种基于贪心的延时匹配算法（TDMG），利用任务的等待时间以获得更好的分配结果，同时通过约束设置快速筛选匹配对以加快分配效率。最后，在模拟数据集与真实数据集上对所提出的算法进行不同参数下的性能比较分析，实验结果证明了本文所提出的方法具有可行性和有效性。

定义1：众包工作者定义为w=＜lw，aw，vw＞，其中lw表示工作者位置，aw表示工作者上线时间，vw表示工作者移动速度。为简化问题，本文假设所有工作者的移动速度均为1，因此分配成本可视作为工作者的移动距离。

定义2：众包任务定义为t=＜lt，at，et，it，Pt＞，其中lt表示任务位置，at表示任务发布时间，et表示任务等待时间，it表示任务所需物品，Pt={p1，p2，...，pn}表示满足所需物品的地点并按其与任务的距离进行升序排列的集合。工作者必须前往相应的配送点p∈Pt领取物品并交付于请求者以完成任务。

定义3：配送地点定义为p=＜lp，Sp＞，其中lp表示地点位置，表示所提供物品类型。配送地点的位置与供应信息都提前已知并存储在众包平台中。为了简化问题，本文假设每个地点包含两种物品类型。

定义4：匹配对定义为(w，p，t)，表示工作者w移动至配送点lp领取物品，然后前往任务所在位置lt进行交付以完成任务。

定义5：分配成本定义为Cost(w，p，t)=d(w，p) +d(p，t)，其中d(.，.)表示任意两点之间的欧式距离。

定义6：面向任务需求的在线三类分配问题定义，给定一组工作者集合W，一组任务集合T以及一组地点集合P，任务与工作者会在随机时间内动态出现在众包平台上，目标函数如式（1）所示。

其目的是在W、T、P中找到匹配集合M，使得任务分配平均成本最小化，其中|M|=表示平台中任务分配的总数量。如果任务匹配成功，则I(w，p，t)=1，反之匹配未成功，则I(w，p，t)=0。同时，满足以下约束条件：①任务在分配时必须选择满足其所需物品的配送地点，即it⊇Sp；
②工作者和任务上线后才可以进行分配，任务超过等待时间将会在平台上消失；
③每一个工作者最多只能分配一个任务，任务被分配后一定会完成。

Tong 等［24］对在线最小匹配的代表性算法进行全面的实验比较，实验表明贪心算法比其他算法有更好的效果，但是贪心算法无法保证未来不会出现比当前更好的分配结果。本文考虑到在任务等待期间内陆续可能会出现新的工作者加入平台，如果任务与新的工作者匹配比与当前在线工作者匹配有更好的效果，则可以将原先被任务占用的工作者释放并将新的工作者分配给任务，从而可以有效地降低任务分配的平均成本。

贪心算法会为每个任务计算所有可能的匹配对，能够有效找到当前最优结果，但是算法运行效率较低。如果当前任务与地点之间的距离d(t，p)不小于当前最小成本Costmin，则组合工作者形成的匹配结果Cost(w，p，t)必然大于Costmin。因此，通过参数δ 对遍历范围进行约束，主要作用是过滤距离较远的配送地点和分配成本较大的匹配对，以提高算法运行效率。同时，δ 的大小会影响算法性能，如果δ 较小，运行效率会提高，但是可能会过滤掉一些优质的匹配对导致分配成本上升。反之δ 较大，可以有效降低分配成本，但是会产生大量不必要的计算导致运行效率降低，因此通过多次实验测试，将δ设置为0.4。

具体执行过程如算法1 所示。算法在每个时刻运行一次，首先更新任务集合和工作者集合（第1 行），通过算法2 检查并处理优化集合中每个匹配对的状态（第2 行）。然后对于每个任务，遍历地点集合，若任务与地点之间的距离不小于δ*当前最小成本，则跳过本次循环以减小搜索空间（第3-6 行）；
然后遍历工作者集合，贪婪地寻找分配成本最小的匹配对并将其存放在优化集合中，同时移除已完成匹配的工作者和任务，并更新阈值γ的大小（第7-15行）。最后输出匹配集合M（第16行）。

在每个时刻，算法2 会为集合内每个匹配对中的任务寻找更合适的工作者，但是这会导致更多的时间支出。为了减少遍历集合所需时间，通过阈值γ判断匹配对的状态。如果匹配对的成本大于γ，任务会继续留在集合中并等待更合适的工作者；
反之如果分配成本不大于γ，则立刻输出匹配对并加入匹配集合。研究发现，合适的阈值约束可以有效地减小集合的计算时间，防止一些表现很好的匹配对继续留在集合中，降低运行效率并浪费用户的时间。算法具体执行过程为：

算法在每个时刻会通过式（2）动态调整阈值大小，从而提高算法分配效果。

其中，Costcur表示当前时刻下已分配任务的平均成本，Costavg表示匹配集合M 中任务分配的总平均成本。θ是调整系数，设置大小为0.1。当Costcur≥Costavg，说明当前时刻下的分配效果比总体的分配效果差，反之则说明当前时刻下的分配效果比总体的分配效果好。

算法会在每个时刻检查每个匹配对的状态，如果当前时间小于任务的截止时间且分配结果大于阈值γ，则遍历满足任务需求的每一个配送地点，若任务与地点之间的距离不小于δ*当前最小花费，则跳过本次循环以加快运行速度（第1-5 行）；
对于这些地点，遍历工作者集合，若存在更优的工作者wnew，则将新的工作者wnew和地点pnew与任务构成匹配并替换当前集合中的匹配对，并将原先被任务占用的工作者释放并重新放回工作者集合（第6-11 行）；
如果当前时刻已经到达匹配对中任务的截止时间或分配结果不大于阈值γ，则将匹配对从集合中移除并加入匹配集合M（第12-14行）。

复杂性分析：算法在每个时刻运行一次，需要同时遍历任务集合、配送点集合和工作者集合，因此算法时间复杂度是O(|T| × |P| × |W|)。同时，算法需要分别存储任务和配送地点、配送地点与工作者之间的距离以及优化集合中的匹配对，空间复杂度是O(|T| × |P|+|P| × |W|)。

通过在不同参数分布的模拟数据集和真实数据集上进行实验，从输入参数δ、三者数量和任务等待时间分别研究不同算法对分配效果和运行效率的影响，以验证所提出算法在分配花费和运行时间上的可行性和有效性。实验比较算法如下：①在线随机算法（Random），即随机选择工作者并分配合适的配送地点使得分配成本最小；
②地点就近分配算法（LNP），即选择距离最近的配送点并分配离配送点最近的工作者；
③贪心算法（Greedy），即选择合适的配送点和工作者使得分配成本最小，即minCost(w，p，t)；
自适应阈值算法（Adaptive-RT），即根据文献［16］中所提出的策略，动态调整使用不同阈值的概率并选择满足阈值约束的匹配对；
④离线算法（Offline），即在所有工作者和任务信息提前已知的前提下，根据贪心策略进行分配，使得分配结果接近最优解。

3.1 实验设置

首先通过在不同参数选取的模拟数据集上进行实验，相关参数如表1 所示（默认设置已加粗表示）。真实数据集使用滴滴平台于2016 年11 月成都市采集的订单数据进行实验，分别将订单起始和订单结束信息视作为任务和工作者信息，并随机抽取不同数量的任务和工作者进行实验。实验环境在macOS 系统下运行，编译平台为PyCharm，CPU 为2.6GHz Core i7，内存为16g。为避免偶然性，所有实验数据均是取10次运行结果的平均值。

Table 1 Parameter setting of simulation dataset表1 模拟数据集参数设置

3.2 实验结果

在TDMG 中改变参数δ 对实验结果的影响如图1所示。

Fig.1 Experimental results of varying the parameter δ图1 改变参数δ的实验结果

可以看出，在分配成本方面，随着参数δ 的取值不断增加，任务分配的平均成本逐渐下降，然后趋于稳定。这是因为当δ 增加时，会扩大TDMG 的搜索空间并获取到更多匹配对，从而得到更好的匹配结果。平均成本在［0.1，0.4］区间内下降幅度非常大，在［0.4，1］区间内趋于平缓并逐渐稳定下来。同时，在运行时间方面，由于搜索空间不断增大，算法运行时间不断攀升，且随着参数的增长上升幅度愈发明显。这是由于随着δ 的增加，需要计算更多的匹配对，从而需要消耗更多时间。兼顾分配成本和运行时间，实验中将δ设置为0.4。

图2 展示了任务、工作者与配送地点三者在不同数量下对实验结果的影响。在分配成本方面，随着时间段内三者数量的不断增多，所有算法的平均成本也随之减小。随着数量的增加，有更多可用的工作者，算法可以匹配更多任务并优化每个任务的分配结果。其中，TDMG 的分配效果最接近Offline 的离线结果并远优于其他在线分配算法，其次是Adaptive-RT、Greedy、LNP、Random。同时，随着分配数量的增多，TDMG 的优化效果越明显。这是由于TDMG 可以利用每个任务的等待时间获得更多工作者，并组成更多表现良好的匹配对。在运行时间方面，随着数量的增加，均逐渐增长。其中，Random 的运行时间最短，其次是LNP、Greedy、TDMG、Adaptive-RT。由于在每次迭代中TDMG 需要同时考虑现在和将来的可用工作者以寻找更好的匹配对，因此分配时间略高于其他3种算法。

Fig.2 Experiment results of varying the number of T，W and P图2 改变任务、工作者与配送地点三者数量的实验结果

图3 展示了任务等待时间逐渐增加对实验结果的影响。在分配成本方面，随着任务等待时间的增加，算法平均成本均逐渐降低，这是由于更长的等待时间可以获得更多表现良好的匹配对。其中，TDMG 最接近Offline 离线结果并优于其他在线分配算法，其次是Adaptive-RT、Greedy、LNP、Random。同时，TDMG 算法的平均成本降低幅度明显，而其他3 种算法降低非常缓慢。这是由于任务等待时间的延长导致TDMG 可以在任务等待期间内寻找更多工作者并组成更好的匹配对，从而使得分配效果更好。算法运行时间均逐渐增长，Random 的运行时间最短，其次是LNP 和Greedy，3 种算法表现都很稳定，没有较大波动趋势，再次是TDMG 和Adaptive-RT。TDMG 一开始低于Greedy，随着任务等待时间的增加而不断增长，逐渐高于其他3 种算法。这是由于任务等待时间增加会导致等待队列中的匹配对数量变多，遍历时间也会逐渐增加。而通过设置约束减小搜索空间，使得运行时间增速放缓，因此在运行效率上仍然足够高效，满足实时性需求。

Fig.3 Experiment results of varying the waiting time of T图3 改变任务等待时间的实验结果

图4 展示了在滴滴数据集下任务、工作者与地点在不同分配数量和等待时间变化下的实验结果。随着三者数量的不断增多，在分配成本方面，所有算法均逐渐减小。Random 算法表现最差，其次是LNP、Greedy、Adaptive-RT，TDMG 在表现上始终优于其他4 种在线算法并最接近Offline 的离线结果。在运行时间方面，Random 算法用时最短，其次是LNP、Greedy、TDMG、Adaptive-RT。

随着等待时间的增加，可以观察到TDMG 的表现最接近Offline 的离线结果，其次是Adaptive-RT、Greedy、LNP、Random。同时，TDMG 分配效果随着时间的增加下降幅度明显，其他算法没有较为明显的变化。在运行时间方面，TDMG 用时增加明显，其他算法较为缓慢。Adaptive-RT 用时相对TDMG 较长，其次是Greedy、LNP、Random。

Fig.4 Experiment results of DiDi dataset图4 滴滴出行数据集下的实验结果

通过在合成数据集和真实数据集上对算法的分配成本和效率进行实验，TDMG 始终得到比Random、LNP、Greedy 和Adaptive-RT 更好的分配效果且最接近Offline 的离线结果，这也说明在任务分配过程中将当前在线工作者和任务等待时间段内出现的工作者一并加入考虑可以有效地提高分配效果。在运行时间方面，Adaptive-RT 最高，TDMG 比Random、LNP、Greedy 需要更多的处理时间，但在运行效率上仍然足够高效，满足实时性需求。

本文提出了面向任务需求的在线分配问题，在动态场景下为每个任务分配合适的配送点和工作者，使得平均分配成本最小化。为了解决这一问题，本文考虑利用任务等待期间出现的工作者寻找更优的匹配结果，并通过阈值约束设置提高任务分配效率。最后，本文通过在模拟数据集和真实数据集上的大量实验验证了所提方法在提升分配效果上的可行性和有效性。在未来工作中，将进一步考虑工作者在接受多个任务时的路线规划问题，为工作者提供合理的执行方案以提高配送效率。

推荐访问:在线 三类 分配