随着移动设备的普及以及无线网络资费的快速下降,空间众包作为一种集群众智慧于一身的新型框架,广泛地用于解决和位置相关的问题(如外卖配送)。工人必须实际行驶到任务指定位置才可以完成任务。本文研究空间众包领域的一个重要问题―任务分配问题,即在满足任务和工人双方限制条件的基础上,采用合理的任务分配方案,最大化任务分配数量。目前主流的任务分配方法主要是从特定场景出发,通过近似解算法,逼近最大化任务分配数量的目标。然而,大部分的任务分配算法对场景的限制条件过多,基于贪心策略的近似解算法通常会陷入局部最优的结果中。和以往方法相比,本文主要关注如何使用精确解算法,解决最大化全局任务分配数量的问题,具体研究内容如下:(1)本文着重研究了空间众包中的任务分配问题,介绍了已有的分配方案,描述了具有代表性的各类算法的优势,并分析了其中存在的问题。(2)本文首次研究工作时间约束下的最优任务分配问题,该模式中工人具有不同工作时长,其完成任务的能力和最晚工作时间相关,该问题消除了以往研究中为工人添加的诸多不切实际的限制,更加贴近实际问题。(3)本文创新性地提出了基于树分解技术的精确解算法,根据工人任务重叠情况为工人划定分组,并使用搜索树结构重新组织工人分组,最后提出了启发式深度优先算法搜索全局最优的分配方案。此外,为提升搜索算法的效率,本文提出三种优化策略,极大地减少了搜索的次数。(4)本文通过实验分析了关键参数对本方案效率的影响,并和已有的最佳任务分配方案进行对比,展示出本算法的有效性。