任务分配问题是一个被广泛研究的问题,基于空间距离的任务分配是任务分配问题在基于位置的服务中的典型应用,如快递、售后服务及物流等,现有的空间任务分配问题通常以最小化空间距离代价为目标。然而,实际应用中存在另一类空间任务匹配需求,要求被服务对象与服务者之间存在一定的社会关系。服务者与服务对象的社会关系会影响服务效果,通常紧密的社会关系便于沟通、交流。例如在推销保险时,如果销售人员与客户之间具有紧密的社会关系同时空间距离较近,更容易建立销售人员与客户之间的关系,方便以后的沟通合作。基于此需求,本文将社会网络关系结合到空间任务匹配问题中,提出了一种基于空间和社会距离的任务匹配问题。该问题的目标是找到一个既满足空间距离和社会关系的双重约束又满足成员容量限制且总体代价值最小的任务分配结果。本文将节点间的空间距离和社会距离的加权和作为任务代价度量。基本的匹配过程是计算所有服务对象与服务者间的任务代价,然后选择代价最小的匹配。当服务对象与服务者数量较大时,匹配效率较低。本文将该问题转化为二分图多重最优匹配问题,并对二分图构建方法和匹配方法进行优化。本文提出了四类算法实现二分图多重最优匹配过程,分别为完全二分图上的匹配算法、基于排序的完全二分图的匹配算法、启发式构建二分图的匹配算法和动态建边的匹配算法。其中,完全二分图上的匹配算法是根据所有候选成员与任务之间的社会距离和空间距离构建完全二分图,然后对二分图进行分配以求得准确解,该算法需要对候选成员集合和任务集合进行全遍历,代价较大。观察发现,完全二分图在匹配中存在大量冗余边。因此,如何建立少量边的二分图成为本文的一个研究重点和难点。本文提出了启发式构建二分图的匹配算法,该算法采用启发式建边策略进行二分图的构建,能够节省建图时间,具有较高的搜索效率,但求解质量难以保证。在二分图构建完成后,二分图分配过程的优化成为了本文另一个研究重点和难点。因此本文提出了基于排序的完全二分图的匹配算法是对完全二分图上的匹配算法中的分配过程进行了优化,在匹配过程中加入了排序,从而减少了分配时间。为了能够提高查询精确的解的效率,本文提出了动态建边的匹配算法。本文采用真实的数据集对所提出的算法进行验证,综合评估了各类算法的效率与求解质量。同时,本文还对三种启发式构建二分图的匹配算法的查询结果进行了分析,通过改变不同参数分析最终分配结果的质量。最后,本文设计和实现了基于空间位置和社会关系的服务类任务分配系统。