众包,通常是指“一种把过去由专职员工执行的工作任务通过公开的Web平台,以自愿的形式外包给非特定的解决方案提供者群体来完成的分布式问题求解模式”。随着移动设备的普及以及移动互联网的快速发展,传统众包数据的类型在时间和空间上也得到了延伸。因此,传统众包就有了新的发展方向——移动众包。移动众包的核心研究问题包括任务分配、质量控制和隐私保护。根据参与者类别数量的不同,可将基于匹配的任务分配分为2类对象(众包任务和众包工人)任务分配和3类对象(众包任务、众包工人和众包工作地点)任务分配。本文所研究的内容为3类对象在线任务分配。3类对象在线任务分配要求任务分配完成后,需要众包工人和众包任务请求者都移动到众包工作地点,共同参与任务的执行。本文分别研究了在最大化总效用的同时最小化差旅成本的3类对象在线任务分配问题和单一的最小化差旅成本的3类对象在线任务分配问题。在第一项研究内容中,我们针对3类对象的最大化总效用问题提出了QCA(Quality Constraint Algorithm)算法。该算法首先将已有的研究中忽略的单个匹配之间的公平问题(任务报酬和工人的技能熟练度不匹配)量化为匹配质量,然后采用了讨价还价的匹配策略进行分配。同时,在讨价还价的过程中,将任务请求者和工人对差旅成本的偏好也作为价格协商的考虑因素之一。这种分配策略不仅解决了公平问题和降低了差旅成本,而且在总效用方面也优于已有的算法。在第二项研究内容中,我们针对某些任务报酬与所分配工人无关的场景,考虑通过最小化差旅成本实现最大化总效用的解决思路。因此,我们研究了3类对象任务分配问题中最小化差旅成本的问题。针对此问题,我们提出了基于Greedy算法和Hungarian算法的两阶段式解决方案—GH算法。针对此框架中的缺点,我们又提出了GH-AT算法。GH-AT算法在GH算法的基础上添加了自适应阈值机制,并对经典的组合优化算法Hungarian算法进行改进,大大降低了Hungarian算法在带有约束条件的任务分配问题中的时间复杂度。