基于树分解的空间众包最优任务分配算法

随着配备高保真传感器的移动设备的普及以及无线网络资费的迅速下降,空间众包成为一种新型的问题解决框架,被用于将位置相关的任务（如路况报告,食品配送）分配给工人（配备智能设备并愿意完成任务的人）。本文研究空间众包中最优任务分配问题,关键在于设计出将每个任务分配给最合适的工人的任务分配策略,以使得完成的总任务数目最大化,而所有的工人可以在完成所分配的任务后,在预期最晚工作时间之前返回起点。找到全局最优分配是一个棘手的问题,因为该问题不等于单个工人的最佳分配的简单累加。本文注意到,仅有部分工人存在任务依赖,因此本文利用树分解技术将工人分割成独立的集合,并提出一种带启发式的深度优先搜索算法,该算法可以快速地更新启发函数界限,从而高效的对不可能成为最优解分配方案尽早地剪枝。实验表明,本文所提出的方法是非常有效的,可以很好地解决最优任务分配问题。