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

来源：软件学报杂志2018年第3期北京时间：

作者：李洋,贾梦迪,杨文彦,赵艳,郑凯

单位：李洋，苏州大学 计算机科学与技术学院, 江苏 苏州 21500611,贾梦迪，苏州大学 计算机科学与技术学院, 江苏 苏州 21500602,杨文彦，苏州大学 计算机科学与技术学院, 江苏 苏州 21500603,赵艳，苏州大学 计算机科学与技术学院, 江苏 苏州 21500604,郑凯，苏州大学 计算机科学与技术学院, 江苏 苏州 21500605

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

关键词：空间众包;任务分配;任务依赖;树分解;最优解算法