学位论文简介

任务分配是空间众包中的基础研究课题，其有助于众包平台高效地指导指导工人完成指定任务获得高额回报。在滴滴出行，美团外卖，饿了么等的实际平台中发挥着关键作用。本文以空间众包作为研究课题应用，探索任务分配中的关键技术，取得主要的创新成果如下：

(1) 基于满意度的任务分配。针对多工作者协同完成复杂任务的场景，本研究旨在实现用户满意度最大化的任务分配结果。为此，我们通过量化工作者协作的熟练程度，进而衡量用户满意度，并构建了一个以最大化用户满意度为目标的研究模型。为了有效地得出任务分配方案，我们设计了两种算法：一种是基于贪心策略的分配算法，另一种则采用了博弈论原理。本研究不但证明了该问题为NP难问题，并证明了所提出的贪心算法的近似度为$1-\frac{1}{e}$。此外，我们同样证明了本研究所提出的基于博弈论的算法可以达到纳什均衡，并证明该解可实现满意度最大化的分配结果。

(2) 基于众包工作者轨迹的联盟任务分配。在考虑工作者轨迹的任务联盟分配方面，现有研究常常假设众包工作者投入全职工作，但在共享经济的背景下，参与众包任务的多为兼职人员，他们有自己的工作时间和路线安排。为此，将任务自然融入到他们日常轨迹和时间表中，便成为有效利用兼职资源的关键。本研究依托于工作者的固定轨迹，对周边任务进行打包，形成任务联盟，并嵌入到工作者的日常路线中，从而达到最大化任务完成率。本研究证明了为众包任务分配任务联盟是NP难问题。并提出了MEG算法为每个工作者规划了一条完成分配任务联盟的最优路径。

(3) 基于双边偏好预测的稳定匹配。现有任务分配算法虽然可快速且实现高效益的分配结果，但是分配过程中往往仅考虑其中一方的利益，或者工人，或者用户。已有的研究工作鲜有同时考虑多方的利益从而实现平台的长远发展。因此，本研究旨在于实现双方都有选择权利的稳定匹配。此外，传统的研究通常基于工作者与任务之间的地理位置信息，忽略了工人和用户有各自偏好的场景。我们通过预测众包工作者以及任务请求者的潜在偏好，根据这些预测来实现一个双方都满意的稳定匹配任务分配，从而超越了仅基于地理定位的传统分配方法，为复杂偏好环境中的任务分配问题提供了全新的解决途径。

主要学术成果

[1] Xie Y, Wu F, Zhou X, et al. Trajectory-aware Task Coalition Assignment in Spatial Crowdsourcing[J]. IEEE Transactions on Knowledge and Data Engineering, 2023. (第一作者，SCI 2区，CCF A类期刊)

[2] Xie Y, Wu F, Zhou X, et al. Trajectory-aware Task Coalition Assignment in Spatial Crowdsourcing (Extended Abstract). IEEE International Conference on Data Engineering (ICDE).（第一作者，CCF A 类会议）

[3] Xie Y, Wang Y, Li K, et al. Satisfaction-aware task assignment in spatial crowdsourcing[J]. Information Sciences, 2023, 622: 512-535. (第一作者，SCI一区)